[알고리즘] Tree 4 - AVL tree

- 이진 트리이다.
- 각각의 노드마다 왼쪽과 오른쪽 sub-tree의 높이 차이에 대한 정보를 가지며 부분 트리의 높이 차이가 1보다 크지 않은 성질을 가진다.
- O(lon n) 의 시간 복잡도로 검색, 삽입, 삭제를 할 수 있다.
- 삽입, 삭제 시 원하는 노드를 찾기 위해 2개의 경로가 필요하기 때문에 레드-블랙 트리 만큼 효율이 좋지 않아 자주 쓰이지 않는다.
- 노드가 삽입, 삭제 될 때 회전(rotation)을 통해 트리를 재구성 한다.

[회전]

균형이 맞지 않은 경우 (양쪽 서브트리의 높이 차이가 2이상 나는 경우)
아래와 같이 네가지 회전 방법을 통해 균형을 맞춰 준다.

LL

조건

왼쪽 서브트리의 높이가 오른쪽 서브트리 높이보다 2이상 크고
왼쪽 서브트리의 왼쪽 서브트리가 오른쪽 서브트리의 높이보다 큰 경우 
- left - left 로 길어짐으로 LL이라 명명한다.
- 오른쪽으로 돌려준다.

- 균형이 틀어진 노드를 NodeA라 하고 왼쪽 서브트리 쪽 첫번째 노드를 NodeB라 할 경우

NodeA.left = NodeB.right   NodeB.right = NodeA

RR

조건
오른쪽 서브트리의 높이가 왼쪽 서브트리 높이보다 2이상 크고
오른쪽 서브트리의 오른쪽 서브트리가 왼쪽 서브트리의 높이보다 큰 경우 
- right - right 로 길어짐으로 RR이라 명명한다.
- 왼쪽으로 돌려준다.

- 균형이 틀어진 노드를 NodeA라 하고 왼쪽 서브트리 쪽 첫번째 노드를 NodeB라 할 경우

NodeA.right = NodeB.left   NodeB.left = NodeA

LR

조건
왼쪽 서브트리의 높이가 오른쪽 서브트리 높이보다 2이상 크고
왼쪽 서브트리의 오른쪽 서브트리가 왼쪽 서브트리의 높이보다 큰 경우 
- left - right 로 길어짐으로 LR이라 명명한다.
- 서브트리를 왼쪽으로 돌려주고 다시 전체를 오른쪽으로 돌린다.

- 균형이 틀어진 노드를 NodeA라 하고 왼쪽 서브트리 쪽 첫번째 노드를 NodeB라 할 경우

RR(NodeB)   NodeB.right = NodeA

RL

조건
오른쪽 서브트리의 높이가 왼쪽 서브트리 높이보다 2이상 크고
오른쪽 서브트리의 왼쪽 서브트리가 오른쪽 서브트리의 높이보다 큰 경우 
- right - left 로 길어짐으로 RL 이라 명명한다.
- 서브트리를 오른쪽으로 돌려주고 다시 전체를 왼쪽으로 돌린다.

- 균형이 틀어진 노드를 NodeA라 하고 왼쪽 서브트리 쪽 첫번째 노드를 NodeB라 할 경우

LL(NodeB)   NodeB.left = NodeA

[삽입]

- BST와 같은 방식으로 삽입 후 균형이 맞지 않으면 회전으로 맞추어 준다.

[삭제]

- 삭제되는 노드가 leaf 노드인 경우 삭제만 하면 된다.
- 삭제되는 노드가 leaf 노드가 아닌 경우
  왼쪽 서브트리의 가장 큰 값 혹은 오른쪽 서브트리의 가장 작은 값으로 대체한다.
  leaf 노드가 될 때까지 반복하다 leaf 노드가 되면 삭제한다.
- 삭제 후에 균형이 맞지 않으면 회전으로 맞추어 준다.

[소스]