[TIL] 자료구조 - 트리:회전 소개

※ 트리: 회전 소개

- 균형 잡힌 트리를 만들기 위해 트리의 노드 위치를 바꾸는 과정을 회전이라고 한다.

 

연결 리스트처럼 한 방향으로 나열된 트리는 균형 잡혀 있지 않다고 표현을 하는데 균현 잡힌 트리에서는 특정 요소를 탐색하는 시간 복잡도가 O(logn) 이지만 균형 잡히지 않은 트리에서는 연결 리스트와 같은 O(n)이 된다. 따라서, 데이터를 효율적으로 관리하기 위해서는 트리를 균형 있게 만드는 것이 중요하다.

 

조부모 노드, 부모 노드, 자식 노드의 크기 관계에 따라 우측 회전이나 좌측 회전을 한다. 트리를 재정렬하면 항상 중간 크기의 요소가 가장 상단에 있는 루트가 된다.

 

1. 불균형이 좌측 서브트리에서 나타나는 경우

- 크기 관계는 (조부모 노드) > (부모 노드) > (자식 노드)이다. 우측 회전을 하여 조부모 노드를 부모 노드의 우측 자식 노드 위치로 옮겨준다.

 

2. 불균형이 우측 서브트리에서 나타나는 경우

- 크기 관계는 (조부모 노드) < (부모 노드) < (자식 노드)이다. 좌측 회전을 하여 조부모 노드를 부모 노드의 좌측 자식 노드 위치로 옮겨준다.