[TIL] 자료구조 - 트리:회전(2)

※ 트리:회전

- 다음과 같이 임시 포인터를 사용해 좌측 회전, 우측 회전 구현한다

// 좌측 회전: 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮깁니다.
public Node<E> leftRotate (Node<E> node){
	Node<E> tmp = node.right; // set temp=grandparents right child
	node.right = tmp.left; // set grandparents right child=temp left child
	tmp.left = node; // set temp left child=grandparent 
	return tmp; // use temp instead of grandparent
}

// 우측 회전: 조부모 노드를 부모 노드의 오른쪽 자식 노드 위치로 옮깁니다.
public Node<E> leftRotate (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);
}