자료구조 - AVL Tree 정리

AVL Tree의 Insertion, Remove 시 동작

Insertion

- 기본적으로 BST의 Insertion 방식을 사용하고, 어떤 노드의 자식 노드들의 height 값의 차가 1보다 커지면 Trinode Restructuring 을 수행한다.

1. Insert된 노드부터 부모 노드를 찾아가면서 균형이 깨진 노드를 찾는다.
2. 찾으면, 현재 경로까지 노드 중 최근 3 가지 노드를 선택한다.
(밑에서부터 x, y, z 로 놓는다.)
3. Inorder 순서로 a, b, c 로 놓는다.

총 4가지 경우의 Rotation이 있다.

1) 왼쪽 Single Rotation
트리의 왼쪽에서 b = y -> 트리가 일렬로 있을 때

Y 노드를 잡고 올려주는 모습이다.
그림에는 나오지 않았지만 당연히 Z의 부모 노드는 Y의 부모 노드가 된다.

2) 왼쪽 Double Rotation
트리의 왼쪽에서 b = x -> 트리가 한 번 꺾일 때

X 노드를 잡고 Y 와 Z 사이로 올리는 모습이다.
마찬가지로 Z의 부모 노드가 X의 부모 노드가 된다.

3) 오른쪽 Single Rotation
트리의 오른쪽에서 b = y -> 트리가 일렬로 있을 때

왼쪽일 때에서 In-order의 순서만 바뀌고 거의 유사하다.

4) 오른쪽 Double Rotation
트리의 오른쪽에서 b = x -> 트리가 한 번 꺾일 때

왼쪽일 때에서 In-order의 순서만 바뀌고 거의 유사하다.

Deletion

- Insertion과 마찬가지의 조건에서 Trinode Restructuring을 수행한다. 단, 한 번 수행해도 더 위의 노드가 균형이 깨질 수 있으므로 균형이 깨진 노드를 찾지 못 할 때까지 Restructuring을 수행해야 한다.

1. Delete된 노드부터 부모 노드를 찾아가면서 균형이 깨진 노드를 찾는다.
2. 찾으면, 올라온 반대 방향 으로 3칸 내려간다.
(밑에서부터 x, y, z 로 놓는다.)
3. Inorder 순서로 a, b, c 로 놓는다.

4. Insertion과 동일하게 수행.

처음엔 노드의 이동을 글로만 이해하려 했는데, 확실히 그림을 그려보는게 이해에 도움이 훨씬 잘 되는 것 같다.