3. Tree

Tree

 

트리는 스택이나 큐와 같은 선형구조가 아닌 비선형 자료구조이다. 트리는 계층적 관계를 표현하는 자료구조이다. 

 

트리의 구성 요소

 

• Node(노드) : 트리를 구성하고 있는 각각의 요소
• Edge(간선) : 트리를 구성하기 위해 노드와 노드를 연겨하는 선
• Root(루트) : 트리 구조에서 최상위에 있는 노드
• Terminal or Leaf Node(단말 노드) : 하위에 다른 노드가 연결되어 있지 않은 노드
• Internal Node(비단말 노드) : 단말 노드를 제외한 모든 노드로 루트 노드를 포함

이진 트리(Binary Tree)

 

루트를 중심으로 두 개의 서브 트리로 나뉜 트리이다. 또한 나뉜 두 서브 트리도 모두 이진 트리어야 한다.

재귀적인 성질을 가지고 있다. 추가로 공집합도 이진 트리로 포함시켜야 한다. 노드가 하나 뿐인 것도 이진 트리 정의에 만족한다.

 

트리에서는 각 층별로 숫자를 매겨 이를 트리의 level(레벨) 이라고 한다. 레벨의 값은 0부터 시작이고 따라서 루트 노드의 레벨은 0이다. 그리고 트리의 최고 레벨을 해당 트리의 height(높이) 라고 한다.

 

Binary Tree Traversal

 

1. Inorder Traversal(중위 순회)

 

 

• 왼쪽 서브트리를 중위순회 한다.
• 노드를 방문한다.
• 오른쪽 서브트리를 중위순회한다.

방문 순서 : A -> B -> C -> D -> E -> F -> G -> H -> I

 

 

 

2. Preorder Traversal(전위 순회)

 

• 노드를 방문한다
• 왼쪽 서브트리를 전위 순회한다.
• 오른쪽 서브트리를 전위 순회한다.

방문 순서 : F -> B -> A -> D -> C -> E -> G -> I -> H

 

3. Postorder Traversal(후위 순회)

 

• 왼쪽 서브트리를 후위 순회한다.
• 오른쪽 서브트리를 후위 순회한다.
• 노드를 방문한다

방문 순서 : A -> C -> E -> D -> B -> H -> I -> G -> F

 

코드

void Traversal(node) {
	if(node) {
    	//visit(node); preorder
        traversal(node->left);
        //visit(node); inorder
        traversal(node->right);
        //visit(node); postorder
    }
}

 

4. Levelorder traversal

 

root 부터 한 레벨씩 아래로 이동하는 level order는 queue를 이용하여 구현 가능하다.

 

queue<node> q;

void levelorder(root) {
	q.push(root);
    while(!q.empty()) {
    	node n = q.front();
    	q.pop();
        visit(n);
        if(n->left != null)
        q.push(n->left);
        if(n->right != null)
        q.push(n->right);
    }
}

BST(Binary Search Tree)

 

이진 탐색 트리란 이진 탐색(binary search)와 링크드 리스트(linked list)를 결합한 자료구조를 말한다.

이진 탐색의 효율적인 탐색 능력을 유지하면서도, 빈번한 자료 입력과 삭제를 가능하게끔 고안됐다.

 

이진 탐색의 경우 탐색에 소요되는 시간복잡도는 O(logn)로 빠르지만 자료 입력, 삭제가 불가능하다.

링크드 리스트의 경우 자료 입력, 삭제에 소요되는 시간복잡도는 O(1)이지만 탐색하는데 O(n)의 시간복잡도가 소요된다.

이 두마리 토끼를 잡는 것이 이진탐색트리의 목적이다.

 

이진 탐색 트리는 다음과 같은 규칙을 만족해야 한다.

• 각 노드의 왼쪽 서브트리에는 해당 노드의 값보다 작은 값을 지닌 노드들로 이루어져 있다.
• 각 노드의 오른쪽 서브트리에는 해당 노드의 값보다 큰 값을 지닌 노드들로 이루어져 있다.
• 중복된 노드가 없어야 한다.
• 왼쪽 서브트리, 오른쪽 서브트리 또한 이진 탐색 트리이다.

이진 탐색 트리를 순회할 때 중위 순회 방식으로 탐색하면 이진탐색트리 내에 있는 모든 값을 정렬된 순서대로 읽을 수 있다.

 

코드

 

 

typedef struct Node
{
	int key;
    struct Node* left;
    struct Node* right;
}Node;

Node* root = NULL;

Node* Insert(Node* root, int value) {
	if(root == NULL) {
    	root = (Node*)malloc(sizeof(Node));
        root->left = root->right = NULL;
        root->key = value;
        return root;
    }
    
    else {
    if(root->key > value)
    	root->left = Insert(root->left, value);
    else
    	root->right = Insert(root->right, value);
    }
    
    return root;
}

Node* findMinNode(Node* root)
{
    Node* temp = root;
    while(temp->left != NULL)
        temp = temp->left;
    return temp;
}

Node* Delete(Node* root, int value) {
	Node* temp = NULL;
    if(root == NULL)
    	return NULL;
        
    if(root->key > value)
    	root->left = Delete(root->left, value);
    else if(root->key < value)
    	root->right = Delete(root->right, value);
    else {
    	if(root->right != NULL && root->left != NULL) {
        	temp = findMinNode(root->right);
            root->key = temp->key;
            root->right = Delete(root->right, temp->key);
        }
        else {
        	temp = (root->left == NULL) ? root->right : root->left;
            free(root);
            return temp;
        }
    }
    
    return root;
}

Node* Search(Node* root, int value)
{
    if(root == NULL)
        return NULL;

    if(root->key == value)
        return root;
    else if(root->key > value)
        return Search(root->left, value);
    else
        return Search(root->right, value);
}