C++로 구현하는 자료구조!!!트리자료구조(Tree)@@

강력한 언어, C++로 구현하는 자료구조

Tree - Binary Search Tree

  이번에 설명드릴 자료구조의 형태는 완전 이진트리(Binary Search Tree)로, Tree 자료구조 중 가장 많이 사용되는 자료구조입니다! 물론 제일 쉽기도 해요~ 여기부터는 조금 더 추상적으로 이해해야 하는 부분이 많기 때문에 쉽사리 이해하기 힘들 수 있습니다. 하지만, 자료구조를 알지 못하면 프로그램을 작성하는 건 무리입니다. 자료구조의 강력한 기능과 구현력을 바탕으로 정상적으로 작동되는 프로그램이 만들어지기 때문입니다!

 

완전 이진 트리의 추상적 형태 _ 출처 : geeksforgeeks.org

 

위의 형태로 구현되는 것이 완전 이진 트리입니다. 설명드리면, 노드의 왼쪽 하위 트리는 부모 노드보다 작은 노드가 포함되며 오른쪽 노드는 부모 노드보다 큰 노드가 포함됩니다! 당연히 추가되는 노드 또한 완전 이진트리의 형태를 갖추어야 하기 때문에 이러한 방식으로 삽입될 것입니다! 간단하게 트리에서 사용되는 용어를 설명드리자면,

 

노드	8,3,10 ... 등 각 객체가 노드가 됩니다.
차수	부모 노드가 가지고 있는 자식 노드의 수 입니다. 8은 루트노드로서, 차수가 2이겠죠?
리프 노드	Leaf노드로 잎파리의 의미인데요, 위의 그림에서 1처럼 아래 자식노드를 하나도 가지고 있지 않은 노드입니다. 당연히 차수는 0이죠
내부 노드	Branch노드로 자식을 가지고 있는 노드입니다.
방향 간선	Edge라고도 하는 부모 노드가 첫째, 자식 노드가 둘째 원소인 순서쌍이라고 볼 수 있습니다.
경로	Path는 이웃하는 두 노드가 앞이 부모, 뒤가 자식인 노드를 의미합니다.
노드의 깊이	루트노드 (8)에서 내부노드(6)까지의 깊이는 2이겠죠? 네, 루트 노드와 현재 구하고자 하는 노드사이의 길이이다
노드의 레벨	루트 노드에서 자신까지 가는 경로의 길이 더하기 1을 하면됩니다. 루트 노드의 레벨 1인데요, 그렇다면, 위 그림의 Maximum Level은 4가 되겠죠!!

 

어후 너무 많죠? 그냥 그렇구나하고 넘어가세요! 코드 짜다 보면 "아 이게 이 개념이었구나" 하게 되어있습니다!! 그렇다면 코드로 구현해볼까요? 함수의 크기가 조금 있는 편이기 때문에, 코드 블록별로 설명 드릴 텐데, 복잡하더라도 순서대로 코드 작성해보면서 따라오시면 금방 따라옵니다!!! 걱정 마세요 ㅎㅎㅎㅎ원래 어려운 형태니까요~

 

C++의 Class를 이용해 구현해보는 Tree(BST - Binary Search Tree)

1-1. 노드의 표현

노드의 표현은 너무 간단합니다. 어떤 걸 포함해야할까요? 당연히 노드는 부모 노드가 될 수 도 있고, 자식 노드도 될 수 있기 때문에, 왼쪽, 오른쪽 포인터 노드를 둘 다 가지고 있어야 합니다. 그리고 정수 값을 담을 변수가 들어갈 것입니다!!

 

struct Node{
    Node *left, *right;
    int value;
};

위처럼 구현해주시면 됩니다. 왼쪽과 오른쪽을 가리킬 수 있는 포인터 변수가 자식 노드를 가리킬 것입니다!!

 

1-2. 완전 이진 트리의 표현

조금 길 수 있어서 많이 끊어냈습니다. 코드 블록이 많이 생겨서 보는 게 귀찮은 것보다 하나하나 어떻게 구현되는지 확인하는 게 더 도움될 것 같아서요~

1-2-1. 클래스 구현부

class BinarySearchTree{
    public:
        BinarySearchTree():root(nullptr){};
        ~BinarySearchTree(){};
 
        void addNode(int value);
        bool searchValue(int value);
        void removeNode(int value);
        void show();
    private:
        Node *root;
        Node *tail;
 
        void inOrder(Node *current){
            if(current != nullptr){
                inOrder(current -> left);
                cout << current -> value << endl;
                inOrder(current -> right);
            }
        }
 
        Node *searchMaxNode(Node *node){
            if(node == NULL)
                return NULL;
            while(node -> right != NULL){
                node = node -> right;
            }
            return node;
        }
        Node *removeSequence(Node *node, int _value);
};

루트노드와 꼬리 노드가 있는데, 뭐 사실 꼬리 노드는 해줘도 그만 ~ 안 해줘도 그만입니다. 루트 노드는 당연히 트리의 시작이 되는 노드이겠죠? 구현되는 멤버 함수는, 노드를 추가하는 함수, 탐색하는 함수, 제거하는 함수, 그리고 출력하는 함수는 inorder() 함수로 중위 순회의 의미를 가집니다. 중위 순회에 대해서 설명을 드리면,

 

Inorder _ Tree Traversal _ 출처 : geeksforgeeks.org

 

만약 위와 같은 트리가 있다면, 깊이 우선 탐색을 실시하는데, 방향이 4 -> 2 -> 5 -> 1 -> 3의 순서로 왼쪽 노드부터 우선적으로 탐색하는 알고리즘입니다!! 

 

그리고 searchMaxNode가 있는데, 아주 간단한 역할을 수행합니다. 최댓값을 가진 노드를 찾아서 반환하는데요, 잘 생각해보세요! 가장 큰 값은 오른쪽으로 계속 밀어 넣으니까 오른쪽으로만 탐색하면 아주 간단하게 탐색에 성공하겠죠?? ㅎㅎ 네 그렇습니다. 이제 노드를 추가하는 함수에 대해서 설명드리겠습니다.

 

1-2-2. 노드를 추가하는 함수

void BinarySearchTree::addNode(int value){
    Node *node = new Node();
    Node *tmpRoot = nullptr;
 
    node -> value = value;
    if(root == nullptr)
        root = node;
    else{
        Node *ptr = root;
        while(ptr != nullptr){
            tmpRoot = ptr;
            if(node -> value < ptr -> value){
                ptr = ptr -> left;
            }else{
                ptr = ptr -> right;
            }
        }
        if(node -> value < tmpRoot -> value)
            tmpRoot -> left = node;
        else
            tmpRoot -> right = node;
    }
}

Node * BinarySearchTree::removeSequence(Node *node, int _value){
    if(node == nullptr) return node;
    else if(node -> value > _value){
        node -> left = removeSequence(node -> left ,_value);
    }else if(node -> value < _value){
        node -> right = removeSequence(node -> right, _value);
    }else{
        Node *ptr = node;
        if(node -> right == nullptr && node -> left == nullptr){
            delete node;
            node = nullptr;
        }else if(node -> right == nullptr){
            node = node -> left;
            delete ptr;
        }else if(node -> left == nullptr){
            node = node -> right;
            delete ptr;
        }else{
            ptr = searchMaxNode(node -> left);
            node -> value = ptr -> value;
            node -> left = removeSequence(node -> left, ptr -> value);
        }
    }
    return node;
}
 
void BinarySearchTree::removeNode(int value){
    Node *ptr = root;
    removeSequence(ptr, value);
}

bool BinarySearchTree::searchValue(int value){
    Node *ptr= root;
    Node *tmpRoot = nullptr;
    while(ptr != nullptr){
        if(ptr -> value == value){
            cout << value << "Found" << endl;
            return true;
        }else if(ptr -> value > value)
            ptr = ptr -> left;
        else
            ptr = ptr -> right;
    }
    cout << value << "not Found" << endl;
    return false;
}

#include <iostream>#include <string>using namespace std;int main(){
    BinarySearchTree *BST = new BinarySearchTree();
    BST -> addNode(1);
    BST -> addNode(3);
    BST -> addNode(6);
    BST -> addNode(9);
    BST -> addNode(13);
    BST -> addNode(22);
    BST -> addNode(17);
    BST -> addNode(10);
    BST -> addNode(2);
 
    BST -> show(); cout << endl;
    BST -> searchValue(4);
    BST -> searchValue(17);
    BST -> removeNode(22);
 
    BST -> show();
 
    cout << endl;
    return 0;
}
 
RESULT > 
1
2
3
6
9
10
13
17
22
 
4not Found
17Found
 
1
2
3
6
9
10
13
17