AVL 트리

모든 노드에서 왼쪽과 오른쪽의 서브트리의 높이 차이가 1 이하를 유지하는 BST

위 BST는 어떤 노드에서 보더라도 왼쪽 서브트리와 오른쪽 서브트리의 높이차이가 1이하이다.

이러한 상태를 유지하기 위해 모든 노드는bf(=balance factor)를 관리한다. 모든 노드의 bf의 절대값을 1이하가 되도록 하는 것이다.

 

트리의 좌우 균형이 무너지는 순간은 삽입/삭제 이후이다.

 

삽입/삭제후 균형이 무너지는 경우는 총 4가지 상황이 있고, 이 4가지상황에서 각각 어떻게 균형을 맞출 수 있는지 이해하자.

 

 

LL 케이스

 

균형이 무너진 첫 번째 유형이다. 왼쪽 높이는 2인데 오른쪽 높이는 0 이라서 20노드를 기준으로 balance factor(left height - right height) 가 2가 되었다. 이럴 때는 우회전(LL)을 한번 해준다.

 

RR 케이스

 

22노드를 삽입한 이후 12노드에서 밸런스가 무너진 것이 포착되었다. 오른쪽 높이는 2인데 왼쪽 높이는 0 이므로 bf값이 -2가 되었다.

 

RL 케이스

왼쪽이 2, 오른쪽은 높이가 0인데 지금까지와는 조금 다르다. 이런 경우는 왼쪽으로 한번 돌려준 후 오른쪽으로 돌려준다.

 

LR 케이스

RL돌리기와 대칭되는 상황이라고 보면 된다. 이때는 오른쪽으로 돌리고, 왼쪽으로 돌려주면 된다.