[트리] 트리의 회전 - 이론

트리의 좋은 모습은 "균형 잡힌" 트리이다.

"균형 잡혔다"는 뜻은 자식 노드가 한쪽 방향으로 치우치지 않고 깊이가 비슷한 상황을 이야기한다.

 

이진 탐색 트리에서 삽입된 노드가 균형을 깨뜨리는 경우가 발생한다. 그럴 때 우리는 트리를 회전 시켜줘야한다.

 

회전에서 Left 회전과 Right 회전이 있다.

오른쪽 자식의 오른쪽 sub 트리가 문제일 때 : L회전

왼쪽 자식의 왼쪽 sub 트리가 문제일 때 : R회전

 

L회전은 오른쪽 자식을 부모 노드로 하고 부모 노드를 자식의 왼쪽 자식으로 편입하는 것이다.

R회전은 반대로 왼쪽 자식을 부모 노드로 하고 부모 노드를 자식의 오른쪽 자식으로 편입하는 것이다.

 

이번에는 조금 더 복잡한 경우를 보자.

 

오른쪽 자식의 왼쪽 sub 트리가 문제일 때 : RL회전

왼쪽 자식의 오른쪽 sub 트리가 문제일 때 : LR회전

 

한번 꺽이는 형태의 트리는 두번의 회전을 해줘야한다. 펴주는 과정이 필요하고, 펴준것을 회전시키는 것입니다.

 

이상 트리의 회전을 알아보았습니다.

다음에 코드로 이 회전을 구현하는 것을 해보겠습니다.