AVL 삽입, 삭제

특징

트리의 모든 노드들은 오른쪽, 왼쪽 서브트리의 높이 차이를 {-1, 0, 1} 중 하나를 가짐

50에서 살펴 본다면 왼쪽은 높이가 1 오른쪽은 높이가 2로 둘의 차이는 -1을 가진다.

노드 추가, 삭제 후 조건을 만족시키지 않는다면, 균형을 맞추는 작업을 진행한다.

 

노드 하나 씩 검사하며 만족하지 않는 노드가 발생한다면, 해당 노드에서 작업을 수행하면 된다.

모든 노드들이 조건을 만족한다.

만족하지 않는 경우

70에서 만족하지 않으므로 70을 기준으로 오른쪽 회전을 한다.

60은 70이 원래 자신의 왼쪽 자식이 있었지만 비게 되었으므로 60을 70의 왼쪽 자녀로 해준다.

노드의 삭제에서
2번의 단계가 필요한 경우

아래와 같은 경우 노랜 색만 집중을 해보면 60이 루트로 가야 완전 이진트리가 된다.

1단계

70을 기준으로 오른쪽으로 회전해 60을 70자리로 올려준다.

2단계

50을 기준으로 왼쪽 회전을 한다.

이러면 완전 이진트리가 완성된다.

루트 삭제

60을 삭제하기 위해 65와 교체를 한 후 삭제를 하고 AVL이 맞게 수정해 주면 된다.