참고 자료 : https://velog.io/@min9288/백엔드-기술-면접-질문자료구조

• 힙이란 : 완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어졌고, 여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조 입니다.

• 힙의 삽입, 삭제 :

  힙의 삽입

  1. 힙에 새로운 요소가 들어오면, 일단 새로운 노드를 힙의 마지막 노드에 이어서 삽입합니다.

  2. 새로운 노드를 부모 노드들과 교환해서 힙의 성질을 만족시킵니다.

  힙의 삭제

  1. 최대 힙에서 최댓값은 루트 노드이므로 루트 노드가 삭제됩니다.

  • 최대 힙(max heap)에서 삭제 연산은 최댓값을 가진 요소를 삭제하는 것 입니다.

  2. 삭제된 루트 노드에는 힙의 마지막 노드를 가져옵니다.

  3. 힙을 재구성합니다.

• 힙이 할수있는 것을 균형 이진 트리가 할수 있지않나?

• 이진 탐색 트리 : 왼쪽 자식은 부모보다 작고, 오른쪽 자식은 부모보다 큰 이진트리, 이진탐색트리는 이진탐색의 효율적인 탐색능력과, 연결리스트의 장점을 모두 따와 노드의 탐색과, 삽입, 삭제연산에 대해 평균적으로 O(logN)의 시간복잡도를 보입니다.

• 이진 탐색 트리 삽입, 탐색, 삭제

• 자가 균형 트리 : 삽입/삭제 시 자동으로 depth (루트로 부터 내려갈 수 있는 최대 레벨)를 최소로 유지하는 노드 기반 이진 탐색 트리 ( depth가 최소인 것은 Complete binary tree인 경우 ) 입니다.

• AVL : AVL 트리란 한 쪽으로 값이 치우치는 이진 탐색 트리(Binary Search Tree, BST)의 한계점을 보완하기 위해 만들어진 균형 잡힌 이진 트리입니다. AVL은 항상 좌/우로 데이터를 균형잡힌 상태로 유지하기 위해 추가적인 연산을 진행합니다.

• Red Black Tree : 레드블랙 트리는 모든 노드를 빨간색 또는 검은색으로 색칠합니다. 그리고 연결된 노드들은 색이 중복되지 않도록 관리됩니다.

• 해시 : 키값이 배열의 인덱스 값으로 사용하기에는 적당하지 않고, 키값의 범위가 매우 넓어서 매우 큰 배열이 필요한 문제를 해결하기 위해 해시를 사용합니다. 넓은 범위의 키를 좁은 범위의 키로 변경하는 역할을 수행합니다.

• 충돌회피 방법 :

  만약 서로 다른 두 개의 키가, 해쉬 함수를 통과하였는데, 그 결과가 같다면 이를 충돌이라고 합니다.

  충돌이 많이 일어난다면, O(1)으로 값을 탐색할 수 있는 장점이 없어집니다. 해시 충돌을 최소화 하기 위해서 테이블의 크기를 소수로 사용해서 만들어야 합니다.

  만약 충돌이 난다면, 해결하는 방법이 크게 2가지가 있는데, 개방 주소법과 분리 연결법이 있습니다.

  개방 주소법

  • 배열만을 사용하며, 저장 인덱스가 겹칠 경우 해당 인덱스의 옆 인덱스에 저장하는 방식입니다.
  • 옆에 인덱스와 데이터 충돌이 일어나면 다시 옆 인덱스에 저장합니다.
  • 충돌 데이터가 많이 발생하면 성능에 심각한 문제가 발생합니다.

  분리 연결법

  • Hash Table 에 연결 리스트에서 사용하는 Node 객체를 저장합니다.
  • Hash Table의 셀마다 연결 리스트를 하나씩 저장하고 충돌이 발생하는 데이터는 연결 리스트의 다음 노드에 추가합니다.
  • 데이터를 검색할 때는 Hash Table의 인덱스를 찾은 후 셀에 연결된 리스트를 순차적으로 탐색하며 찾으려는 Hash Code 와 저장된 Node의 Hash Code를 비교하는 것입니다.