AVL 트리

AVL 트리

AVL 트리 개념

• 이진 탐색 트리(BST)의 한 종류
  • 이진 트리는 모든 노드가 가지는 자식 노드를 최대 2개 가지는 형태다.
  • 이진 탐색 트리는 이진 트리의 모든 노드가 왼쪽 서브 트리는 자기보다 작은 값이, 오른쪽 서브 트리에는 큰 값이 배치되는 특징이 있다.
• 스스로 균형(balancing)을 잡는 트리
• balance factor를 통해 균형 유지

balance factor

balance factor는 위와 같은 이진 탐색 트리가 있을 때 임의의 노드 x에 대해서 (왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이)의 값을 말한다.

AVL 트리 특징

AVL 특징은 간단한다. (왼쪽 서브트리의 높이 - 오른쪽 서브트리의 높이)의 값은 balance factor라고 했다. AVL 트리의 특징을 가지려면 트리의 모든 노드들이 이 balance factor의 값이 {-1, 0, 1} 범주안에 있어야 한다. 위 그림은 50의 노드인 경우에만 구했지만 다른 노드들을 똑같이 구해보면 모두 {-1, 0, 1} 범주안에 있다는 것을 확인할 수 있다.

-1: 자식 노드가 없을 때
0: 자식 노드가 1개 있을 때
1: 자식 노드가 2개 있을 때

AVL 트리의 균형을 잡는 방법은 트리에 삽입 혹은 삭제 후 balance factor의 값이 {-1, 0, 1} 범주안에 있지 않다면 균형을 맞추는 작업을 수행한다.

AVL 트리 연산

1. 1단계에서는 50의 루트 노드와 70의 오른쪽 서브 노드가 있다. 이 때는 AVL 트리가 성립한다.
2. 2단계에서는 90의 노드를 추가했다.
3. 3단계에서는 balance factor를 계산했더니 값이 {-1, 0, 1} 범주안에 있지 않다.
4. AVL 트리는 균형을 잡기 위해 70 노드를 Rotate 시킨다. 그러면 AVL 트리의 특징을 갖추게 된다.

정리

• 삽입/삭제를 위해서 루트 노드에서 적절한 위치까지 찾아서 처리를 해준다.
• 삽입/삭제 후 균형이 깨졌는지 확인하기 위해 삽입/삭제가 발생한 위치에서 루트 노드로 거꾸로 올라오면서 balance factor를 확인하여 균형이 깨졌다면 재조정을 해준다.
• 시간복잡도는 이진 탐색 트리의 경우 최악의 경우 O(N)이다. 하지만 AVL 트리는 균형을 맞추기 때문에 최악의 경우에도 O(log N)이다.
• 하지만 단점이 있다. 엄격하게 균형을 유지하기 때문에 삽입/삭제시 트리 균형을 확인하고 만약 균형이 깨졌다면 트리 구조를 재조정하기 때문에 시간이 꽤 소요된다.
• 이 문제를 해결한 것이 Red-black 트리이다.

References

• 쉬운코드 - AVL 트리