Tree rotation

[ 출처 : https://en.wikipedia.org/wiki/Tree_rotation ]

 

- left subtree가 더 무거울 때 right rotation을 해준다.

- right subtree가 더 무거울 때 left rotation을 해준다.

 

Example : rotate left

1에서 imbalance가 발생했다고 해보자.

또, imbalance의 원인이 3 혹은 3의 subtree에 있다고 해보자.

 

1을 기준으로 left rotation을 해준다. (즉, 1-2-3 덩어리를 왼쪽으로 한 칸 민다)

 

imbalance가 해소되었다.

 

 

Example :  rotate right-left

1에서 imbalance가 발생했다고 해보자.

또, imbalance의 원인이 2 혹은 2의 subtree에 있다고 해보자.

 

z : imbalance가 발생한 위치

y : z.right

x : y.left

 

로 정의하자.

 

x가 z로부터 right-left 위치에 있으므로 rotateRight(y), rotateLeft(z) 를 해야한다.

 

이렇게 하면 imbalance가 해소되는지 한 번 확인해보자. 

 

먼저 3을 기준으로 right rotation을 해준다. (즉, 2-3 덩어리를 오른쪽으로 한 칸 민다)

 

다음으로 1을 기준으로 left rotation을 해준다. (즉, 1-2-3 덩어리를 왼쪽으로 한 칸 민다)

 

imbalance가 해소되었다.