[ 자료구조 ] Binary Search Tree

트리(Tree)는 임의의 노드에서 다른 노드로의 경로가 하나 밖에 없는 자료구조입니다.

단 하나의 루트 노드(Root Node)가 있고, 루트 노드에서 하위 노드(Sub Node)들이 연결된 비선형 계층 구조입니다.

 

이진 트리 구조(Binary Tree)는 트리 자료구조 중에서 모든 노드가 최대 2개씩 자식 노드를 가질 수 있는 구조를 말합니다. 

 

< 이진 트리 분류 >

• 포화 이진 트리(Full Binary Tree) : 노드가 꽉 차 있는 트리입니다.
• 완전 이진 트리(Complete Binary Tree) : 마지막 레벨 전까지는 노드가 꽉 차있고, 마지막 레벨의 왼쪽에서 오른쪽으로 노드가 채워져 있는 트리입니다. (마지막 레벨이 다 채워지지 않아도 됨.)
• 편향 이진 트리(Skewed Binary Tree) :  왼쪽 혹은 오른쪽 서브트리만을 가지는 트리입니다.

이진 탐색 트리(Binary Search Tree) : 이진 트리 기반의 탐색을 위한 자료구조입니다.  모든 노드는 유일한 값이고

왼쪽 서브 트리의 값은 루트의 값보다 작고 오른쪽 서브 트리의 값은 루트보다 큰 값을 가지도록 구성합니다.

 

1. 구현 사항

#include <iostream>
 
using namespace std;
 
template<typename T>
class Node
{
public:
    T data;
    Node* left;
    Node* right;
 
    Node(T _data = 0, Node* _left = NULL, Node* _right  = NULL) : data(_data), left(_left), right(_right)
    {
 
    }
 
    ~Node()
    {
        left = NULL;
        right = NULL;
    }
};
 
template<typename T>
class Binary_Tree
{
public:
    int size;
    Node<T>* root;
 
    Binary_Tree(T data = 0)
    {
        root = new Node<T>(data, NULL, NULL);
    }
 
 
    ~Binary_Tree()
    {
        delete root;
    }
 
    Node<T>* Getroot()
    {
        return root;
    }
 
    void visit(Node<T>* current)
    {
        cout << current-> data << endl;
    }
 
    // 전위 순회 Current - Left - Right
    void preorder(Node<T>* current) 
    {
        if (current != NULL)
        {
            visit(current);
            preorder(current->left);
            preorder(current->right);
        }
    }
 
    // 중위 순회 Left - Current - Right
    void inorder(Node<T>* current)
    {
        if (current != NULL)
        {
            inorder(current->left);
            visit(current);
            inorder(current->right);
        }
    }
 
    // 후위 순회 Left - Right - Current
    void postorder(Node<T>* current)
    {
        if (current != NULL)
        {
            postorder(current->left);
            postorder(current->right);
            visit(current);
        }
    }
 
    // 노드 추가
    void insert(T data)
    {
        Node<T>* temp = root;
 
        while (true)
        {
            if (data < temp-> data) // 왼쪽
            {
                if (!temp-> data) // 데이터 없다면 추가.
                {
                    temp-> left = data;
                    return;
                }
                else // 있다면 다시
                {
                    temp = root-> left;
                }
            }
            else // 오른쪽
            {
                if (!temp-> data) // 데이터 없다면 추가.
                {
                    temp-> right = data;
                    return;
                }
                else // 있다면 다시
                {
                    temp = root-> right;
                }
            }
        }
 
    }
};

2. STL 활용 

#include <iostream>
#include <set>
 
using namespace std;
 
int main()
{
    set<string> s;
 
    // insert(element)
    s.insert("abc");
    s.insert("def");
    s.insert("ghi");
    s.insert("jkl");
 
    // erase(element)
    s.erase("jkl");
 
    // empty(), size()
    if (!s.empty()) cout << "s size : " << s.size() << '\n';
 
    // find(element)
    cout << *s.find("abc") << '\n';
    cout << *s.find("def") << '\n';
 
    // count(element)
    cout << "abc count : " << s.count("abc") << '\n';
 
    return 0;
}