여기에서 균형 이진 검색 트리가 무엇인지 볼 수 있습니다. 이진 검색 트리(BST)는 왼쪽 자식에 더 작은 요소가 있고 오른쪽 자식에 더 큰 요소가 있는 이진 트리입니다.
BST에서 요소를 검색하는 평균 시간 복잡도는 O(log n)입니다. 이진 탐색 트리의 높이에 따라 다릅니다. 이진 검색 트리의 속성을 유지하기 위해 트리가 왜곡되는 경우가 있습니다. 따라서 기울어진 나무는 다음과 같이 보일 것입니다 -
이것은 실제로는 트리지만 연결된 목록처럼 보입니다. 이러한 종류의 트리의 경우 검색 시간은 O(n)입니다. 바이너리 트리에는 효과적이지 않습니다.
이러한 문제를 극복하기 위해 높이가 균형을 이루는 나무를 만들 수 있습니다. 그래서 나무는 죽임을 당하지 않을 것입니다. 강제로 우리는 균형을 만들 것입니다. 따라서 노드의 각 면에는 높이가 거의 동일한 하위 트리가 있습니다.
균형을 잡기 위한 다양한 기술이 있습니다. 그 중 일부는 -
-
AVL 트리
-
적-검정 나무
위 예제의 높이 균형 형태는 다음과 같습니다. -
