자가 균형 이진 탐색 트리(Self-balancing Binary Search Tree)에 대해 설명하세요
Keyword
균형 트리, 편향 트리, balance factor
Script
평균적으로 Binary Search Tree에서 탐색에 있어 시간복잡도는 O(log n)입니다. 하지만 편향 트리(skewed tree)가 만들어지면, 최악의 경우 탐색에 있어 O(n)의 시간복잡도를 가집니다. 이 문제를 해결하기 위해 균형 트리를 사용할 수 있습니다. 먼저 균형 트리(balanced tree)는 모든 sub tree의 높이차가 1이하인 tree를 말합니다. 이때 balance factor를 사용해서 균형을 유지하는데, balance factor는 왼쪽과 오른쪽 sub tree의 높이의 차이를 의미합니다. 이 balace factor와 일정한 규칙에 따라 노드 분할 및 병합 또는 회전을 통해 균형을 유지하는 binary search tree를 self-balancing binary search tree라고 합니다.
Additional
Balance Factor(BF)
Balance Factor (k) = height (left(k)) - height(right(k))Balance Factor는 왼쪽 sub tree의 높이에서 오른쪽 sub tree의 높이의 차이다.
with programming