자료구조 및 알고리즘 8 - Binary Search Tree

자료구조 수업을 바탕으로 저의 생각을 정리하는 글 입니다.

 

0. Binary Search Tree

 

Definition

• Node contains key which can make us identify from other nodes
• There is one Root node(unless empty BST, but if there is Dummy data in Root, we do not have to take care of it
• Root node may have "two" child node(s)
• Each child is the root node of its subtree
• Each subtree is itself a BST
• The key values in left subtree are all smaller than the key values in right subtree

BST

 

1. Code for Node

 

class Node{
    int data;
    Node *L, *R;
};

 

2. Search Algorithm

 

1. call Search(Root, x)
2. Search(Node, x)
3. Recursion
   1. If no current Node then return Fail
   2. Compare data with x
      1. Equal) return current Node
      2. data < x) return Search(Right, x)
      3. data > x) return Search(Left, x)

 

2.1 Code for Search

Node* Search(Node *N, int x){
    // @param N: current Node
    // @param x: data to find

    // we cannot find where the data is
    if(N == NULL)
        return NULL;
    // if the data to find is smaller than data of N, we should call Search() with left Node of N
    else if(N->data > x){
        // std::cout << N->data << " ";
        return Search(N->L, x);   
    }
    // if the data to find is bigger than data of N, we should call Search() with right Node of N    
    else if(N->data < x){
        // std::cout << N->data << " ";
        return Search(N->R, x);
    }
    // success!
    else{
        // std::cout << "Found!! " << N->data << " ";
        return N;
    }
}

 

2.2 Performance

 

It might depend on how long the height of graph is

performance of search in BST

 

3. Insert Algorithm

 

First of all, we should call Search() and then if we found the node that have the data to insert, we could not insert the node.

We should connect the parent node with the node we are making

 

3.1 Code for Insert

Node* Insert(Node *N, Node **P, int x){
    // @param P: pointer of parent node 
    //           that is supposed to have the address of the node we are trying to insert
    if(N == NULL){
        Node *newNode = new Node(x);
        newNode->L = NULL;
        newNode->R = NULL;
        *P = newNode;
        return newNode;
    }
    // Search
    else{
        if(N->data > x)
            return Insert(N->L, &(N->L), x);
        else if(N->data < x)
            return Insert(N->R, &(N->R), x);
        // there is the node that have the data we want to insert
        else
            return NULL;
    }
}

 

4. Delete Algorithm

 

1. Do Seach()
2. if Search() returns Fail, Delete() returns Fail
3. there are 3 cases could come out
   1. the node to delete have no child node
   2. the node to delete have one child node
   3. the node to delete have two child nodes

Node* SearchEndNode(bool direct, Node* N){
    // direct true means left
    // direct false means right
    
    if(direct){
        if(N == NULL)
            return N;
        else
            return SearchEndNode(direct, N->L);
    }
    else{
        if(N == NULL)
            return N;
        else
            return SearchEndNode(direct, N->R);
    }
}

Node* Delete(Node *N, Node* P, int x){
    // Search
    if(N == NULL)
        return NULL;
    else if(N->data > x)
        return Delete(N->L, N, x);
    else if(N->data < x)
        return Delete(N->R, N, x);
    else{
        // case 1
        if(N->R == NULL && N->L == NULL){
            if(P->L == N){
                P->L = NULL;
                delete N;
            }
            else{
                P->R = NULL;
                delete N;
            }
        }
        // case 2
        else if(N->R == NULL || N->L == NULL){
            if(P->R == N && N->R != NULL){
                P->R = N->R;
                delete N;
            }
            else if(P->R == N && N->L != NULL){
                P->R = N->L;
                delete N;
            }
            else if(P->L == N && N->R != NULL){
                P->L = N->R;
                delete N;
            }
            else{
                P->L = N->L;
                delete N;
            }
        }
        // case 3
        else{
            if(P->L == N){
                Node* endNode = SearchEndNode(true, N->R);
                N->data = endNode->data;
                Delete(N, P, endNode->data);
            }
            else{
                Node* endNode = SearchEndNode(false, N->L);
                N->data = endNode->data;
                Delete(N, P, endNode->data);
            }
        }
    }

    return NULL;
}