[자바로 구현하고 배우는 자료구조] 4. 힙(Heap) & 트리(Tree) (4)

---

4-12. 트리:Contains

contain 메소드를 이용하여 트리에 찾고자 하는 요소가 있는지 확인할 수 있다.

public boolean contains(E obj){
	return contains(obj, root);
}

public boolean contains(E obj, Node<E> node){
	// node가 null이면 false를 반환한다.
	if(node == null){
    	return false;
    }
    // obj와 node.data가 같으면 true를 반환한다.
    if(((Comparable<E> obj).compareTo(node.data))==0){
    	return true;
    }
    // 비교하는 값이 node값보다 작아 오른쪽 노드로 이동하여 비교한다.
    if(((Comparable<E> obj).compareTo(node.data))>0){
    	return contains(obj, node.right);
    }
    // 조건에 해당하지 않으므로 왼쪽 노드로 이동하여 비교한다.
    return contains(obj, node.left);
}

 

4-13. 트리:제거

위 트리에서 노드 15를 제거하기 위해서 다음의 과정을 거쳐야 한다. 먼저 15노드의 왼쪽 포인터를 null로 설정한다. 그리고 15의 부모 노드인 10의 오른쪽 포인터를 15가 아니라 12를 가리키도록 설정한다.

 

 만약 위 트리의 15처럼 자식 노드가 하나가 아니라 두 개인 경우, 각 노드의 크기를 비교하여 부모가 왼쪽 자식의 노드보다 크고, 오른쪽 자식 노드보다 작은 규칙을 지켜야 한다.

 

4-14. 트리:회전 소개

위 숫자 배열로 트리를 만든다고 가정해보자. 왼쪽 아래 트리처럼 균형있는 트리는 O(log n)의 시간복잡도를 갖지만 오른쪽 아래 트리처럼 불균형할 경우 O(n)의 시간 복잡도를 갖는다. 이 경우 비효율적이므로 회전을 이용하면 왼쪽 아래의 트리처럼 균형잡힌 트리로 바꿀 수 있다.

위의 두 그림은 각각 서브트리가 왼쪽으로 치우쳐진 경우와 오른쪽으로 치우쳐진 경우이다. 왼쪽으로 치우쳐진 노드는 중간의 부모 노드를 기준으로 조부모 노드를 오른쪽 회전시키고, 오른족으로 치우쳐진 노드는 부모노드를 기준으로 조부모 노드를 왼쪽으로 회전시킨다. 

 

 

4-15. 트리:회전

트리 회전 소개에서 본 두 트리는 모두 한쪽 방향으로 치우쳐진 트리이다. 하지만 위 두 서브트리처럼 한쪽으로 치우쳐진 게 아니라 부모노드가 불균형을 이루고 있다면? 이 경우 한쪽으로 치우쳐진 트리로 만들고, 그 다음 왼쪽 회전이나 오른쪽 회전을 해준다. 첫 번째의 경우, 4의 오른쪽 포인터를 6을 가리키게 하고, 8의 왼쪽 포인터를 null을 가리키게 한다. 그리고 마지막으로 6의 오른쪽 포인터가 8을 가리케가 하면 된다. 이렇게 오른쪽 회전을 한 다음 왼쪽 회전을 해주면 균형있는 트리로 바꿀 수 있다.

 

4-16. 트리:회전(코딩)

회전을 코드로 작성할 때, 왼쪽 회전과 오른쪽 회전, 오른쪽-왼쪽 회전과 왼쪽-오른쪽 회전 네가지 메소드를 모드 작성해야 한다.

public Node<E> leftRoatate(Node<E> node){
	Node<E> temp = node.right;
    node.right = temp.left;
    temp.left = node;
    return temp;
}
public Node<E> rightRoatate(Node<E> node){
	Node<E> temp = node.left;
    node.left = temp.right;
    temp.right = node;
    return temp;
}
public Node<E> rightLeftRoatate(Node<E> node){
	node.right = rightRotate(node.right);
    return leftRotate(node);
}
public Node<E> leftRightRoatate(Node<E> node){
	node.left = leftRotate(node.left);
    return rightRotate(node);
}

 

---

오늘의 교훈: 미리미리 정리 안하면 몰아서 정리하느라 죽는다.