자료구조[8] Tree

Tree

용어

root 노드에서 다른 노드로 가는 길은 한 가지만 존재한다.
파일 시스템등 계층 의미가 있는 데이터를 다룰 때 tree를 사용한다.

Binary Tree

Binary(이진) tree는 자식 노드를 최대 2개만 갖는 tree를 말한다.
자식 노드가 없거나 1개 혹은 2개이면 된다.

Ancestors: 노드가 root 노드로 가는 길에 있는 모든 노드들이다.
Descendants: 한 노드의 아래쪽에 있는 모든 노드들이다.

Max nodes at level l: $2^l$
$N_{max} = 2^0 + 2^1 + 2^2 + ... + 2^{h-1} = 2^h - 1$

Max Height: N (same as linked list)
Min Height: $log(N+1)$ - from $N_{max} = 2^h - 1$ -> 트리를 꽉 채웠을 때, 높이는 $log(N+1)$

Binary Search Tree

개요

binary search tree는 findItem()에 특화되어있다.

1. 각각의 노드는 고유한 값을 갖는다.
2. 값들은 >, <로 비교한다.
3. 노드들의 왼쪽 값은 오른쪽 값보다 작아야한다.
4. 값을 insert하는 순서에 따라 모양이 달라진다.

findItem()

BST이므로 모든 노드를 탐색할 필요는 없어 보인다.

1. root에서 시작해 값을 비교하기 시작한다.
2. 노드의 값이 찾는 값보다 크면 왼쪽 subtree에서 다시 탐색을 시작한다.
3. 반대의 경우엔 오른쪽 subtree에서 탐색을 시작한다.
4. 위의 과정을 값을 찾을 때까지 반복한다.
5. 값을 찾았거나 nullptr에 도달하면 끝난다.

위 알고리즘의 시간복잡도는 어떨까?

얼핏봐서는 O(log(N))처럼 보인다. 그러나 이는 tree의 모양에 따라 다르다.
tree가 linked structure처럼 1직선이면 시간복잡도는 O(N)이 된다.
일반적인 BST모양이면 O(log(N))만큼 걸린다. 즉, 높이 h만큼 비교해야한다.

정리하자면 일반적으로는 O(log(N))이지만, 굉장히 unbalance한 상황에선 O(N)도 나올 수 있다.

정의

template<class ItemType>
struct TreeNode{
	ItemType value;
    TreeNode* left;
    TreeNode* right;
}

template<class ItemType>
class TreeType
{
private:
	TreeNode<ItemType>* root;
Public:
	TreeType();
    ~TreeType();
    TreeType(const TreeType<ItemType>&); // 복사생성자
    void operator=(const TreeType<ItemType>&);
    void clear();
    bool isFull() const;
    bool isEmpty() const;
    int length() const;
    bool findItem(ItemType& item);
    void insertItem(ItemType item);
    void deleteItem(ItemType item);
};

length()

Logical Level

길이를 구하려면 왼쪽 subtree 개수와 오른쪽 subtree개수 그리고 자기 자신을 더하면 될 것같다.
이를 recursion으로 구현해보자.

Base case: The (sub)tree is empty (length == 0)
General case: length(left) + length(right) + 1

Implementation Level

int TreeType::length() const{
	return countNodes(root);
}

int TreeType::countNodes(TreeType* tree){
	if (tree == nullptr){
    	return 0;
    }
    else {
    	return countNodes(tree->left) + countNodes(tree->right) + 1;
    }
}

finditem()

Logical Level

Base case 1: 아이템을 찾았을 때
Base case 2: 현재 tree가 nullptr일 때
General case: 왼쪽, 오른쪽 탐색

Implementation Level

bool TreeType::findItem(ItemType& item){
	return find(root, item);
}

bool TreeType::find(TreeNode* tree, ItemType& item){
	if (tree == nullptr){ // base case 2
    	return false;
    }
    else if(tree->value == item){ // base case 1
    	item = tree->value;
    	return true;
    }
    else if(tree->value < item){
    	return find(tree->right, item);
    }
    else {
    	return find(tree->left, item);
    }
}

insertItem()

Logical Level

값이 들어갈 자리를 찾고 넣어주면 될 것같다. 근데 찾았을 때 직전의 노드를 바꿔야하므로 이도 call-by-ref 방식을 사용하여 자동으로 바뀌도록 구현해보자.

Base case: 현재 tree가 nullptr일 때
General case: 왼쪽, 오른쪽 탐색

Implementation Level

void TreeType::insertItem(ItemType item){
	return find(root, item);
}

Void TreeType::insert(TreeNode*& tree, ItemType item){
	if (tree == nullptr){
    	tree = new TreeNode<ItemType>; // 자동으로 바뀜
        tree->right = nullptr;
        tree->left = nullptr;
        tree->value = item;
    }
    else if(tree->value < item){
    	return insert(tree->right, item);
    }
    else {
    	return insert(tree->left, item);
    }
}

tree->right 혹은 left로 값을 받아오기 때문에 tree = new TreeNode<ItemType>;을 해주면 자연스럽게 왼쪽 혹은 오른쪽 tree가 새로운 노드를 가리키도록 할 수 있다.

deleteItem()

Logicla Level

노드를 delete하는 것은 추가적인 작업이 필요하다. 왜냐하면 지우고 나서도 BST성질을 유지해야하기 때문이다.

1. leaf노드를 delete할 때는 그냥 delete
2. 자식 노드를 하나만 갖고 있을때는 지우고 자식을 위로 올림
3. 자식 노드가 두 개 이상일 경우 왼쪽 가장 가까운 값과 바꾼다.
4. 가장 가까운 값은 왼쪽(오른쪽) subtree에서 제일 오른쪽(왼쪽) 값 (둘 중에 하나 고르면 됨)

Implementation Level

void TreeType::deleteItem(ItemType item){
	return delete(root, item);
}

void TreeType::delete(TreeNode*& tree, ItemType item){
	if(tree->value == item){
    	return deleteNode(tree);
    }
    else if (tree->value < item){
    	return delete(tree->right, item);
    }
    else {
    	return delete(tree->left, item);
    }
}

void TreeType::deleteNode(TreeNode*& tree){
	ItemType data;
    TreeNode* tempPtr = tree;
    
    if (tree->left == nullptr){ // 0 or 1 child
    	tree = tree->right;
        delete tempPtr;
    }
    else if (tree->right == nullptr){ // 1 child
    	tree = tree->left;
        delete tempPtr;
    }
    else{ // 2 children
    	getPredecessor(tree->left, data); // 왼쪽 subtree의 맨 오른쪽
        tree->value = data;
        delete(tree->left, data); // 나머지 child도 처리해야하기 때문에 다시 호출함 맨 끝에 있었던 애가 child를 갖는 경우도 있기 때문임
    }
}

void TreeType::getPredecessor(TreeNode* tree, ItemType& data){
	while(tree->right != nullptr){
    	tree = tree->right;
    }
    data = tree->value;
}

Tree Traversal

tree traversal의 뜻은 tree의 모든 노드를 방문한다는 뜻이다.
우리가 해야할 일에 따라 tree traversal을 3가지로 나누어 볼 수 있다.

1. Inorder Traversal -> 오름차순으로 tree print
2. Preorder Traversal -> copy the tree
3. Postorder Traversal -> delete the tree

Inorder Traversal

Implementation Level

void TreeType::inOrder(TreeNode* tree){
	if (tree != nullptr){
    	inOrder(tree->left);
        do Something with tree->value // Queue로 data 저장을 하곤 함
        inOrder(tree->right);
    }
}

Preorder Traversal

deep copy를 할 때 위에서부터 아래로 copy

Implementation Level

void TreeType::preOrder(TreeNode* tree){
	if (tree != nullptr){
    	do Somthing with tree->value
        preOrder(tree->left);
        preOrder(tree->right);
    }
}

이 traversal 방식은 Depth-first search 즉, DFS 방식이라 부른다.

Postorder Traversal

아래에서부터 위로 traverse하며 지워야 한다.

Implementation Level

void TreeType::postOrder(TreeNode* tree){
	if (tree != nullptr){
        postOrder(tree->left);
        postOrder(tree->right);
        do Somthing with tree->value
    }
}

시간 복잡도

이러한 BST가 array기반 list나 linked 기반 list보다 시간 복잡도 측면에서 유리하다.
findItem()이나 insertItem(), removeItem()에서 더 유리하다.

Binary Tree Types

Full Binary Tree

정 이진 트리로 child가 1개만 있는 노드가 존재하지 않는 tree이다. 즉, 모든 노드는 child를 0개 혹은 2개를 갖고있다.

Complete Binary Tree

완전 이진 트리로 노드를 위에서부터 그리고 왼쪽에서부터 채우는 tree를 말한다.

Perfect Binary Tree

포화 이진 트리로 leaf 노드 제외 모든 노드가 2개의 child를 갖는 tree를 말한다.

Array Representation of Trees

tree를 linked 말고 array 형식으로 구현는 것도 가능하다.

위 그림처럼 위에서부터 그리고 왼쪽으로 인덱스를 붙인다.

아이템은 delete하면 -1로 채워준다.

Index

어떠한 노드의 index를 알 때

1. 왼쪽 child 노드 = index * 2 + 1
2. 오른쪽 child 노드 = index * 2 + 2
3. parent 노드 = (index - 1) / 2