7-1. [C++] 이진 탐색 트리란?

탐색이란?

탐색(search)은 컴퓨터 응용 중 가장 중요한 것들 중 하나이다.

컴퓨터에는 데이터들이 저장되어 있고 이 데이터들 중에서 필요한 데이터를 찾아내는 작업은 빈번한 작업이다.

컴퓨터에 저장되는 데이터의 양이 급속도로 증가하고 있어 효율적이고 바른 탐색을 하는 것은 매우 중요하다.

 

자료구조의 관점에서 보면 탐색은 자료구조의 중요한 응용 분야 중 하나이다.

후에 다양한 탐색 방법을 알아볼 것이지만, 지금은 탐색을 위해 특화된 이진 트리인 이진 탐색 트리를 알아보자.

 

탐색 관련 용어

이진 탐색 트리를 알아보기 전에 탐색 관련 용어들을 먼저 알아보자.

컴퓨터 프로그램에서 탐색은 레코드(record)의 집합에서 특정한 레코드를 찾아내는 작업을 의미한다.

레코드는 하나 이상의 필드(field)로 구성된다.

레코드들의 집합을 테이블(table)이라고 한다.

레코드들은 키(key)라고 불리는 하나의 필드에 의해서 식별할 수 있다.

키는 서로 중복되지 않는 고유한 값을 가지기 때문에 이를 통해 각각의 레코드들을 구별할 수 있다.

이러한 키를 주요키(primary key)라고 한다.

---

이진 탐색 트리란?

이진 탐색 트리(BST, Binary Search Tree)는 이진 트리 기반의 효율적인 탐색을 위한 자료구조이다.

이진 탐색 트리는 트리의 정의처럼 재귀적으로 정의된다.

이진 탐색 트리(Binary Search Tree)

(1) 모든 모드는 유일한 키를 갖는다.
(2) 왼쪽 서브트리의 키들은 루트의 키보다 작다.
(3) 오른쪽 서브트리의 키들을 루트의 키보다 크다.
(4) 왼쪽과 오른쪽 서브트리도 이진 탐색 트리이다.

이진 탐색 트리의 ADT

이진 탐색 트리도 이진 트리의 일종이므로 이진 트리의 연산들을 ADT에 포함시킬 수 있다.

• 데이터 : 이진 탐색 트리의 특성을 만족하는 이진 트리
• 연산 : 
  • insert(node) : 이진 탐색 트리의 특성을 유지하면서 새로운 노드 node를 트리에 삽입한다.
  • remove(node) : 이진 탐색 트리의 특성을 유지하면서 노드 node를 트리에서 삭제한다.
  • search(key) : 키 값이 key인 노드를 찾아 반환한다.

이진 트리에서는 삽입/삭제 연산을 위한 노드의 위치를 지정하는 것이 쉽지 않아 코드로 구현하진 않았다.

이진 탐색 트리에서는 삽입/삭제 연산을 코드로 구현할 것이다.

이때 중요한 것은 삽입/삭제 연산 시 이진 탐색 트리의 조건을 유지해야 한다는 것이다.

---

이진 탐색 트리의 기본 틀

위 ADT를 바탕으로 UML 다이어그램을 만들어보자.

위 UML 다이어그램을 바탕으로 기본 틀을 만들어보자.

BinaryNode, BinaryTree 클래스는 이 전에 사용했던 것을 약간 수정해 재사용한다.

// BinaryNode.h
#include <iostream>

class BinaryNode {
protected:
    int data;
    BinaryNode *left;
    BinaryNode *right;

public:
    BinaryNode(int data = 0, BinaryNode *left = NULL, BinaryNode *right = NULL)
        : data(data), left(left), right(right) {}

    void setData(int data) { this->data = data; }
    void setLeft(BinaryNode *left) { this->left = left; }
    void setRight(BinaryNode *right) { this->right = right; }

    int getData() { return data; }
    BinaryNode *getLeft() { return left; }
    BinaryNode *getRight() { return right; }

    bool isLeaf() { return (left == NULL) && (right == NULL); }
};

// BinaryTree.h
#include "BinaryNode.h"
#include <algorithm>
using namespace std;

class BinaryTree {
protected:
    BinaryNode *root;

public:
    BinaryTree() : root(NULL) {}

    void setRoot(BinaryNode *node) { root = node; }
    BinaryNode *getRoot() { return root; }

    bool isEmpty() { return (root == NULL); }

    void preorder() {
        cout << "preorder   : ";
        preorder(root);
        cout << endl;
    }
    void preorder(BinaryNode *node) {
        if (node == NULL) return ;

        cout << "[" << node->getData() << "] ";
        preorder(node->getLeft());
        preorder(node->getRight());
    }
    void inorder() {
        cout << "inorder    : ";
        inorder(root);
        cout << endl;
    }
    void inorder(BinaryNode *node) {
        if (node == NULL) return;

        inorder(node->getLeft());
        cout << "[" << node->getData() << "] ";
        inorder(node->getRight());
    }
    void postorder() {
        cout << "postorder  : ";
        postorder(root);
        cout << endl;
    }
    void postorder(BinaryNode *node) {
        if (node == NULL) return;

        postorder(node->getLeft());
        postorder(node->getRight());
        cout << "[" << node->getData() << "] ";
    }
    void display() {
        preorder();
        inorder();
        postorder();
    }

    int getCount() {
        return isEmpty() ? 0 : getCount(root);
    }
    int getCount(BinaryNode *node) {
        if (node == NULL) return 0;

        return 1 + getCount(node->getLeft()) + getCount(node->getRight());
    }

    int getLeafCount() {
        return isEmpty() ? 0 : getLeafCount(root);
    }
    int getLeafCount(BinaryNode *node) {
        if (node == NULL) return 0;

        if (node->isLeaf()) return 1;
        else return getLeafCount(node->getLeft()) + getLeafCount(node->getRight());
    }

    int getHeight() {
        return isEmpty() ? 0 : getHeight(root);
    }
    int getHeight(BinaryNode *node) {
        if (node == NULL) return 0;

        return 1 + max(getHeight(node->getLeft()), getHeight(node->getRight()));
    }
};

// BiSearchTree.h
#include "BinaryTree.h"

class BiSearchTree : public BinaryTree {
public:
    BiSearchTree() {}
    ~BiSearchTree() {}

    // BinaryNode *search(int key) {}
    // BinaryNode *search(BinaryNode *node, int key) {}
    
    // void insert(BinaryNode *newNode) {}
    // void insert(BinaryNode *rootNode, BinaryNode *newNode) {}
   
    // void remove(int key) {}
    // void remove(BinaryNode *parent, BinaryNode *node) {}
};

위 코드의 틀을 바탕으로 주석처리된 부분들을 하나씩 채워보자.

 

위 코드는 아래 이미지를 클릭해 깃허브에서도 확인할 수 있다.