트리 회전

1. 본문

트리 회전(Tree Rotation)은 이진 트리(Binary Tree)의 한 종류인 이진 탐색 트리(Binary Search Tree)의 구조를 변경하는 연산입니다. 이 연산은 트리의 균형을 유지하고, 특정 연산의 효율성을 높이기 위해 사용됩니다.
트리 회전의 핵심:

• 구조 변경: 트리 회전은 특정 노드를 기준으로, 그 노드의 위치와 부모 또는 자식 노드의 위치를 서로 바꾸는 방식으로 트리의 구조를 변경합니다.
• 순서 유지: 이진 탐색 트리의 핵심 속성인 "왼쪽 자식 노드는 부모 노드보다 작고, 오른쪽 자식 노드는 부모 노드보다 크다"는 순서는 유지됩니다. 즉, 회전 후에도 이진 탐색 트리의 속성은 그대로 유지됩니다.
• 균형 유지: 트리 회전의 주된 목적 중 하나는 트리의 균형을 맞추는 것입니다. 불균형한 트리는 탐색, 삽입, 삭제 등의 연산에서 비효율을 초래할 수 있습니다. 회전을 통해 트리의 높이를 줄이고, 더 균형 잡힌 형태로 만들 수 있습니다. (예: AVL 트리)

• 특정 노드(X)를 기준으로, 그 노드의 오른쪽 자식(Y)을 새로운 부모 노드로 만들고, X를 Y의 왼쪽 자식으로 만듭니다.
• Y의 원래 왼쪽 자식은 X의 오른쪽 자식으로 이동합니다.

• 특정 노드(X)를 기준으로, 그 노드의 왼쪽 자식(Y)을 새로운 부모 노드로 만들고, X를 Y의 오른쪽 자식으로 만듭니다.
• Y의 원래 오른쪽 자식은 X의 왼쪽 자식으로 이동합니다.

• 자가 균형 이진 탐색 트리 (Self-Balancing Binary Search Trees): AVL 트리, 레드-블랙 트리 등과 같은 자가 균형 이진 탐색 트리는 삽입 및 삭제 연산 중에 트리의 균형이 깨질 경우, 트리 회전을 사용하여 균형을 자동으로 복원합니다.
• 기타 트리 알고리즘: 트리의 균형을 유지하거나 특정 노드의 위치를 조정해야 하는 다양한 알고리즘에서 트리 회전이 활용될 수 있습니다.
• 불균형이 왼쪽 서브트리에서 나타나는 경우 우측 회전을 합니다.
• 불균형이 오른쪽 서브트리에서 나타나는 경우 좌측 회전을 합니다.