이진 탐색 트리 Binary Search Tree : BST

/*
 * 이진탐색트리(Binary Search Tree : BST) 는 삽입, 삭제, 탐색에서 월등한 성능을 나타낸다.
 *
 * BST는 공백이 가능한 이진트리로서 공백이 아니라면 다음의 성질을 만족한다.
 * ①모든 원소는 키를 가지며, 어떤 두 원소도 동일한 키를 갖지 않는다.
 *   즉, 키는 유일한 값을 갖는다.
 * ②공백이 아닌 좌측 서브트리에 있는 키들은 그 서브트리의 루트의 키보다 작아야 한다.
 * ③공백이 아닌 우측 서브트리에 있는 키들은 그 서브트리의 루트의 키보다 커야 한다.
 * ④좌측과 우측 서브트리도 BST이다. 
 *
 *  높이가 h인  BST에 대해 탐색(search)를 사용하면 O(h)시간내에 탐색을 수행할 수 있다.
 *  높이가 h인  BST에 대해 key값의 노드를 삽입할 경우 탐색하는데 드는 시간 O(h)와
 *    알고리즘의 나머지 부분 O(1)의 시간이 필요하다.
 *    그러므로 전체 필요한 시간은  O(h) 이다.
 *  높이가 h인  BST에서 삭제 또한  O(h)시간내에 수행할 수 있다.
 */

import java.util.Random;

public class BinarySearchTree {

  static Node root;

  public static void main(String[] args) {
    Random r = new Random();
    // 랜덤으로 10개의 노드생성
    for (int i = 0; i < 10; i++) {
      int t = r.nextInt(100);
      System.out.print(t + " ");
      insertNode(root, t);
    }
    System.out.println();
    //  중위 순회하여 이진탐색트리를 구성하였는지 검사한다.
    // 정렬되어 있다면 이진탐색트리가 제대로 구성된 것이다.
    inOrder(root);
    System.out.println();

    // 랜덤으로 30개의 값을 만들어
    // BST에 같은 값의 노드가 있으면 삭제함.
    for (int i = 0; i < 30; i++) {
      int t = r.nextInt(100);
      //System.out.print(t + " ");
      if (deleteNode(root, root, t)) { // 트리에 삭제한 노드가 존재하면
        System.out.println(t + " was Deleted !!!");
        inOrder(root);
        System.out.println();
      } else {
        //System.out.println(" is Not dangled in the Tree !!!");
      }
    }
  }

  // 트리에서 key 값을 가진 노드를 찾는다.
  // 없을 경우 null을 반환한다.
  static Node search(Node n, int key) {
    while (n != null) {
      if (key == n.data)
        return n;
      if (key < n.data)
        n = n.left;
      else
        n = n.right;
    }
    return null;
  }

  // 트리 삽입을 위한 search 메쏘드
  // 트리가 공백이거나 val값의 노드가 존재하면 null을 반환
  // 아니면 마지막 검사한 노드 반환
  static Node modifiedSearch(Node n, int key) {
    if (n == null)
      return null;
    while (n != null) {
      if (key == n.data)
        return null;
      if (key < n.data) {
        if (n.left == null)
          return n;
        else
          n = n.left;
      } else {
        if (n.right == null)
          return n;
        else
          n = n.right;
      }
    }
    return null;
  }

  // BST 노드 생성
  static void insertNode(Node n, int key) {
    Node temp = modifiedSearch(n, key);
    if (temp != null || n == null) { // num이 트리내에 없을 경우
      Node node = new Node(null, key, null);
      if (n != null) { // temp의 자식으로 삽입한다.
        if (key < temp.data)
          temp.left = node;
        else
          temp.right = node;
      } else {
        root = node; //공백트리이면 루트로 만든다.
      }
    }
  }

 

  // BST 노드 삭제
  static boolean deleteNode(Node parent, Node current, int key) {
    boolean isLeftChild = true;
    if (current == null)
      return false; //삭제할 노드가 없음

    while (current.data != key) {
      parent = current;
      if (key < current.data) {
        isLeftChild = true;
        if (current.left == null) // 해당 노드가 트리에 존재하지 않음
          return false;
        current = current.left;
      } else {
        isLeftChild = false;
        if (current.right == null) // 해당 노드가 트리에 존재하지 않음
          return false;
        current = current.right;
      }
    } // end of while

    if (current.left == null && current.right == null) { // leaf인경우
      if (isLeftChild)
        parent.left = null;
      else
        parent.right = null;
    } else if (current.right == null) { // 좌측 child만 있을 경우
      if (current == root)
        root = current.left;
      else if (isLeftChild)
        parent.left = current.left;
      else
        parent.right = current.left;
    } else if (current.left == null) { // 우측 child만 있을 경우
      if (current == root)
        root = current.right;
      else if (isLeftChild)
        parent.left = current.right;
      else
        parent.right = current.right;
    } else { // 좌우측 child가 모두 존재할 경우
      Node leftMax = maxNode(current.left);
      current.data = leftMax.data;
      deleteNode(current, current.left, current.data); // recursive call
    }
    return true;
  }

  // 특정 노드이하 가장 큰 값을 가지는 노드를 찾는다.
  static Node maxNode(Node n) {
    Node max = n;
    while (max.right != null) {
      max = max.right;
    }
    return max;
  }

  //중위순회
  static void inOrder(Node n) {
    if (n != null) {
      inOrder(n.left);
      n.visit();
      inOrder(n.right);
    }
  }

}

class Node {
  Node left;
  int data;
  Node right;

  Node(Node left, int data, Node right) {
    this.left = left;
    this.data = data;
    this.right = right;
  }

  void visit() {
    System.out.print(data + " ");
  }
}