BST 구현하기, C++

 

BST를 구현해보고 기본적인 함수들을 구현해보자

BST는 이진 탐색 트리로 루트노드보다 작은 값은 항상 왼쪽에 큰 값은 항상 오른쪽에 존재하는 트리다.

 

#include <iostream>


//노드에 대한 정의 이진 트리이기 때문에 자식은 2개가 최대임
struct node
{
    int data;
    node* left;
    node* right;
}

struct bst
{
    node* root = nullptr; //초기 값은 널

    
    node* find(int value)
    {
        return find_implement(root, value);
    }
    
private:
        node* find_implement(node* current, int value)
        {
            //현재노드가 NULL이라면
            if(!current)
            {
                std::cout << std::endl;
                return NULL;
            }
            //현재 노드가 원하는 노드라면
            if(current->data == value)
            {
                std::cout << value << std::endl;
                return current; //해당 노드 반환
            }
            //우리가 찾으려는 값이 현재 노드 값보다 작을 경우
            if(value < current->data)
            {
                std::cout << current->data << "보다 작습니다." << std::endl;
                return find_implement(current->left, value);
            }
            //큰 경우
            std::cout << current->data << "보다 큽니다." << std::endl;
            return find_implementation(current->right, value
            
        }
public:
        //해당 노드를 넣음
        void insert(int value)
        {
        	//루트노드가 비어있으면 루트노드가 된다.
            if(!root) root = new node{value, NULL, NULL};
            //루트노드가 있으면 루트노드부터 어디에 넣을지 탐색
            else insert_implementation(root, value);
        }
        
private:
    	//노드를 어디다 넣어야 할 지를 재귀적으로 찾음
        void insert_implement(node* current, int value)
        {
            if(value < current->data)
            {
                if(!current->left)
                    current->left = new node{value, NULL, NULL};
                else
                    insert_implement(current->left, value);
            }
            else
            {
                if(!current->right)
                    current->right = new node {value, NULL, NULL};
                else
                    insert_implement(current->right, value);
            }
        }
    
    //중위 순회를 기본적으로 한다.
public:
        void inorder()
        {
            inorder_implement(root);
        }
        
private:
        void inorder_implement(node* start)
        {
            if(!start) return;
            inorder_implement(start->left);
            std::cout << start->data <<std::endl;
            inorder_implement(start->right);
        }
public:
	//계승자라고 해석하면 있어보이지만 아무튼 Successor는 자기보다 큰 노드 중 가장 작은 값을 말한다
	node* successor(node* start)
	{
        //자기보다 큰 값이기 때문에 오른쪽트리로 가는 것이다.
		auto current = start->right;
		while (current && current->left)
			current = current->left;
		return current;
	}
	//해당 노드 삭제함수.
	void deleteValue(int value)
	{
		root = delete_implement(root, value);
	}
private:
	node* delete_implement(node* start, int value)
	{
		if (!start)
			return NULL;

		if (value < start->data)
			start->left = delete_implement(start->left, value);
		else if (value > start->data)
			start->right = delete_implement(start->right, value);
		else
		{
			if (!start->left) // 자식 노드가 전혀 없거나, 왼쪽 자식 노드만 없는 경우
			{
				auto tmp = start->right;
				delete start;
				return tmp;
			}

			if (!start->right) // 오른쪽 자식 노드만 없는 경우
			{
				auto tmp = start->left;
				delete start;
				return tmp;
			}

			// 자식 노드가 둘 다 있는 경우
			auto succNode = successor(start);
			start->data = succNode->data;

			// 오른쪽 하위 트리에서 후계자(successor)를 찾아 삭제
			start->right = delete_implement(start->right, succNode->data);
		}

		return start;
	}
};

 

트리에게는 검색, 삭제, 삽입이 필요하다.

특별히 순회방법도 필요하다.

그리고 트리가 Root노드부터 검색하기 때문에 Root에서 처리를 어떻게 해야할지

해당 위치가 NULL일 때 설정을 잘 해주어야 한다.