AVL 트리의 회전

먼저 두 노드를 회전시킨다는 건 두 노드의 높이를 서로 바꾸는 것을 의미한다. 그냥 잡아 피는 게 아니라 노드의 부모자식관계를 역전시켜야 한다.

 

일직선 불균형, 꺽쇠 불균형은 단지 내가 분류하려고 붙인 것일 뿐 정식 명칭은 아니다. 본래 왼쪽 자식의 왼쪽 서브트리에서 불균형이 발생하면 LL 유형 오른쪽 자식의 왼쪽 서브트리에서 불균형이 발생하면 RL유형과 같이 말한다.

 

오른쪽 회전, 왼쪽 회전이 헷갈린다면 그냥 시계방향(오른쪽 회전) 반시계방향(왼쪽 회전)으로 이해하면 좀 낫다.

 

 

1. 일직선 불균형(RR,  LL유형)

불균형이 생긴 서브트리의 반대 방향으로 회전한다.

왼쪽 자식의 왼쪽 서브트리에서 불균형이 발생하면 오른쪽(시계방향)으로 회전(LL유형)

오른쪽 자식의 오른쪽 서브트리에서 불균형이 발생하면 왼쪽(반시계방향)으로 회전(RR유형)

 

왼쪽 자식의 서브트리에서 불균형이 발생했으므로 오른쪽(시계방향) 회전한다.

 

 

 

2. 꺽쇠 불균형(RL, LR유형)

a. 자식 노드를 불균형이 발생한 방향으로 회전시켜 일직선 노드를 만든다.

왼쪽에서 불균형이 발생했으므로 자식노드를 왼쪽(반시계방향) 회전한다.

 

 

 

b. 일직선 불균형이 됐으므로 부모노드를 반대 방향으로 회전시킨다.

부모 노드를 오른쪽(시계방향) 회전한다.