TIL 정리_89

트리의 회전 

이진 트리의 시간 복잡도는 O(log n)이고 한쪽으로 치우친 트리는 O(n)이다
-> 이 차이점을 균형이라고 한다 //균형잡힌 트리
->데이터를 효율적으로 관리하기 위해서 균형있는 트리를 만들어야 한다 
트리는 최대한 균형 잡히게 만들기 위해서는 숫자들이 정렬되어있어야 한다

균형잡힌 트리를 만들기 위해 트리의 노드 위치를 변경하는 것을 회전이라고 한다

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

 

 

회전 방법 

• 불균형이 왼쪽 서브트리에서 나타나는 경우
  크기 관계는 조부모 노드 > 부모 노드 > 자식 노드이다 
  우측 회전을 하여 조부모 노드를 오른쪽 자식 노드의 위치로 옮긴다

 

• 불균형이 오른쪽 서브트리에서 나타난 경우
  크기 관계는 조부모 노드 < 부모 노드 < 자식 노드이다 
  좌측 회전을 하여 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮긴다

 

• 트리가 한쪽으로 치우치지 않은 경우 
  우측 회전과 좌측 회전을 모두 사용하여 불균형을 해소한다

 

 

불균형이 오른쪽 자식의 왼쪽 서브 트리에서 나타날 경우

크기 관계는 부모 노드 > 자식 노드 > 조부모 노드이다
자식 노드에 대해 부모 노드를 우측 회전 -> 좌측 회전을 하여 
조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮긴다

 

 

불균형이 왼쪽 자식의 오른쪽 서브 트리에서 나타날 경우

크기 관계는 부모노드 > 조부모 노드 > 자식 노드이다
자식 노드에 대해 부모 노드를 좌측 회전 -> 우측 회전을 하여 
조부모 노드를 부모 노드의 오른쪽 자식 노드 위치로 옮긴다

 

트리의 회전을 코드로 구현

 

좌측 회전 코드 

set temp = grandparents right child //임시 포인터 생성
set grandparents right child = temp left child
set temp left child = grandparent
-> 조부모 노드 대신 임시 포인터를 사용한다 
조부모 노드 -> 부모 노드의 왼쪽 자식 노드 위치로 이동

public Node<E> left Rotate(Node<E> node) {
Node<E> tmp = node.right;
node.right = tmp.left;
tmp.left = node;
return tmp;
}

 

우측 회전 코드

set temp = grandparents left child
grandparents left child = temp right child
set temp right child = grandparent
조부모 노드 -> 부모 노드의 오른쪽 자식 노드 위치로 이동 

public Node<E> right Rotate(Node<E> node) {
Node<E> tmp = node.left;
node.left = tmp.right;
tmp.right = node;
return tmp;
}

트리가 한쪽으로 치우치지 않은 경우 

//알맞은 노드를 가지고 좌측, 우측 회전을 호출
public Node<E> rightLeftRotate(Node<E> node) {
node.right = rightRotate(node.right); 
return leftRotate(node);
} //우측 -> 좌측 회전

public Node<E> leftRightRotate(Node<E> node) {
node.left = leftRotate(node.left);
return rightRotate(node);
} //좌측 -> 우측 회전