들어가기 전에
트리에서 불균형이 일어났을 때 회전을 사용하여 해결하는 방법에 대해 알아보겠습니다.
학습 목표
트리의 회전을 코드로 구현할 수 있습니다.
핵심 단어
- 트리
- 균형
- 회전
강의 듣기
1-16. 트리:회전(코딩)
트리:회전 (코딩)
다음과 같이 임시 포인터를 사용하여 좌측 회전, 우측 회전을 구현합니다.
// 좌측 회전: 조부모 노드를 부모 노드의 왼쪽 자식 노드 위치로 옮깁니다.
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);
}
생각해보기
1) 임시 포인터 tmp를 사용하는 이유는 무엇인가요?
comment
leftRotate, rightRotate에는 node.parent와 tmp 간의 관계를 수정하지 않는 문제점이 있습니다
Rotate에 노드를 넣어 실행하게 되면 Node와 tmp의 위치는 바뀌고 tmp를 기존의 Node 자리에 재배정하게 되지만,
Node에게 parent가 있었다면 node.parent는 아직도 node를 가리키고 있습니다 (Node class에 parent 포인터가 없어도)
따라서 node.parent가 tmp를 자식으로서 가리키게 만들어야 하는데
이는 Node class에서 parent 포인터를 사용하지 않으면 복잡해집니다 (node.parent를 찾기위해 root부터 다시 내려와야함)
Node class에서 parent 포인터를 사용한다고 할때 코드를 이렇게 짤 수 있을것 같습니다
public Node<E> leftRotate(Node<E> node)
Node<E> tmp = node.right;
if tmp == null // 어쩌다 오른쪽 자식이 없는데 회전을 시도하게되는 경우를 다뤄줍니다
---return node;
node.right = tmp.left;
if node.right != null // tmp에게서 null이 아닌 노드를 물려받음, 그 노드의 부모를 변경해줘야 함
---node.right.parent = node;
tmp.left = node;
tmp.parent = node.parent; // tmp의 부모를 node의 부모로 변경합니다. null이어도 괜찮습니다
if node.parent != null // node.parent가 null이면 tmp가 root가 되므로 스킵해야합니다
---if node.parent.left == node // node가 부모의 왼쪽 자식인지 확인, 주소 비교로 가능
------node.parent.left = tmp; // node.parent가 기존의 node 대신 tmp를 가리킴
---else
------node.parent.right = tmp;
else // node.parent 가 null 이므로 root 입니다, root를 업데이트 해줍니다
---root = tmp;
node.parent = tmp; // 이제 node.parent를 tmp로 업데이트 해줘도 순서상 문제가 없습니다
return tmp;