[자료구조] Binary Tree(이진트리)

Binary Tree

특징

• root 라는 특별한 노드가 존재
• 오직 왼쪽 / 오른쪽 두가지 child node만 가질 수 있음
• 각 node는 정확히 1개의 부모 node를 갖음

트리의 깊이 : leaf node 중 가장 깊은 node의 깊이

 

Full Binary tree(정 이진트리)

모든 leaf node가 같은 깊이를 갖으면서, 모든 잎이 아닌 node가 2개의 자손이 있는 것

대략 이런 모습이다

Complete Binary Tree (완전 이진 트리)

가능한 먼 노드들을 왼쪽부터 채워나가는 이진 트리

위와 같은 순서로 채워지는 트리이다

Array representation of Complete Binary Tree

완전 이진트리는 배열을 이용해서 구현할 수 있다.

위와 같은 형태의 완전 이진 트리가 있다고 가정해보자.

그럼 임의의 배열 arr에 아래와 같이 저장할 수 있다.

A

L

G

O

R

I

T

H

M

S

 

특정 노드 i를 가정할 때,

i의 부모 노드는 [(i-1) / 2]로 구할 수 있다.

i의 왼쪽 자식 노드는 [2i + 1]로 구할 수 있다.

i의 오른쪽 자식 노드는 [2i + 2]로 구할 수 있다.

이진트리의 삭제

이진트리의 삽입은 마지막 leaf node에 자식을 추가해주는 것으로 쉽게 만들 수 있다.

그러나 이진트리의 삭제는 약간 다르다.

leaf node의 경우는 단순하게 삭제하면 되지만, 그렇지 않은 node의 경우에는 해당 자리를 가장 깊은 level의 가장 right인 node로 대체하고 기존 right노드를 제거해주는 방식으로 구현하면 된다.

 

코드로 구현하기

class BTNode
{
    private object data;
    private BTNode left;
    private BTNode right;
}

이런식으로 생겼다고 가정해보자.

public BTNode getLeft(){ // left node 반환
	return left;
}

public BTNode getRight(){ // right node 반환
	return right;
}

public void set Data(object newData){ // 데이터 넣기
	data = newData;
}

public boolean isLeaf(){ //leaf node인지 확인
	return (left == null) && (right == null);
}

public object getLeftmostData(){
	if(left == null)
    	return data;
    else
    	return left.getLeftmostData();
}

public BTNode delNode(BTNode root, int x) {
        // 1) 기저 사례: 빈 트리면 그대로 반환
        if (root == null) {
            return null;
        }

        // 현재 노드의 키 값 (Object 타입이므로 Integer로 캐스트)
        int key = (Integer) root.getData();

        // 2) 삭제할 값이 더 작으면 왼쪽 서브트리로
        if (key > x) {
            root.setLeft(delNode(root.getLeft(), x));
        }
        // 3) 더 크면 오른쪽 서브트리로
        else if (key < x) {
            root.setRight(delNode(root.getRight(), x));
        }
        // 4) 같으면 이 노드를 삭제
        else {
            // 자식이 하나도 없거나 오른쪽만 있을 때
            if (root.getLeft() == null) {
                return root.getRight();
            }
            // 왼쪽만 있을 때
            if (root.getRight() == null) {
                return root.getLeft();
            }
            // 양쪽 자식이 모두 있을 때: 후계자 찾기
            BTNode succ = getSuccessor(root);
            // 후계자의 데이터를 복사
            root.setData(succ.getData());
            // 오른쪽 서브트리에서 후계자를 삭제
            root.setRight(delNode(root.getRight(), (Integer) succ.getData()));
        }

        return root;
    }

    // 후계자(smallest node in right subtree) 찾기
    private BTNode getSuccessor(BTNode node) {
        BTNode curr = node.getRight();
        while (curr.getLeft() != null) {
            curr = curr.getLeft();
        }
        return curr;
    }
}

이런 식으로 메소드를 구현하면 된다.

이진 트리 복사하기

트리를 그대로 복사하는 경우는 아래와 같은 과정을 거친다.

1. 왼쪽 서브 트리 카피
2. 오른쪽 서브 트리 카피
3. 새로운 트리 생성하기

코드로 표현하면 아래와 같다.

 public static BTNode treeCopy(BTNode source)
 {
 	BTNode leftcopy, rightcopy;
 	if (source == null)
 		return null;
 	else
 	{
 		leftCopy = treeCopy(source.left);
 		rightCopy = treeCopy(source.right);
 		return new BTNode(source.data, leftCopy, rightCopy);
 	}
}

트리 순회하기

• Pre-order traversal
  1. root node부터 시작
  2. 왼쪽 서브 트리로 재귀 호출
  3. 오른쪽 서브 트리로 재귀 호출

위 사진과 같은 순서로 root에서 시작해서 순회한다.

• In-order traversal
  1. 왼쪽 서브 트리로 재귀 호출(위로 올라감)
  2. root node 방문
  3. 오른쪽 서브 트리로 재귀 호출(위로 올라감)

위 사진과 같은 순서로 맨 왼쪽 leaf node부터 맨 오른쪽 leaf node로 순회한다.

• Post-order traversal
  1. 왼쪽 서브트리로 재귀 호출(위로)
  2. 오른쪽 서브트리로 재귀 호출(위로)
  3. root 방문

위 사진처럼 왼쪽, 오른쪽, root 순으로 순회한다.