트리의 높이가 O(Log n)이면 이진 트리가 균형을 이룹니다. 여기서 n은 노드 수입니다. 예를 들어, AVL 트리는 왼쪽과 오른쪽 하위 트리의 높이 차이가 최대 1이 되도록 하여 O(Log n) 높이를 유지합니다. Red-Black 트리는 숫자가 다음과 같은지 확인하여 O(Log n) 높이를 유지합니다. 모든 루트-리프 경로의 검정색 노드 수는 동일하며 인접한 빨간색 노드가 없습니다. 균형 이진 검색 트리는 검색, 삽입 및 삭제에 O(log n) 시간을 제공하므로 성능 측면에서 좋습니다.
균형 이진 트리는 다음 세 가지 조건을 따르는 이진 트리입니다.
- 모든 노드의 왼쪽 및 오른쪽 트리 높이는 1 이상 차이가 나지 않습니다.
- 해당 노드의 왼쪽 하위 트리도 균형을 이루고 있습니다.
- 해당 노드의 오른쪽 하위 트리도 균형을 이루고 있습니다.
단일 노드는 항상 균형을 이루고 있습니다. 높이 균형 이진 트리라고도 합니다.
예 :
균형 및 불균형 이진 트리
각 노드에 대한 왼쪽 하위 트리와 오른쪽 하위 트리의 높이 차이가 0 또는 1인 이진 트리의 일종입니다. 위 그림에서 값이 0인 루트 노드는 깊이 2단위로 불균형을 이루고 있습니다. .
균형 이진 트리의 적용:
균형 이진 트리의 장점:
- 비파괴 업데이트는 동일한 점근 효과를 갖는 균형 이진 트리에서 지원됩니다.
- 올바른 순서의 범위 쿼리 및 반복은 균형 이진 트리를 통해 가능해집니다.