AVL tree에 대한 깨달음

데이터 구조에서 Binary Search Tree(BST)를 배운 뒤 BST의 치명적인 약점을 알게 된다.

BST는 고르게 잘 분포해 있을 때는O(logN)의 복잡도로 insert, delete, search가 가능하지만, 만약 데이터가 한쪽으로 쏠리게 되면 skewed tree의 형태가 만들어져 O(N)의 복잡도가 되어버린다.

 

AVL( Adelson-Velsky and Landis )tree는 이렇게 데이터가 쏠리는 것을 방지한다.

각 노드마다 양쪽 height를 비교하여 그 차이가 1을 넘을 수 없도록 하는 것이다. 그러면 balanced tree가 된다.

Left height - right height를 balance factor로 정의하며 balance factor의 절댓값이 1을 넘지 못하도록 한다.

그리고 1을 넘게 되면 그 즉시 Violation! 으로 tree의 모양을 꼬물꼬물 바꾼다.

 

총 네가지 Violation 상황에 따른 꼬물꼬물 방법을 그림으로 정리해 보았다.

AVL binary tree 꼬물꼬물 1

AVL binary tree 꼬물꼬물 2

위 증명을 하다가 궁금했던 점은, T1, T2, T3의 Height가 다른 경우에는 증명을 하지 않아도 되나? 였다.

그런데 고민을 해보니 위 증명으로 충분했다. 다른 상황의 경우 아래 두 가지 이유로 따로 증명할 필요가 없었다.

 

1. 그 상황은 이미 balance factor violation 되는 상황, 우리의 증명은 balance 한 상황 -> violation을 봄

2. 그 상황은 이미 too balanced. 추가적인 insert가 있으면 결국 우리의 증명 네 가지 상황 중 하나가 됨 

 

반론이나 질문은 환영입니다.