Difference between revisions of "Binary search tree"

From 탱이의 잡동사니
Jump to: navigation, search
(Created page with "== Overview == 이진 탐색 트리(BST: Binary search tree) 내용 정리 == Basic == BST 는 다음과 같은 속성이 있는 이진 트리 자료 구조 이다. * 각 노...")
 
 
Line 28: Line 28:
 
* 자식 노드가 2개인 노드 삭제: 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰 값으로 대체하거나, 오른쪽 서브트리에서 가장 작은 값으로 대체한 뒤, 해당 노드(왼쪽 서브 트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드)를 삭제한다.
 
* 자식 노드가 2개인 노드 삭제: 삭제하고자 하는 노드의 값을 해당 노드의 왼쪽 서브트리에서 가장 큰 값으로 대체하거나, 오른쪽 서브트리에서 가장 작은 값으로 대체한 뒤, 해당 노드(왼쪽 서브 트리에서 가장 큰 값을 가지는 노드 또는 오른쪽 서브트리에서 가장 작은 값을 가지는 노드)를 삭제한다.
  
 +
== Examples ==
 +
=== C ===
 +
<source lang=c>
 +
 +
#include <stdio.h>
 +
#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>
  
 
[[category:alrorithm]]
 
[[category:alrorithm]]

Latest revision as of 11:17, 8 February 2018

Overview

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

Basic

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

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

Search

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

Insert

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

Delete

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

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

Examples

C

#include <stdio.h>
#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;
}