5. 이진 탐색 트리(BST, Binary Searching Tree)

이진 탐색 트리

이진 탐색 트리는 아래의 조건을 만족해야 한다.

①각 노드에서 왼쪽 자식은 부모의 값보다 작고, 오른쪽 자식은 부모의 값보다 크다.

②각 노드는 모두 고유한 값을 갖는다.

이진 탐색 트리의 예시

 

연결리스트로 구현된 이진 탐색 트리 코드

class BST;

class Node{
friend BST;
private:
    int key;
    Node *left; Node *right;
public:
    Node(int k=0, Node *l=0, Node *r=0){
        key = k; left = l; right = r;
    }
};

class BST{
private:
    Node *root;
public:
    BST(){root=0;}
    void insert(int x){}

    void remove(int x){}
};

 

이진 탐색 트리에서의 삽입

삽입 될 위치를 탐색하는 과정을 거친후 삽입한다.

 void insert(int x){
        Node *p=root, *q=0;
        while(p){
            q=p;
            if(p->key == x)
                return;
            else if(p->key > x)
                p=p->left;
            else
                p=p->right;
        }//q가 삽입될 위치의 부모노드를 가리킴
        if(q->key > x)
            q->left = new Node(x);
        else
            q->right = new Node(x);
    }

 

이진 탐색 트리에서의 삭제

삭제의 경우 세가지 경우를 따져야 한다.

 

경우1. 삭제할 노드의 자식이 없는 경우

 방법 : 단순히 삭제

 

경우2. 삭제할 노드의 자식이 하나인 경우

 방법 : 삭제 후 자식 노드와 부모 노드를 잇는다.

 

경우3. 삭제할 노드의 자식이 둘인 경우

 방법 : 삭제할 노드의 왼쪽 서브트리에서 최대값 혹은 우측 서브트리에서 최소값과 교체후 삭제.

 

void remove(int key)
{
    int found = 0;
    if (!tree->root)
        return ERROR;

    Node *p = root; //to be deleted node
    Node *q = NULL;       //deleted node' parent
    while (p)
    {
        if (p->key == key)
        {
            found = 1;
            break;
        }
        q = p;
        if (p->key > key)
            p = p->left;
        else
            p = p->right;
    }

    if (found != 1)
    {
        printf("not found");
        return ERROR;
    }

    if ((p->left) && (p->right))
    { //two child
        Node *min = p->right, *min_parent = p;
        while (min->left)
        {
            min_parent = min;
            min = min->left;
        }
        if (min_parent->left == min)
        {
            min_parent->left = min->right;
        }
        else
        {
            min_parent->right = min->right;
        }

        p->key = min->key;
        free(min);
    }
    else if ((p->left == NULL) && (p->right == NULL))
    {	//no child
        if (q)
        {
            if (q->left == p)
                q->left = NULL;
            else
                q->right = NULL;
        }else //delete root
            tree->root = NULL;
        free(p);
    }
    else
    { // one child
        if (q){
            if (q->left) //Parent's left child is to be deleted
            {
                if (p->left)
                    q->left = p->left;
                else
                    q->left = p->right;
            }
            else{ //Parent's right child is to be deleted
                if (p->left)
                    q->right = p->left;

                else
                    q->right = p->right;
            }
        }
        else{ //delete root
            if (p->left)
                tree->root = p->left;
            else if (p->right)
                tree->root = p->right;
            else
                tree->root = NULL;
        }
        free(p);
    }
    return SUCCESS;
}

---

 

이진 탐색 트리의 경우 탐색, 삽입, 삭제의 시간 복잡도는 모두 O(h)이다.

 

편향된 이진 탐색 트리의 경우 시간복잡도 측에서 불리하기 때문에 보완한 방법이 AVL 트리이다.

 

AVL트리 : 높이가 균형을 이루는 트리. 좌측과 우측 서브트리의 높이차가 1이하.