트리 회전시키기

균형잡히지 않은 트리

균형잡히지 않은 트리

위와 같이 한 방향으로 나열된 트리를 균형 잡히지 않은 트리 라고 합니다.

일반적인 트리는 시간복잡도가 O(logN) 이지만

균형 잡히지 않는 트리는 시간복잡도가 O(N) 입니다.

따라서 트리를 사용하는 데 있어서 비효율이 발생합니다.

 

왼쪽으로 돌리기

public void rotateLeft(Node x){
	//일단 돌리자
	Node y = x.right;
	x.right = y.left;
	
	
	//y입장에서 parent 정리
	if(y.left != null) y.left.parent = x;
	y.parent = x.parent;
	
	//x입장에서 parent 정리
	if(x.parent == null){
		root = y;
	}
	else if(x == x.parent.left){
		x.parent.left = y;
	}
	else{
		x.parent.right = y;
	}
	
	y.left = x;
	x.parent = y;
	
}

코드로만 보면 이해하기 힘드니 그림으로 설명 하겠습니다.

 

 

일단 돌리자

불균형 트리

위 그림과 같이 불균형한 트리가있다고 가정합시다.

위 트리를 왼쪽으로회전시켜 균형을 맞춰 보려고 합니다.

 

가장 먼저 위 트리를 두개로 나누는 것 부터 해봅시다.

 

  위 그림에 x표 해놓은 곳을 잘라서 두개의 트리로 나누어 봅시다.

 

트리를 왼쪽으로 돌린다는 의미는 y밑으로 x가 들어간다는 의미입니다.

하지만 y의 자식은 포화 상태 이므로 y의 자식하나를 x쪽 트리로 전달해야합니다.

y는 x보다큰 수의 집합입니다,

따라서 y보다작은 수들의 집합을 x의 오른쪽으로 붙이면 y의 자식하나를 x로 전달할 수있습니다.

 

 

위의 작업이 아래 코드와 같습니다.

//일단 돌리자
	Node y = x.right;
	x.right = y.left;

 

이제 해야할 작업은 두 트리의 부모를 재설정 해주는 작업입니다.

 

//y입장에서 parent 정리
	if(y.left != null) y.left.parent = x;
	y.parent = x.parent;

 

y쪽에서 전달해준 트리의 부모를 재설정 하고

y의 부모를 x의 부모로 설정해 줍니다.(x가 있던자리로 향하는 과정)

 

//x입장에서 parent 정리
	if(x.parent == null){
		root = y;
	}
	else if(x == x.parent.left){
		x.parent.left = y;
	}
	else{
		x.parent.right = y;
	}

x쪽에서도 마찬가지로 부모를 재설정 해줍니다.

마지막으로 두 트리를 합쳐주면 트리의 회전이 완료됩니다.

	y.left = x;
	x.parent = y;