자료구조: Tree(1) - Binary Search Tree -

오늘은 Search , Insert , Delete 모두 다 빠른 성능을 보여주는 Tree에 대해 알아보겠다.

 

Contents

 

• Skip List idea from Linked List
• Binary Search Tree Definition
• Search Algorithm, Insert Algorithm, Delete Algorithm
• Proofs of Correctness and Performance

Skip List

지난 포스트의 Skip List의 아이디어를 활용한 것이다. ( 링크드 리스트에서 여러개의 포인트를 설정하고 노드들 Jump 하기 )

 

Definition of Binary Search Tree

 

 

값은 아무거나 넣을 수 있다.  노드 3개를 묶어서 보았을 때 중간 노드의 값보다 큰 값은 오른쪽 작은 값은 왼쪽으로 들어가게되는 형태이다.  좀 더 명확하게 설명해보자.

 

• NODE contains Key
• there is one Root Node (unless empty BST)
• Root Node may have two (LEFT and RIGHT) CHILD(ren) Node(s)
• Each Child is the ROOT of its own SUBTREE
• Each Subtree is itself a BST
  • We call them Left and Rigth Subtree(s)
• The Key values in Left Subtree all smaller than the Key in the Root Node
  • And Vice Versa(= 오른쪽은 root 보다 큰 값)
  • Holds recursively in each Subtree (of course)

 

Code for Node

class Node {
    int k;
    Node *l, *r;
    
};

 

Search Algorithm

• Call Search (Root, X(찾으려는 값))
• Search(Node, X)
• Recursive Implementation
  • If no current Node then return FAIL (return NULL)
  • Compare K(Key at current Node) with X (value to Search)
  • If EQUAL then return current Node (pointer to the Node) [Case 1]
  • If K < X then return Search(Right Child, X) [Case 2]
  • If K > X them return Search(Left Child, X ) [Case 3]

Code for Search

 

Node *Search(Node *N, int x) 
{
    if (N == Null) return NULL;
    if (N -> k == X) return N;
    else if (N->k < X) return Search(N->r,X)
    else return Search(N->1, X);    
};

 

Search Correctness

 

• To Prove : "If X equals key in a node, Search() returns the pointer to the node, otherwise it will return FAIL"
• Proof by cases :
  • Case 1 : Trivial
  • Case 2 : "K < X" means that X is not in the Left SubTree, so if X is in the Tree then X is in the Right Subtree. Search(Right Child, X) will return the pointer to the node if X is in the Right Subtree
  • Case 3 : Ditto ( Case2 와 대칭 )

Search Performance

 

Height 에 대해 따로 정의를 안했는데 root에서 마지막 child 노드까지 노드의 개수를 height라고 하겠다. (왼 : height 5 오: height 9)

 

오른쪽과 왼쪽을 비교해 보았을 때 오른쪽 Tree 는 왼쪽에 비해 노드 개수에 비례한 height가 낮아진다. 직관적으로 생각해보면 Performace 는 height에 비례하게 될 것이다. Tree의 성능은 다음과 같다.

 

• Given a fixed Tree
  • Worst Case : O(Height)
  • Average Case: ??? (정하기가 매우 곤란함. 논란의 여지가 있음.)
• Considering All Possible Trees
  • Worst Case: O(n)
  • Average Case: Later(추후 포스터에서... )

Insert 5

 

Search를 생각해 봤으니 다음은 Insert를 알아보자. 예를들어서 5를 insert 하려면 어떤 방식으로 넣어야 할까?

 

Insert Algorithm

• First Search (Root, X) (Search가 먼저 선행.)
• If Search() succeeds, then Insert() fails.
• If Search() fails, then make a new Node at the last direction the Search() tried to go.

Insert Flow in Tree 

 

Code for Insert

Node *Insert(Node *N, int X) 
{
    while ( 1 ) {   
        
        if (N == Null) { //최초에만 발생 가능한 Case
            N = new Node ; 
            N -> l = n->r = Null; 
            N->k = X;
            return N;
        } 
        else if (N -> k == X) return NULL;
        else if (N->k < X) { 
            if (N->r == NULL) {
                P = new Node;
                P->l = P ->r =NULL;
                P->k = X;
                return P; 
        }
            else N = N->r;
        }
        else {
            //Ditto 
                };
 
}    
};

 

Insert Correctness

• Comes almost directly from the Correctness of Search
• When the algorithm goes down to a SubTree
  • It satisfies the condition that "If X is in the Tree, X is in that SubTree."

Performance

 

첫번째 case 단순한 루프 ->상수시간이다.

나머지 case들을 봐도 단순히 Search 과정에서 노드를 하나 생성&연결하는 것뿐이므로 결과적으로 Insert 하는데 걸리는 시간은search와 동일하다고 할 수 있겠다.