Binary Search Tree

binary search tree는 해당 노드보다 큰 값을 갖는 노드는 자신의 오른쪽 노드에, 보다 작은 값을 갖는 노드는 자신의 왼쪽 노드에 배치되는 binary tree이다. 

왼쪽 자식 <= 나 <= 오른쪽 자식

 

BST는 최악의 경우(모든 노드가 정렬되어 삽입될 경우) O(n)의 시간에 수행되지만, 임의로 만들어진 트리의 높이의 기대값이 O(log n)이다. 

 

search, minimum, maximum, predecessor, successor, insert, delete등이 O(log n)시간 내에 가능하다. 

 

BST 형태로 자료가 입력되어 있을 경우, inorder traversal이라는 간단한 재귀함수를 통해 O(n)시간 내에 BST내의 모든 키를 정렬된 순서대로 출력할 수 있다. 

 

inorder_traversal(root)
    if root!=NULL
        inorder_traversal(root->left)
        print(root->key)
        inorder_traversal(root->right)

 

다음은 보다 복잡하지만 재귀를 사용하지 않는 Morris Traversal이라는 inorder traversal 기법이다.

다음 기법은 threaded tree의 기법을 응용한다. 

morris_traversal(root)
    if root==NULL
        return
    
    current_node=root
    while current_node != NULL
        if current_node->left==NULL
            print(current_node->key)
            current_node=current_node->right
        else
            previous_node = current_node->left
            
            //현재 노드의 predecessor까지 이동
            while predecessor_node->right != NULL and predecessor_node->right != current_node
                predecessor_node = predecessor_node->right

            //predecessor와 현재 노드를 연결 (threaded tree)
            if predecessor_node->right ==NULL
                predecessor_node ->right= current_node
                current_node=current_node->left
            
            else
                predecessor_node->right=NULL	//출력하면서 threaded 해제
                print(current_node->key)
                current_node=current_node->right

 

검색

tree_search(key)
    while root!=NULL
        if root->key==key
            break
        else if root->key<key 
            root=root->right
        else 
            root=root->left
    return root

 

min&max

tree_minimum(root)
    while root->left != NULL
        root=root->left
    return root

tree_maximum(root)
    while root->right != NULL
        root=root->right
    return root

 

Successor&Predecessor

tree_successor(root)
    if root->right != NULL
        root=root->right
        return tree_minimun(root)
    else
        parent=root->parent
        while parent!= NULL && parent -> right == root
            root=parent
            parent=parent->parent
        return parent

tree_predecessor(root)
    if root->left != NULL
        root=root->right
        return tree_maximum(root)
    else
        parent=root->parent
        while parent != NULL && parent -> left == root
            root= parent
            parent=parent->parent
        return parent

 

삽입

tree_insert(Tree, new_node)
    parent=NULL
    current_node=Tree.root
    while current_node != NULL
        parent= current_node
        if new_node->key < current_node -> key
            current_node=current_node -> left
        else 
            current_node=current_node -> right
    
    new_node->parent=parent
    
    if parent==NULL
        Tree.root=new_node
    else if new_node->key < parent->key
        parent->left=new_node
    else
        parent->right=new_node

삭제

삽입은 간단하지만 삭제는 간단하지 않다 

한 노드를 삭제하는 경우의 수는 4가지가 존재한다. 

1) 타겟 노드의 자식노드가 하나도 없을 경우

        이 경우, 타겟 노드의 부모노드로부터 타겟노드로 연결되는 자식 pointer를 끊어버림으로써 손쉽게 삭제가 가능하다

2) 타겟 노드의 왼쪽 자식 노드만 없을 경우

        이 경우, 해당 노드의 자식노드를 타겟 노드의 자리로 상승시킨다.

3) 타겟 노드의 오른쪽 자식 노드만 없을 경우

        이 경우, 해당 노드의 자식노드를 타겟 노드의 자리로 상승시킨다.

4) 타겟 노드가 두 개의 자식 노드를 갖고 있을 경우

        이 경우가 복잡하다. 이 경우 타겟 노드 자리에 올라온 노드에 대해 노드의 좌/우의 자식들이 BST의 특성을 만족해야 한다. 

        따라서 타겟 노드를 successor과 대체하거나, predecessor와 대체함으로써 좌우 노드들이 BST의 특성을 만족하게 한다. 

        이때 아래에서 올라오는 node들이 2개의 자식을 갖고있을 경우 문제가 복잡해지는 것이 아니냐고 물을 수도 있다. 

        그러나 아래에서 올라오는 노드들이 타겟 노드의 predecessor이거나 successor이기 때문에 이들은 최대 하나의 자식만을 갖는다.

 

삭제를 하기 전에 삭제를 위한 서브함수를 하나 정의한다.

transplant(Tree,target,successor)
    if target->parent==NULL
        Tree.root=successor
    else if target==target->parent->left
        target->parent->left=successor
    else 
        target->parent->right =successor
            
    if successor != NULL
        successor->parent=target->parent

transplant가 successor->parent->left, successor->parent->right는 수정하지 않는다.

이는 부모와 교환만 하는 것이 목적이 아니라, 부모와 교환한 후, 부모를 삭제할 생각이기 때문에 건드리지 않는다. 

tree_deletion(Tree, target)
    if target->left==NULL		//왼쪽 자식이 null이거나 양쪽 자식 모두가 null인 경우
        transplant(Tree,target,target->right)
    else if target->right==NULL
        transplant(Tree,target,target->left)	//오른쪽 자식이 null인경우
    else										//두 자식 모두가 존재할 경우
        successor=tree_minimum(target->right)
        
        if successor->parent!=target
            transplant(Tree,successor,successor->right)
            successor->right=target->right
            successor->right->parent=successor
        transplant(Tree,target,successor)
        successor->left=target->left
        successor->left->parent=successor

 

 

 

이번 페이지의 구현은 parent의 pointer를 저장해야한다.

parent pointer를 저장하지 않을 경우 각 노드마다 저장공간을 아낄 수 있다. 

다음 포스트에는 parent pointer를 저장하지 않은 경우의 BST에 대해 포스트하겠다.

 

다음은 c로 구현한 BST이다. 

 

/*
 parent node pointer를 포함 --> 수행속도는 향상, 보다 많은 메모리공간 차지
 
 순회: O(n)
 search: O(log n)
 min, max: O(log n)
 successor, predecessor: O(log n)
 insert: O(log n)
 delete: O(log n)
 */

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

struct node_struct{
    int key;
    struct node_struct* left;
    struct node_struct* right;
    struct node_struct* parent;
};
typedef struct node_struct* node;
void inorder_recur(node root);
void MorrisTraversal(node root);

node tree_search(node root,int key);
node tree_minimum(node root);
node tree_maximum(node root);
node tree_successor(node root);
node tree_predecessor(node root);
void tree_insert(node *root, int key);
void tree_delete(node* root, int key);
void transplant(node* root,node node1,node node2);

int main(int argc, const char * argv[]) {
    node root=NULL;
    tree_insert(&root, 38);
    
    
    for(int i=0;i<24;i++){
        int i=rand()%88+1;
        printf("%d 삽입\n",i);
        tree_insert(&root, i);
    }
    printf("입력끝\n\n");
    MorrisTraversal(root);
    
    //삭제시험
    MorrisTraversal(root);
    tree_delete(&root, 2);
    MorrisTraversal(root);
    tree_delete(&root,75);
    tree_delete(&root,38);
    MorrisTraversal(root);
}

void inorder_recur(node root){
    if(root){
        inorder_recur(root->left);
        printf("%d ",root->key);
        inorder_recur(root->right);
    }
}

void MorrisTraversal(node root)
{
  node current, pre;

  if (root == NULL)
    return;

  current = root;
  while (current != NULL) {

    if (current->left == NULL) {
      printf("%d ", current->key);
      current = current->right;
    }
    else {

      /* Find the inorder predecessor of current */
      pre = current->left;
      while (pre->right != NULL
        && pre->right != current)
        pre = pre->right;

      /* Make current as the right child of its
      inorder predecessor */
      if (pre->right == NULL) {
        pre->right = current;
        current = current->left;
      }

      /* Revert the changes made in the 'if' part to
      restore the original tree i.e., fix the right
      child of predecessor */
      else {
        pre->right = NULL;
        printf("%d ", current->key);
        current = current->right;
      } /* End of if condition pre->right == NULL */
    } /* End of if condition current->left == NULL*/
  } /* End of while */
    printf("\n");
}

node tree_search(node root,int key){
    while(root){
        if(root->key==key) return root;
        else if(root->key<key) root=root->right;
        else root=root->left;
    }
    return root;
}

node tree_minimum(node root){
    while(root->left) root=root->left;
    return root;
}

node tree_maximum(node root){
    while(root->right) root=root->right;
    return root;
}

node tree_successor(node root){
    if(root->right){
        root=root->right;
        return tree_minimum(root);
    }else{
        node parent=root->parent;
        while(parent!=NULL && parent->right==root){
            root=parent;
            parent=parent->parent;
        }
        return parent;
    }
}

node tree_predecessor(node root){
    if(root->left){
        root=root->left;
        return tree_maximum(root);
    }else{
        node parent=root->parent;
        while(parent!=NULL && parent->left==root){
            root=parent;
            parent=parent->parent;
        }
        return parent;
    }
}

void tree_insert(node *tree, int key){
    node root=*tree;
    if(root==NULL){
        node new=malloc(sizeof(struct node_struct));
        new->key=key;
        new->right=NULL;
        new->left=NULL;
        new->parent=NULL;
        
        *tree=new;
        return;
    }
    node parent=NULL;
    while(root){
        parent=root;
        if(root->key<key) root=root->right;
        else if(root->key>key) root=root->left;
        else{
            printf("해당 키가 이미 트리 내에 있습니다.\n");
            return;
        }
    }
    node new=malloc(sizeof(struct node_struct));
    new->key=key;
    new->right=NULL;
    new->left=NULL;
    new->parent=parent;
    if(parent){
        if(parent->key>key) parent->left=new;
        else parent->right=new;
    }
}

void tree_delete(node* root, int key){
    node target=tree_search(*root, key);
    if(target==NULL){
        printf("그런 노드 없습니다.\n");
        return;
    }else{
        if(target->left==NULL){
            transplant(root, target, target->right);
        }else if(target->right==NULL){
            transplant(root, target, target->left);
        }else{
            node successor=tree_minimum(target->right);
            if(successor->parent!=target){
                transplant(root, successor, successor->right);
                successor->right=target->right;
                successor->right->parent=successor;
            }
            transplant(root, target, successor);
            successor->left=target->left;
            successor->left->parent=successor;
        }
    }
}

void transplant(node* root, node node1,node node2){
    if(node1->parent==NULL){
        *root=node2;
    }else if(node1==node1->parent->left){
        node1->parent->left=node2;
    }else{
        node1->parent->right=node2;
    }
    if(node2!=NULL) node2->parent=node1->parent;
}