Binary Tree(이진 트리), Binary Search Tree(이진탐색트리)

1. Binary Tree

1-1. 정의

유한개의 노드로 이루어진 트리이다.

이진 트리는 root(노드)와 그와 이어진 두개의 이진트리들로 구성된다.(이를 각각 left, right subtree로 칭한다.)

 

1-2. 용어

(1) node : 이진 트리를 구성하는 단위 value를 저장하는 공간과 왼쪽과 오른쪽을 노드를 가르치는 포인터로 구성된다.

(2) children : root 노드의 왼쪽과 오른쪽이 가리키는 node를 child라 한다.

(3) edge : root들을 잇는 선분

(4) ancestor : children의 반대

(5) descendant : 밑의 노드들

(6) path : 이웃하는 두 노드가 앞이 부모, 뒤가 자식인 노드의 열

(7) level(=depth) : 루트 노드에서 자신까지 가는 경로의 길이. root node의 depth는 0, level은 1. level = depth + 1

(8) size : 자기 자신 및 모든 자손 노드의 수

(9) leaf node : 차수가 0인 노드, 자식이 없는 노드

(10) internal node : 자식이 있는 노드

 

1-3. Full Binary Tree

각각의 노드가 leaf node거나 자식이 두개인 internal node로 이루어진 tree

1-4. Complete Binary Tree

1) 맨 끝 level을 제외하고 모든 노드가 completely full한 경우.(모든 노드가 좌우 자식트리가 꽉찬 internal node)

2) 가장 바닥 레벨의 노드는 왼쪽으로 치우쳐져있는 경우

Complete Binary Tree

1-5. Full Binary Tree Theorem

Full BT에서 leaf node의 개수는 internal node의 개수보다 하나 더 많다.

 

Proof (by mathematical induction) :

1) when # of internal node = 1,

1 internal node must have two leaf nodes

2) when # of internal node = n-1 holds, # of internal node = n

 n개의 # of internal nodes를 가진 BT를 T라고 칭할 때, 2개의 leaf 노드를 가진 internal node 하나를 없애보자. 해당 이진트리 T'는

귀납법의 가정에 따라 n개의 leaf 노드를 가진다.

이때 없앤 internal node를 다시 복원시키면 internal node + 1, leaf node + 2가 되어 여전히 둘의 차이는 1이 된다.

 

1-6. Full Binary Tree Corollary

BT node의 빈 포인터의 개수는 node 총 갯수보다 하나 많다.

 

null pointer를 모두 채우면 Full Binary Tree와 같아지고,

Null pointer는 leaf node로 바뀌고, 원래 있었던 node들은 internal node로 바뀌는 것을 알 수 있다.

 

1-7. Traversal

BT에서 node를 방문하는 순서를 traversal(탐색)이라 한다.

 

각각의 노드를 한 번씩만 방문하고 순서를 매기는 과정이라고도 칭한다.

 

모든 traversal은 재귀적으로 정의된다.

 

1) preorder traversal

: root node - left subtree - right subtree

 

2) postorder traversal(calculator)

: left subtree- right subtree - root node

 

postorder traversal로 표현한 계산

 

3) In-order traversal(Sorting in BST)

: left subtree- root node - right node

 

2. Binary Search Tree

2-1. Link-based BST 구현

함수들은 재귀함수의 형태로 구현이 가능하다.

 

int count(Node rt){
	if (rt == null) return 0;
	return 1 + count(rt.left) + count(rt.right);
}

node에 구현에 있어서

 

(1) leaf node가 internal node와 같은 경우

(2) internal node와 leaf node가 다른 경우

 

로 나누어지게 된다.

 

2-2. Space overhead

전체 메모리 사용 공간 대비 데이터 메모리가 아닌 사용 공간을 의미한다.

 

(non data space) / (total space)

 

the Full Binary Tree Theorem에서부터

pointer의 절반은 null인 것을 알 수 있다. (null pointer == # of nodes + 1)

 

만약 leaf node에서만 데이터를 저장한다면 overhead는 tree가 full인지의 여부에 따라 overhead가 달라지게 된다.

 

Space Overhead의 계산 예시

 

full tree, node가 왼쪽, 오른쪽 자식 노드를 가리키는 포인터, 데이터를 가르키는 포인터를 가지고 있는 경우

 

- Total space required is (3p+d)n

- Overhead space: 3pn

if p = d, overhead = 3/4

 

여기서 leaf node의 자식을 가리키는 포인터를 없앤다면,

full tree이기 때문에 leaf node는 전체 node의 절반이다. (정확하게는 n+1/(2n+1))

 

(n/2)2p + np / (n/2)2p + np + dn = 2p / 2p + d

if p = d, space overhead = 2/3

 

2-3. Binary Search Tree

: 모든 element들이 root node의 element를 기준으로 작을 경우 왼쪽 subtree에, 크거나 같을 경우 오른쪽 subtree에 위치하게 정렬된 경우를 뜻한다.

 

내부의 함수들 또한 재귀적으로 정의가 가능하다.

 

public void insert(K k, E e){
	Node root = inserthelp(root, k, e);
    nodecount++;
}

private Node inserthelp(Node rt, K k, E e){
	if(rt == null) return new Node<K, E>(k, e);
    if(rt.key.compareTo(k) > 0)
    	rt.setLeft(inserthelp(rt.left(), k, e));
    else
    	rt.setRight(inserthelp(rt.right(), k, e));
    return rt;
}

 

BST의 경우 node를 삭제하는 과정이 tricky한데,

 

1) 삭제를 원하는 key 값을 가진 Node를 찾고,

2) 그의 오른쪽 subtree에 있는 요소들 중 최솟값을 찾은 후

3) 삭제를 원하는 node에 해당 값을 치환해준다.

4) 원래 최솟값 node는 삭제해준다.

 

이를 코드로 적으면

 

public E remove(K k){
	E temp = findhelp(root, k);
    if(temp != null){
    	root = removehelp(root, k);
        nodecount--;
    }
    return temp;
}

private E findhelp(Node rt, K k){
	if(rt == null)
    	return null;
    if(rt.key().compareTo(k) > 0)
    	return findhelp(rt.left(), k);
    else if(rt.key().compareTo(k) < 0)
    	return findhelp(rt.right(), k);
   	else
    	return rt.element();
}

private Node getmin(Node rt){
	if(rt.left() == null)
    	return rt;
    else return getmin(rt.left());
}

private Node deletemin(Node rt){
	if(rt.left() == null) return rt.right();
    else{
    	rt.setLeft(deletemin(rt.left()));
    }
    return rt;
}

private Node removehelp(Node rt){
	if(rt == null) return null;
    if(rt.key().compareTo(k) > 0){
    	rt.setLeft(removehelp(rt.left(), k));
    }
    else if(rt.key().compareTo(k) < 0)
    	rt.setRight(removehelp(rt.right(), k));
    else{
    	if(rt.left() == null)
        	return rt.right();
        else if(rt.right() == null)
        	return rt.left();
        else{
        	Node tmp = getmin(rt.right());
            rt.setElement(tmp.element());
            rt.setKey(tmp.key());
            rt.setRight(deletemin(rt.right()));
        }
    }
    return rt;
}

2-4. 시간복잡도

(1) Find : O(d)

 

(2) Insert : O(d)

 

(3) delete : O(d)

 

d = depth of the tree => balanced한 경우에는 d가 O(log n)으로 주어진다.

worst case엔 depth가 n이 된다.

 

2-5. Array를 이용한 구현

 

complete binary tree의 경우,

 

각각의 node 번호를 index로 하여 parent, left child, right child, left sibling, right sibling을 저장하는 array로 구현할 수도 있다.

 

 

 

array로 구현한 complete binary tree

r is position of node

 

parent(r) = Floor$(\frac{r-1}{2})$, if r != 0

LeftChild(r) = 2r+1, if 2r+1 < n

RightChild(r) = 2r+2, if 2r+2 < n

LeftSibling(r) = r - 1, if r is even && r != 0

RightSibling(r) = r + 1, if r is odd && r + 1 < n

 

r이 0일 때가 root node!

 

2-6. Inorder Traversal

BST에서 Inorder Traversal을 하면 Sorted Value를 얻을 수 있다!