[CS] 자료구조 - 이진탐색트리 (Binary Search Tree)

이진탐색트리 (Binary Search Tree)

이진탐색트리는 이진트리의 한 종류로 아래와 같은 특징을 가진다.

 

• 각 노드의 키는 중복되지 않는다.
• 루트 노드의 왼쪽 서브 트리는 루트 노드의 키보다 작은 키를 갖는 노드들로 이루어져 있다.
• 루트 노드의 오른쪽 서브 트리는 루트 노드의 키보다 큰 키를 갖는 노드들로 이루어져 있다.
• 좌우 서브 트리도 모두 위와 같은 이진탐색트리의 특징을 갖는다.

내가 찾으려는 키가 루트 노드의 키보다 작으면 왼쪽 트리로, 크면 오른쪽 트리로 탐색하면 되기 때문에 기존의 이진트리보다 탐색이 빠르다는 장점이 있다.

 

이진탐색트리에서는 무조건 트리의 높이(h) 이하의 탐색이 이루어진다.

 

public class BinarySearchTree {
  public static void main(String[] args) {

  }

  Node root = null;

  public class Node {
    int value;
    Node leftNode;
    Node rightNode;

    public Node(int data) {
      this.value = data;
      this.leftNode = null;
      this.rightNode = null;
    }
  }

  public boolean searchNode(int data) {
    // root == null 이면 비어있는 트리!
    if (root == null) {
      return false;
    }

    Node findNode = root;

    while (findNode != null) {
      if (findNode.value == data) {
        return true;
        // data 가 root 보다 작으면 root 의 왼쪽 트리 root 로 다시 초기화 한 후 while 문!
      } else if (data < findNode.value) {
        findNode = findNode.leftNode;
        // data 가 root 보다 크다면 root 의 오른쪽 트리 root 로 다시 초기화 한 후 while 문!
      } else {
        findNode = findNode.rightNode;
      }
    }

    // while 문을 다 돌았으면 찾으려는 값이 없기때문에 false
    return false;
  }

  public boolean insertNode(int data) {
    // CASE 1 : Node 가 하나도 없을 때
    if (root == null) {
      root = new Node(data);
    } else {
      // CASE 2 : Node 가 하나 이상 들어가 있을 때
      Node findNode = root;
      while (true) {
        // CASE 2-1 : 현재 Node 의 왼쪽에 Node 가 insert
        if (data < findNode.value) {
          // 왼쪽 Node 가 존재하면 다시 한번 data 와 Node 의 value 비교!
          if (findNode.leftNode != null) {
            findNode = findNode.leftNode;
            // 왼쪽 Node 가 비어있으면 data 를 value 로 가지는 Node 생성 && while 문 break!!
          } else {
            findNode.leftNode = new Node(data);
            break;
          }
          // CASE 2-2 : 현재 Node 의 오른쪽에 Node 가 insert
        } else {
          // 오른쪽 Node 가 존재하면 다시 한번 data 와 Node 의 value 비교!
          if (findNode.rightNode != null) {
            findNode = findNode.rightNode;
            // 오른쪽 Node 가 비어있으면 data 를 value 로 가지는 Node 생성 && while 문 break!
          } else {
            findNode.rightNode = new Node(data);
            break;
          }
        }
      }
    }
    return true;
  }

}