이진 트리(Binary Tree)란?(완전/균형/이진 탐색 트리)

최대 차수가 2인 트리, 즉 노드가 왼쪽 자식과 오른쪽 자식만을 갖는 트리를 이진 트리라고 한다.

두 자식 가운데 하나 또는 둘 다 존재하지 않는 노드가 있어도 상관 없다. 

완전 이진 트리(Complete Binary Tree)

루트부터 아래쪽 레벨로 노드가 가득 차 있고,

같은 레벨 안에서 왼쪽부터 오른쪽으로 노드가 채워져 있는 이진 트리를 완전 이진 트리(Complete Binary Tree)라고 한다.

높이가 K인 완전 이진 트리가 가질 수 있는 노드의 수는 2의 K+1승 -1개 이다(ex 높이가 3일 때, 최대 15개).

 

균형 이진 트리(Balacned Binary Tree)

균형 이진 트리(Balanced Binary Tree)란 트리 내부 모든 노드의 왼쪽 서브 트리와 오른쪽 서브 트리의 높이차가 1을 넘지 않는

트리를 의미한다. 

 

이진 검색 트리(Binary Search Tree)

이진 검색 트리(Binary Search Tree)는 다음의 조건을 만족하는 이진 트리를 의미한다.

 

1. 왼쪽 서브 트리 노드의 키 값은 자신의 노드 키 값보다 작아야 한다.
2. 오른쪽 서브 트리 노드의 키 값은 자신의 노트 키 값보다 커야 한다.

이진 검색 트리는 구조가 단순하고, Inorder DFS를 통하여 노드 값을 오름차순으로 얻을 수 있다.

이진 검색과 비슷한 방식으로 아주 빠르게 검색할 수 있으며(O(log N)), 노드 삽입 역시 쉽다.

 

이진 검색 트리를 배열로 표현했을 때, 해당 배열의 특정 노드의 값 array[i]는 array[2*i + 1]을 왼쪽 자식으로,

array[2*i +2]를 오른쪽 자식으로 갖는다. 또한 부모 노드의 값은 array[i-1 //2]이다.

 

- 이진 검색 트리에서의 검색(Search)

  이진 검색 트리의 조건 상, 특정 값이 어떤 노드의 루트 값보다 작다면 그 값은 해당 노드의 왼쪽에 위치 하며,

  루트 값보다 크다면 오른쪽에 위치한다. 따라서 검색 시, 수행마다 루트를 기준으로 검색 범위를 왼쪽과 오른쪽으로 절반씩

  줄여나갈 수 있다. 

 

- 이진 검색 트리에서의 삽입(Insert)

  검색 과정과 유사하다. 이진 검색 트리 조건을 만족하는 자리를 찾아 그 자리에 값을 넣는다.

 

- 이진 검색트리에서의 삭제(Delete)

  이진 검색 트리에서의 삭제는 3가지 경우가 존재한다. 

 

  경우 1) : 삭제할 노드가 리프 노드인 경우

 추가 작업 없이 트리에서 해당 노드를 삭제하면 된다.

 

  경우 2) : 삭제할 노드의 자식 노드가 한 개인 경우

  삭제할 노드를 자식 노드로 대체하고, 이후 자식 노드를 원래의 위치에서 삭제한다.

 

  경우 3) : 삭제할 노드의 자식 노두가 두 개인 경우

  삭제할 노드를 해당 노드의 inorder successor로 대체하고, inorder successor를 원래의 위치에서 삭제한다.

 

// Binary Search Tree operations in C

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

struct node {
  int key;
  struct node *left, *right;
};

// Create a node
struct node *newNode(int item) {
  struct node *temp = (struct node *)malloc(sizeof(struct node));
  temp->key = item;
  temp->left = temp->right = NULL;
  return temp;
}

// Inorder Traversal
void inorder(struct node *root) {
  if (root != NULL) {
    // Traverse left
    inorder(root->left);

    // Traverse root
    printf("%d -> ", root->key);

    // Traverse right
    inorder(root->right);
  }
}

// Insert a node
struct node *insert(struct node *node, int key) {
  // Return a new node if the tree is empty
  if (node == NULL) return newNode(key);

  // Traverse to the right place and insert the node
  if (key < node->key)
    node->left = insert(node->left, key);
  else
    node->right = insert(node->right, key);

  return node;
}

// Find the inorder successor
struct node *minValueNode(struct node *node) {
  struct node *current = node;

  // Find the leftmost leaf
  while (current && current->left != NULL)
    current = current->left;

  return current;
}

// Deleting a node
struct node *deleteNode(struct node *root, int key) {
  // Return if the tree is empty
  if (root == NULL) return root;

  // Find the node to be deleted
  if (key < root->key)
    root->left = deleteNode(root->left, key);
  else if (key > root->key)
    root->right = deleteNode(root->right, key);

  else {
    // If the node is with only one child or no child
    if (root->left == NULL) {
      struct node *temp = root->right;
      free(root);
      return temp;
    } else if (root->right == NULL) {
      struct node *temp = root->left;
      free(root);
      return temp;
    }

    // If the node has two children
    struct node *temp = minValueNode(root->right);

    // Place the inorder successor in position of the node to be deleted
    root->key = temp->key;

    // Delete the inorder successor
    root->right = deleteNode(root->right, temp->key);
  }
  return root;
}

// Driver code
int main() {
  struct node *root = NULL;
  root = insert(root, 8);
  root = insert(root, 3);
  root = insert(root, 1);
  root = insert(root, 6);
  root = insert(root, 7);
  root = insert(root, 10);
  root = insert(root, 14);
  root = insert(root, 4);

  printf("Inorder traversal: ");
  inorder(root);

  printf("\nAfter deleting 10\n");
  root = deleteNode(root, 10);
  printf("Inorder traversal: ");
  inorder(root);
}

 

▶ 관련 링크

2021.11.18 - [알고리즘/개념] - 트리(Tree)란?