-
AVL 트리의 회전
레드 블랙 트리의 회전의 경우 자식 노드를 신경 써서 옮겨줘야 했으나 AVL 트리의 회전은 균형이 무너진 경우 진행하게 되므로 자식 노드가 존재하지 않는 상황에 진행된다.
이때, BF가 무너진 노드를 x, x의 자식을 c, c의 자식을 c²라 하면 회전이 필요한 경우는 다음과 같이 구분된다.
- c가 x의 왼쪽 자식이고, c²가 c의 왼쪽 자식인 경우(LL) x를 오른쪽 회전
- c가 x의 오른쪽 자식이고, c²가 c의 오른쪽 자식인 경우(RR) x를 왼쪽 회전
- c가 x의 왼쪽 자식이고, c²가 c의 오른쪽 자식인 경우(LR) c를 오른쪽 회전 후 x를 왼쪽 회전
- c가 x의 오른쪽 자식이고, c²가 c의 왼쪽 자식인 경우(RL) c를 왼쪽 회전 후 x를 오른쪽 회전
AVL 트리 회전 예제 ※ AVL 트리의 회전 명칭은 삽입, 제거된 노드에서부터 BF를 조사하며 발생하므로 아래에서부터 위로 이름을 붙인다.
