균형 트리란?

이진 탐색 트리는 탐색 트리의 높이에 따라 비교 연산의 횟수가 달라집니다.

노드의 수가 같다면 트리의 레벨이 최소인 경우에서가 가장 적은 횟수를 가질 수 있고 편향 이진 트리에서 가장 높은 횟수를 가질 수 있습니다.

그렇기때문에 레벨을 최소화할 수 있도록 균형을 맞춰주는 조건을 추가하여 정의하는 트리를 균형 트리 혹은 균형 이진 탐색 트리라고 합니다.

AVL (Adelson-Velskii Landis Tree)

아델슨 벨스키와 란디스가 제안한 대표적인 균형 이진 탐색트리인 AVL은 왼쪽 서브트리의 높이 hL과 오른쪽 서브트리의 높이 hR의 차이를 1 이하로 합니다.

AVL 트리의 특징은 다음과 같습니다.

1. 왼쪽 서브트리 < 부모 노드 < 오른쪽 서브트리의 관계를 가집니다
2. 균형 인수 BF(hL - hR)를 관리합니다.
3. 각 노드의 균형 인수는 {-1, 0, +1}의 세 값만 가질 수 있습니다

말단 노드부터 조상 노드까지 BF를 확인하면서 진행하고 노드를 추가한 시점에서 BF의 절대값이 1을 초과했을 때 회전 연산을 통해 균형을 회복합니다.

하나의 자식 노드를 가지고 있는 자식노드만 가지고 있는 노드가 있을 때 오른차순으로 정렬 후 가운데 있는 노드를 부모노드로, 좌 우의 노드를 자식 노드로 가지게 수정하는 방식입니다.

• LL 회전 연산

  

• RR 회전 연산

  

• LR 회전 연산

  

• RL 회전 연산