[기술 면접] 7. BST(Binary Search Tree), 이진 탐색 트리는 어떤 자료구조인가요?

저번 시간에 이어, 이번에는 BST(Binary Search Tree, 이진 탐색 트리)에 대해 알아보겠습니다. 자료구조 질문들 중엔, 상대적으로 난이도가 높은 편에 속하는 개념이며, 빈출 빈도는 조금 낮은 편에 속합니다. 하지만, 종종 마주한 경험이 있으니, 이번 기회에 정리해 보시길 권해드립니다.

Q: BST(Binary Search Tree, 이진 탐색 트리)는 어떤 자료구조인가요?

이진 탐색트리는 정렬된 tree입이니다. 어느 node를 선택하든 해당 node의 left subtree에는 그 node 값보다 작은 값들을 지닌 node로만 이루어져 있습니다. 그리고 right subtree에는 그 node의 값보다 큰 값들을 지닌 node로만 이루어져 있는 O(log n)의 binary tree입니다.

BST는 저장과 동시에 정렬을 하는 자료구조로, 노드들을 바닥에 투영 시 오름차순 정렬 된다는 것을 알 수 있습니다.

Q: 이진트리(Binary tree)는 어떤 자료구조인가요?

모든 node의 child nodes 갯수가 2 이하인 트리를 이진트리라고 합니다.

Q: BST의 worst case의 시간복잡도는 어떻게 되며, 어떤 경우에 발생하나요?

O(n)이며, 균형 없이 한 쪽으로 치우친 tree의 경우 발생합니다. Linked List와 다를 게 없어진다고 볼 수 있습니다.

해결 방법으로는 자가 균형 이진 탐색 트리(Self-Balancing BST)가 있습니다. 이진 트리의 균형을 유지하며, 대표적으로 AVL트리와 Red-Black Tree가 있습니다. Java에서는 hashmap의 sepaerate chaining으로써 Linked List와 Red-Black Tree를 병행하여 저장합니다.

• AVL Tree : 균형도를 사용하여 삽입/삭제 시 균형을 맞춥니다. 균형도가 절댓값 2 미만이면 균형 트리이며, 2 이상이면 불균형 트리입니다.
  • leaf노드의 높이는 항상 0
  • 자식이 한 개만 있으면 없는 쪽은 -1로 계산(null node)
  • 부모 노드 높이 = Max(좌측 노드 높이, 우측 노드 높이) + 1
  • 균형도 = 좌측 노드 높이 – 우측 노드 높이
    • 균형도가 양수 : 좌측 서브 트리가 비대
    • 균형도가 음수 : 우측 서브 트리가 비대
• Red-Black Tree :
  • 모든 노드는 red, black으로 구성
  • 루트 노트는 black
  • nil 노드는 black : nil 노드는 존재하지 않음을 의미하며 자녀가 없을 때 자녀를 nil노드로 표기함으로써 값이 있는 노드와 동등하게 취급합니다. RB트리에서 leaf노드는 nil노드로 계산합니다.
  • red의 자녀들은 black, red는 연속일 수 없습니다.
  • 임의의 노드에서 자손 nil 노드들 까지 가는 경로들에서 black의 수는 같습니다.
  • black height : 노드 x에서 임의의 자손 nill 노드까지 내려가는 경로에서의 black 수.

마치며

이번 시간에는 BST(Binary Search Tree, 이진 탐색 트리)에 대해 알아보았습니다. 다른 자료구조에 비해 등장 빈도는 조금 낮지만, BST 질문 이후, BST의 Worst Case에 대해 답하고, 그에 대한 해결방안까지 답변할 수 있다면, 굉장히 경쟁력 있는 점수를 받을 수 있을 것으로 생각합니다. 그러니 반드시 숙지하시길 권해드립니다.

다음 시간에는, Hash Table에 대해 알아보겠습니다.