Java-자료구조 5주차 Tree 4 - 14 ~ 16

5주차-Tree
4-14.트리:회전

• '회전'이란?
  -균형 잡힌 트리를 만들기 위해 트리의 노드 위치를 바꾸는 과정

균형 잡힌 트리란?
==> 연결리스트처럼 한 방향으로 나열된 트리가 아닌 모양으로 데이터가 추가된 상태
ex)균형 잡힌 트리

ex)균형잡지 않은 트리

• 왜 회전을 해야 하는가?
  :시간복잡도가 균형잡지 않은 트리보다 균형잡은 트리가 빠르다
  +) 균형잡힌 트리(O(logn)) < 균형 잡히지 않은 트리(O(n))

• 균형 잡힌 트리를 만드는 이유 -> 효율적인 데이터 관리

종류) 우측/좌측 회전
분류 기준: 조부모, 부모, 자식 노드의 크기 관계
(1) 우측 회전
:불균형이 왼쪽 서브트리에 나타나는 경우

크기 관계) 조부모 > 부모 > 자식
우측 회전 결과) 조부모 => 부모의 right child

(2) 좌측 회전
:불균형이 오른쪽 서브트리에 나타나는 경우

크기 관계) 자식 > 부모 > 조부모
좌측 회전 결과) 조부모 => 부모의 left child

• 두 회전 모두 부모 노드가 해당 노드의 중간 부분이 된다(여기서는 루트)
• 회전의 원인: 자식 노드(node caused imbalance)

생각해보기)- 회전을 하기 위한 조건은 무엇인가요?
답: 균형 잡히지 않은 트리를 만드는 데 필요한 조건으로 추가하는 데이터가 지속적으로 증가하거나 감소하는 형태 시 회전이 일어난다

4-15. 트리:회전(심화)

• 트리가 치우치지 않았다면?
  :우측 회전과 좌측 회전 모두 사용

(1) 불균형이 right child의 왼쪽 서브 트리에서 나타나는 경우

크기 관계) 부모 > 자식 > 조부모
회전 결과) 조부모 => 부모의 left child
진행 과정)

(2) 불균형이 left child의 오른쪽 서브 트리에서 나타나는 경우

크기 관계) 부모 > 조부모 > 자식
회전 결과) 조부모 => 부모의 right child
진행 과정)

생각해보기)-위 사진에서 트리를 재정렬하면 어떤 요소가 루트가 되나요?
:부모

4-16.트리:회전(구현)

• 코드 구현 시, 임시 포인터를 사용하여 좌측/우측 회전 구현!
  +) 입력 노드 : 회전 될 노드

<좌측 회전>

// 좌측 회전: 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮깁니다.
public Node<E> leftRotate (Node<E> node){ // 입력노드: 조부모
	Node<E> tmp = node.right; // temp는 grandparents right child(parent)를 가리킨다
	node.right = tmp.left; // grandparents right child은 temp left child를 가리킨다
	tmp.left = node; // temp left child에 grandparent을 둔다 
	return tmp; // 임시포인터인 temp반환
}

temp라는 임시포인터는 조부모 노드 대신 사용된다
위 코드 형상화)

<우측 회전>

// 우측 회전: 조부모 노드를 부모 노드의 오른쪽 자식 노드 위치로 옮깁니다. 
public Node<E> leftRotate (Node<E> node){ // 입력노드: 조부모
	Node<E> tmp = node.left; // temp가 조부모의 left child를 가리킴
	node.left = tmp.right; // 실제 조부모의 left child는 temp의 right child를 가리킨다  
	tmp.right = node;  // temp의 right child가 조부모를 가리킨다
	return tmp;
}

위 코드 형상화)

<모든 회전을 사용하는 코드>
입력 노드는 부모 노드가 된다
(1) 우측 회전 -> 좌측 회전

// 우측 회전 후 좌측 회전
public Node<E> rightLeftRotate(Node<E> node){ 
	node.right = rightRotate(node.right);
	return leftRotate(node);
}

(2) 좌측 회전 -> 우측 회전

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

• 결과 -> 임시 변수가 반환되면서 새로운 부모 노드가 생기는 것!

생각해보기)- 임시 포인터 tmp를 사용하는 이유는 무엇인가요?
답: 해당 노드를 임시 포인터로 연결하지 않으면 연결할 수 없어서