[C++] Tree의 정의 및 Binary Search Tree의 구현

정의

• 트리는 list, queue 등과 달리 한 노드가 여러 노드를 가리킬 수 있는 비선형적 자료구조
• 최상위 노드가 존재하는 계층적인 형태
• 단방향 그래프
• 시작 노드에서 출발해서 다시 돌아올 수 없는 사이클이 없는 연결 그래프

 

용어

• 노드(Node): 트리를 구성하는 데이터 원소
• 간선(Edge): 노드와 노드를 연결하는 선 (노드의 개수 n, 간선의 수 n-1)
• 루트 노드(Root Node): 부모 노드가 없는 트리의 가장 최상단에 있는 노드. 트리에 1개 존재
• 부모 노드(Parent Node): 연결된 두 노드 중 위에 있는 노드
• 자식 노드(Child Node): 부모 노드의 하위 노드
• 형제 노드(Sibling Node): 같은 부모를 갖는 노드
• 조상 노드(Ancestor Node) / 자손 노드(Descedent Node): 노드 V에서 부모 노드로만 계속 이동해서 노드 U로 갈 수 있다면 U는 V의 조상 노드, V는 U의 자손 노드
• 리프 노드(Leaf Node): 자식 노드가 없는 노드
• 서브 트리(Sub Tree): 어떤 노드와 부모 노드 간 연결을 끊으면 해당 노드를 루트 노드로 하는 새로운 트리가 만들어짐. 이것을 서브 트리라고 함. (큰 트리 내부에 트리 구조를 갖춘 작은 트리 - 재귀적 형태)
• 높이(Height): 리프 노드로부터 해당 노드까지 이동하기 위해 거쳐야 하는 간선의 수 (루트 노드의 높이 = 트리의 높이)
• 깊이(Depth): 루트 노드로부터 해당 노드까지 이동하기 위해 거쳐야 하는 간선의 수
• 레벨(Level): 같은 깊이를 가진 노드의 집합
• 트리의 크기(Size of Tree): 트리의 크기는 노드의 개수와 동일

 

Binary Tree 순회

• pre-order (전위 순회): 자신 -> 왼쪽 서브 트리 -> 오른쪽 서브 트리
• in-order (중위 순회): 왼쪽 서브 트리 -> 자신 -> 오른쪽 서브 트리 (key를 정렬한 결과와 같음)
• post-order (후위 순회): 왼쪽 서브 트리 -> 오른쪽 서브 트리 -> 자신
  • 자식 서브 트리를 모두 방문한 후에 자신을 방문하기에 자식 노드에서 계산된 결과를 자신이 활용 가능
  • 계산기 구현, 세그먼트 트리 등

 

Binary Search Tree(BST)

• 정렬된 이진 트리
• 원소의 중복을 허용하지 않음
• 노드의 왼쪽 서브 트리는 노드 값보다 작은 값을 가짐
• 노드의 오른쪽 서브 트리는 노드 값보다 큰 값을 가짐
• 이러한 특성으로 최솟값은 트리의 레벨에 관계없이 가장 왼쪽 끝에 위치한 노드
• 최댓값은 트리의 레벨에 관계없이 가장 오른쪽 끝에 있는 노드
• C++ std::set에는 Binary Search Tree 중 하나는 Red Black Tree가 사용

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

constexpr size_t MAX_NODE = 1000; // 정적 할당

int node_count = 0;
Node node_pool[MAX_NODE];

Node* new_nodw(int x){
	node_pool[node_count].key = x;
    node_pool[node_count].left = nullptr;
    node_pool[node_count].right = nullptr;
}

class BinarySearchTree{
	Node* root;

public:
	BinarySearchTree() = default;
    
    void init() {
        root = nullptr;
        node_count = 0;
    }
    
    void insert(int x){
        root = insert_rec(root, x);
    }
    
    void remove(int x){
    	root = remove_rec(root, x);
    }
    
    bool find(int x) const {
    	Node* node = root;
        while (node != nullptr){
        	if (node->key == x){
            	return true;
            }
            node = x < node->key ? node->left : node->right;
        }
        return false;
    }
    
    void traversal(int type) const {
    	static constexpr std::array< const char*, 3>
        traversal_types = { "pre", "in", "post" };
        std:cout << tarversal_types[type] << "-order ";
        traversal_rec(root, type);
        std::cout << '\n';
    }
private:
	int find_min_key(Node* node) const {
    	while (node->left != nullptr){
        	node = node->left;
        }
    }
    
	// node를 루트로 하는 서브 트리에 x를 삽입한 다음 서브 트리의 루트를 리턴
    Node* insert_rec(Node* node, int x){
        // Node == NULL인 경우
        // 서브 트리가 비어있는 경우. X를 추가하면 노드가 x 하나뿐인 서브 트리가 생김
        // x 노드를 만든 뒤 바로 리턴
        if (node == nullptr){
            return new_node(x);
        }

        if (x < node->key) {
            node->left = insert_rec(node->left, x);
        } else if (x > node->key) {
            node->right = insert_rec(node->right, x);
        }

        // Node의 key와 x가 같은 경우, 트리에 이미 x가 존재하는 것.
        // BST는 원소의 중목을 허용하지 않기에 node를 그냥 반환
        return node;
    }
    
    // node를 루트로 하는 서브 트리에 x를 삭제한 다음 서브 트리의 루트를 리턴
    Node* remove_rec(Node* node, int x){
    	// Node == NULL인 경우
        // x가 원래 트리에 없는 경우. 아무 것도 하지 않고 서브 트리의 루트를 리턴
    	if (node == nullptr){
        	return node;
        }
        
        // Node의 왼쪽 자식 or 오른쪽 자식에서 x를 삭제해야 하는 경우
        if (x < node->key)
        	node->left = remove_rec(node->left, x);
        else if (x > node-> key)
        	node->right = remove_rec(node->right, x);
       	else {
        	// node의 key와 x가 같은 경우
            // node를 삭제하고 node의 부모 노드와 node의 자식 노드를 트리 구조에 맞게 이어주어야 함
            
            // node의 한 쪽 자식이 없는 경우
            // 한쪽 서브 트리가 이미 없으니 나머지 하나의 서브 트리만 남기에, 해당 서브 트리가 원래 트리를 대체
        	if (node->left == nullptr){
            	return node->right;
            } else if (node->right == nullptr) {
            	return node->left;
            }
            
            // node에 왼쪽 자식, 오른쪽 자식만 모두 있는 경우
            // BST를 유지하기 위해 node 자리에는 node의 왼쪽 서브 트리의 모든 값보다 크고,
            // node의 오른쪽 서브 트리의 모든 값보다 작은 값이 와야 함
            // 이를 위해서 node의 key를 오른쪽 서브트리에서 가장 작은 key 값으로 바꾸고, 오른쪽 서브 트리에서
            // 그 key를 삭제하는 대안 사용 (or 왼쪽 서브트리에서 가장 큰 key으로)
            const int temp = find_min_key(node->right);
            node->key = temp;
            node->right = remove_rec(node->right, temp);
        }
        
        return node;
    }
    
    void traversal_rec(Node* node, int type) const {
    	if (node == nullptr) return;
        
        if (type == 0) std::cout << node->key << ' ';
        traversal_rec(node->left, type);
        if (type == 1) std::cout << node->key << ' ';
        traversal_rec(node->right, type);
        if (type == 2) std::cout << node->key << ' ';
    }
}