회전
트리의 구조가 변경될 때 AVL 트리의 속성을 유지하려면 트리를 수정해야 합니다. 이때, 단순 회전(single rotation)이나 이중 회전(double rotation)에 의해 수행됩니다.
만일 AVL 트리의 속성이 노드 x에서 위배되었다면, 이는 left의 높이와 right의 높이 차이가 정확히 2라는 뜻
회전은 AVL 트리의 속성을 회복시키기 위한 기법이므로, 노드 x에 회전을 적용하여 트리를 수정할 수 있다.
-
삽입연산 이후 삽입 지점으로 루트에 이르는 경로의 노드들의 서브 트리만 변경되었으므로 이 노드들만 찾으면 됩니다.
-
위반되는 경우
LL : 왼쪽 자식의 왼쪽 서브트리에 노드가 삽입된 경우
LR : 왼쪽 자식의 오른쪽 서브트리에 노드가 삽입된 경우
RL : 오른쪽 자식의 왼쪽 서브트리에 노드가 삽입된 경우
RR : 오른쪽 자식의 오른쪽 서브트리에 노드가 삽입된 경우
-
단순회전
LL의 경우
RR의 경우
-
이중회전
LR의 경우
RL의 경우
