Binary search tree

From 탱이의 잡동사니
Jump to navigation Jump to search
The printable version is no longer supported and may have rendering errors. Please update your browser bookmarks and please use the default browser print function instead.

Overview

이진 탐색 트리(BST: Binary search tree) 내용 정리

Basic

BST 는 다음과 같은 속성이 있는 이진 트리 자료 구조 이다.

  • 각 노드에 값이 있다.
  • 각 노드의 키 값은 모두 달라야 한다.
  • 값 들은 전순서(totally ordered set-toset: 임의의 두 원소를 비교할 수 있는 부분 순서 집합)가 있다.
  • 노드의 왼쪽 서브트리에는 그 노드의 값보다 작은 값들을 지닌 노드들로 이루어져 있다.
  • 노드의 오른쪽 서브트리에는 그 노드의 값보다 큰 값들을 지닌 노드들로 이루어져 있다.
  • 좌우 하위 트리는 각각이 다시 이진 탐색 트리여야 한다.
  • 중복된 노드가 없어야 한다.

Search

  • 이진 탐색 트리에서 키 X 를 가진 노드를 검색하고자 할 때, 트리에 해당 노드가 존재하면 해당 노드를 리턴하고, 존재하지 않으면 NULL 을 리턴한다.
  • 검색하고자 하는 값을 루트 노드와 먼저 비교하고, 일치할 경우 루트노드를 리턴한다.
불일치하고 검색하고자 하는 값이 루트 노드보다 작을 경우 왼쪽 서브트리에서 재귀적으로 검색한다.
불일치하고 검색하고자 하는 값이 루트 노드보다 클 경우 오른쪽 서브트리에서 재귀적으로 검색한다.

Insert

  • 삽입을 하기 전 검색을 수행한다.
  • 트리를 검색한 후 일치하는 노드가 없으면 마지막 노드에서 키와 노드의 크리를 비교해서 왼쪽이나 오른쪽에 새로운 노드를 삽입한다.

Delete

삭제하려는 노드의 자식 수에 따라..

  • 자식 노드가 없는 노드(리프 노드) 삭제: 해당 노드를 단순히 삭제한다.
  • 자식 노드가 1개인 노드 삭제: 해당 노드를 삭제하고 그 위치에 해당 노드의 자식 노드를 대입한다.
  • 자식 노드가 2개인 노드 삭제: 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰 값으로 대체하거나, 오른쪽 서브트리에서 가장 작은 값으로 대체한 뒤, 해당 노드(왼쪽 서브 트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드)를 삭제한다.

Examples

C

<source lang=c>

  1. include <stdio.h>
  2. include <stdlib.h>

struct bst_node { 

 int value;
 
 struct bst_node* left;
 struct bst_node* right;

};

struct bst_node* create_node(int value) { 

 struct bst_node* node;
 
 node = calloc(1, sizeof(struct bst_node));
 node->left = NULL;
 node->right = NULL;
 node->value = value;
 
 return node;

}

void release_node(struct bst_node* node) { 

 free(node);
 
 return;

}

void release_nodes(struct bst_node* node) { 

 if(node == NULL) {
   return;
 }
 
 release_nodes(node->left);
 release_nodes(node->right);
 
 release_node(node);

}

void insert_node(struct bst_node* root, int value) { 

 if(root == NULL) {
   fprintf(stderr, "Wrong input parameter.\n");
   return;
 }
   
 if(value < root->value) {
   if(root->left == NULL) {
     root->left = create_node(value);
     return;
   }
   else {
     insert_node(root->left, value);
     return;
   }
 }
 else if(value > root->value) {
   if(root->right == NULL) {
     root->right = create_node(value);
     return;
   }
   else {
     insert_node(root->right, value);
     return;
   }
 }
 else {
   // should not reach to here.
   fprintf(stderr, "Something was wrong. Should not reach to here.\n");
   return;
 }
 
 // should not reach to here.
 fprintf(stderr, "Something was wrong. Should not reach to here.\n");
 return;

}

static struct bst_node* find_minimum(struct bst_node* root) { 

 if(root->left == NULL) {
   return root;
 }
 
 return find_minimum(root->left);

}


struct bst_node* delete_node(struct bst_node* root, int value) { 

 struct bst_node* node_tmp;
 
 if(root == NULL) {
   return NULL;
 }
 
 if(value < root->value) {
   root->left = delete_node(root->left, value);
 }
 else if(value > root->value) {
   root->right = delete_node(root->right, value);
 }
 else {
   // found node. delete it.
   
   if((root->left == NULL) && (root->right == NULL)) {
     release_node(root);
     return NULL;
   }
   else if(root->left == NULL) {
     release_node(root);
     return root->right;
   }
   else if(root->right == NULL) {
     release_node(root);
     return root->left;
   }
   else {
     // node has two children
     node_tmp = find_minimum(root->right);
     root->value = node_tmp->value;
     root->right = delete_node(root->right, node_tmp->value);
   }      
 }
 
 return root;

}

struct bst_node* search_node(struct bst_node* root, int value) { 

 if(root == NULL) {
   fprintf(stdout, "Could not find node.\n");
   return NULL;
 }
 
 if(value == root->value) {
   return root;
 }
 else if(value < root->value) {
   return search_node(root->left, value);
 }
 else if(value > root->value) {
   return search_node(root->right, value);
 }
 
 // should not reach to here
 fprintf(stderr, "Should not reach to here. Something was wrong.\n");
 return NULL;

}

int get_height(struct bst_node* root) { 

 int height_left;
 int height_right;
 
 if(root == NULL) {
   return 0;
 }
 
 height_left = get_height(root->left);
 height_right = get_height(root->right);
 
 if(height_left > height_right) {
   return (height_left + 1);
 }
 else {
   return height_right + 1;
 }
 
 // should not reach to here.
 fprintf(stderr, "Should not reach to here. Something was wrong.\n");
 return -1;

}

void print_given_level(struct bst_node* root, int level) { 

 if((root == NULL) || (level < 0)) {
   return;
 }
 
 if(level == 1) {
   printf("%d ", root->value);
 }
 
 print_given_level(root->left, level - 1);
 print_given_level(root->right, level -1);
 
 return;

}

void print_level_order(struct bst_node* root) { 

 int height;
 int i;
 
 height = get_height(root);
 for(i = 1; i <= height; i++) {
   print_given_level(root, i);
   printf("\n");
 }
 
 return;

}

int main(int argc, char** argv) { 

 struct bst_node* root;
 struct bst_node* node_tmp;
 
 root = NULL;
 root = create_node(5);
 
 insert_node(root, 3);
 insert_node(root, 2);
 insert_node(root, 4);
 insert_node(root, 7);
 insert_node(root, 6);
 insert_node(root, 8);

 print_level_order(root);
 
 node_tmp = search_node(root, 4);
 if(node_tmp == NULL) {
   printf("Could not find node info.\n");
 }
 else {
   printf("Found node. value[%d]\n", node_tmp->value);
 }

 node_tmp = search_node(root, 9);
 if(node_tmp == NULL) {
   printf("Could not find node info.\n");
 }
 else {
   printf("Found node. value[%d]\n", node_tmp->value);
 }

 delete_node(root, 3);
 print_level_order(root);
 
 release_nodes(root);
 
 return 0;

} </source>

Retrieved from "http://wiki.pchero21.com/index.php?title=Binary_search_tree&oldid=2895"