[Java] Binary Search Tree

앞 포스팅에서 작성한 Tree의 비효율적인 문제를 개선하기 위해 생긴 이진 탐색 트리다.

트리는 여러 자식을 가질 수 있지만 이진 검색 트리에서는 Binary Tree의 개념을 사용하기 때문에

자식이 Left, Right만 존재한다. 이를 통해 Log_2 (N) 번만에 모든 수행을 끝낼 수 있다.

 

또, inorder를 수행 시 오름차순 정렬된 결과를 얻을 수 있다.

 

package com.study.datastructrue.nonlinear.binarysearchtree;

public class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
       this.value = value;
       left = null;
       right = null;
    }
}

 

기본 적인 노드 정보이다.

 

package com.study.datastructrue.nonlinear.binarysearchtree;

public class LinkedListBST {
    private Node root;
    private int size;

    public LinkedListBST() {
       this.root = null;
       this.size = 0;
    }

    public void add(int value) {
       this.root = addRecursive(root, value);
       this.size++;
    }

    private Node addRecursive(Node current, int value) {
       if (current == null) {
          return new Node(value);
       }

       if (value < current.value) {
          current.left = addRecursive(current.left, value);
       } else if (value > current.value) {
          current.right = addRecursive(current.right, value);
       }

       return current;
    }

    public boolean delete(int value) {
       int originalSize = size;
       this.root = deleteRecursive(root, value);
       return size < originalSize;
    }

    private Node deleteRecursive(Node current, int value) {
       if (current == null) {
          return null;
       }

       if (value == current.value) {
          if (current.left == null && current.right == null) {
             size--;
             return null;
          }

          if (current.left == null) {
             size--;
             return current.right;
          }

          if (current.right == null) {
             size--;
             return current.left;
          }

          int smallestValue = findSmallestValue(current.right);
          current.value = smallestValue;
          current.right = deleteRecursive(current.right, smallestValue);
          return current;
       }

       if (value < current.value) {
          current.left = deleteRecursive(current.left, value);
          return current;
       }

       current.right = deleteRecursive(current.right, value);
       return current;
    }

    private int findSmallestValue(Node root) {
       return root.left == null ? root.value : findSmallestValue(root.left);
    }

    public void printTree() {
       printTree(root, 0);
    }

    private void printTree(Node node, int level) {
       if (node == null) {
          return;
       }

       printTree(node.right, level + 1);

       if (level != 0) {
          for (int i = 0; i < level - 1; i++) {
             System.out.print("|\t");
          }
          System.out.println("|-------" + node.value);
       } else {
          System.out.println(node.value);
       }

       printTree(node.left, level + 1);
    }

    public void traverseInOrder() {
       traverseInOrder(root);
       System.out.println();
    }

    private void traverseInOrder(Node node) {
       if (node != null) {
          traverseInOrder(node.left);
          System.out.print(" " + node.value);
          traverseInOrder(node.right);
       }
    }

    public void traversePreOrder() {
       traversePreOrder(root);
       System.out.println();
    }
    private void traversePreOrder(Node node) {
       if (node != null) {
          System.out.print(" " + node.value);
          traversePreOrder(node.left);
          traversePreOrder(node.right);
       }
    }
    public void traversePostOrder() {
       traversePostOrder(root);
       System.out.println();
    }
    private void traversePostOrder(Node node) {
       if (node != null) {
          traversePostOrder(node.left);
          traversePostOrder(node.right);
          System.out.print(" " + node.value);
       }
    }

    public int size() {
       return size;
    }

}

 

1. 작은 값은 왼쪽 자식으로 큰 값은 오른쪽 자식으로 추가한다.

( 중복된 값을 허용할 경우, count를 사용하거나 여러 방법이 있다.)

2. 삭제 시 고려할 점이 있다.

- 삭제할 값을 찾았을 경우, 

1) 자식이 존재하지 않는다면 내가 지워진 것이니 null을 반환

2) 왼쪽 자식이 존재하지 않는다면 오른쪽 자식을 반환해주어서 Level을 맞춤.

3) 오른쪽 자식이 존재하지 않는다면 왼쪽 자식을 반환해주어서 Level을 맞춤.

4) 자식이 둘 다 존재한다면 큰 녀석 중 가장 작은 녀석으로 교체해주어야 함. inorder의 특성을 맞추기 위함.

 

TreePrint 및 PreOrder, InOrder, PostOrder 결과

4를 지운 후에도 InOrder 결과가 오름차순 인 것을 볼 수 있음.

 

package com.study.datastructrue.nonlinear.binarysearchtree;

public class ArrayBST {
    private int[] tree;
    private int size;

    public ArrayBST(int capacity) {
       tree = new int[capacity];
       size = 0;

       for (int i = 0; i < capacity; i++) {
          tree[i] = Integer.MIN_VALUE;
       }
    }

    public void add(int value) {
       if (size == 0) {
          tree[0] = value;
          size++;
       } else {
          addRecursive(0, value);
       }
    }

    private void addRecursive(int index, int value) {
       if (tree[index] == Integer.MIN_VALUE) {
          tree[index] = value;
          size++;
       } else if (value < tree[index]) {
          int leftChildIndex = 2 * index + 1;
          addRecursive(leftChildIndex, value);
       } else if (value > tree[index]) {
          int rightChildIndex = 2 * index + 2;
          addRecursive(rightChildIndex, value);
       }
    }
    public void printTree() {
       printTreeRecursive(0, 0);
    }

    private void printTreeRecursive(int index, int level) {
       if (index >= tree.length || tree[index] == Integer.MIN_VALUE) {
          return;
       }
       printTreeRecursive(2 * index + 2, level + 1);

       for (int i = 0; i < level; i++) {
          System.out.print("    ");
       }
       System.out.println(tree[index]);

       printTreeRecursive(2 * index + 1, level + 1);
    }

}

 

BST는 LinkedList 뿐만 아니라 Array로도 구현이 가능하다.

Array BST 실행결과

 

package com.study.datastructrue.nonlinear.binarysearchtree;

import java.util.TreeSet;

public class Main {

    public static void main(String[] args) {
       LinkedListBST bt = new LinkedListBST();

       bt.add(6);
       bt.add(4);
       bt.add(8);
       bt.add(3);
       bt.add(5);
       bt.add(7);
       bt.add(9);

       bt.printTree();
       bt.traversePreOrder();
       bt.traverseInOrder();
       bt.traversePostOrder();

       bt.delete(4);
       bt.printTree();
       bt.traverseInOrder();

       ArrayBST bst = new ArrayBST(10);
       bst.add(6);
       bst.add(4);
       bst.add(8);
       bst.add(3);
       bst.add(5);
       bst.add(7);
       bst.add(9);
       bst.printTree();
    }

}

 

Java에서는 Tree를 구현해 둔 것이 있는데 바로 TreeSet 과 TreeMap 이다. 

하지만 Java의 Tree는 Red-Black Tree로 자가균형트리라고도 한다.

이것은 이진 트리 종류 중 균형트리라는 자료구조 중 하나인데 다음 포스트에 설명하겠다.