JAVA

• Java 로 Binary Search Tree 구현

구현

// BinaryTree.java
public class BinaryTree<E>{

  protected Node<E> root;

  protected int size = 0;

  protected INodeCreator creator = null;

  public BinaryTree(){
    root = null;
  }

  final public void insertLeft(E data, Node<E> node){
    if(node.left != null){
        System.out.println("왼쪽 노드가 이미 차있음");
        return ;
    }
    if(root == null){
        root = node;
    }
    Node<E> newNode = new Node<E>(data);
    node.left = newNode;
  }
  final public void insertRight(E data, Node<E> node){
    if(node.right != null){
        System.out.println("오른쪽 노드가 이미 차있음");
        return ;
    }
    if(root == null){
        root = node;
    }
    Node<E> newNode = new Node<E>(data);
    node.right = newNode;
  }

  protected int getMaxLevel(Node<E> node){
    if(node == null)
        return 0;
    return java.lang.Math.max(getMaxLevel(node.left), getMaxLevel(node.right)) + 1;
  }

  public void printPreOrder(){
    BinaryTreePrinter.printPreOrder(root);
  }
  public void printInOrder(){
    BinaryTreePrinter.printInOrder(root);
  }
  public void printPostOrder(){
    BinaryTreePrinter.printPostOrder(root);
  }
  public void printLevelOrder(){
    BinaryTreePrinter.printLevelOrder(root);
  }
  public void printBFS(){
    BinaryTreePrinter.printBFS(root);
  }
  public void print(){
    BinaryTreePrinter.print(root);
  }

  public static class Node<E>{
    // Inner class 에서는 private 라도 멤버 변수 접근 가능함!
    public E element;
    public Node<E> parent;
    public Node<E> left;
    public Node<E> right;

    public Node(){
        this.parent = null;
        this.left = null;
        this.right = null;
    }
    public Node(E element){
        this.parent = null;
        this.element = element;
        this.left = null;
        this.right = null;
    }
    public Node(E element,Node<E> parent){
        this.parent = parent;
        this.element = element;
        this.left = null;
        this.right = null;
    }
    public void visit(){
        System.out.print(element);
    }

  }
  protected static interface INodeCreator<E extends Comparable<E>> {
      public Node<E> createNewNode(E id,Node<E> parent);
  }
}

BST 구현

• BST 삭제는 생각보다 어려움! 꼭 기억~

// BinarySearchTree.java
public class BinarySearchTree<E extends Comparable<E>> extends BinaryTree<E> implements ITree<E>{
   protected enum Position {
      LEFT, RIGHT
  };
  public BinarySearchTree(){

  }
  public Node<E> getNode(E data){
    Node<E> node = root;
    while(node != null){
      if(data.compareTo(node.element) == 0){
        return node;
      }else if(data.compareTo(node.element) < 0){
        node = node.left;
      }else{
        node = node.right;
      }
    }
    return null;
  }
  protected Node<E> getLeafLeftNode(Node<E> node){
    Node<E> tNode = node;
    if(tNode == null)
      return tNode;
    while(tNode.left != null){
      tNode = tNode.left;
    }
    return tNode;
  }

  @SuppressWarnings("unchecked")
  @Override
  public boolean add(E data){
    Node<E> newNode = null;
    if(this.creator == null)
      newNode = new Node<E>(data);
    else
      newNode = this.creator.createNewNode(data, null);

    if(root == null){
      root = newNode;
      root.parent = null;
    }else{
      Node<E> parent;
      Node<E> t = root;
      int cmp;
      do{
        parent = t;
        cmp = data.compareTo(parent.element);
        if(cmp < 0){
          t = t.left;
        }else if(cmp > 0){
          t = t.right;
        }else{
          // 얼레는 그냥 덮어씌우는게 일반적인듯..?
          System.out.println("데이터 중복안됨");
          return false;
        }
      }while( t != null);
      if(cmp < 0){
        parent.left = newNode;
        newNode.parent = parent;
      }else{
        parent.right = newNode;
        newNode.parent = parent;
      }
    }
    return true;
  }

  @SuppressWarnings("unchecked")
  protected Node<E> addAndGetNode(E data){
    Node<E> newNode = null;
    if(this.creator == null)
      newNode = new Node<E>(data);
    else
      newNode = this.creator.createNewNode(data, null);
    if(root == null){
      root = newNode;
      root.parent = null;
    }
    insertNode(root, newNode);
    return newNode;
  }
  // recursive add
  private Node<E> insertNode(Node<E> currentParent, Node<E> newNode) {
    if (currentParent == null)
      return newNode;
    else if (newNode.element.compareTo(currentParent.element) > 0){
      currentParent.right = insertNode(currentParent.right, newNode);
      currentParent.right.parent = currentParent;
    }
    else if (newNode.element.compareTo(currentParent.element) < 0 ){
      currentParent.left = insertNode(currentParent.left, newNode);
      currentParent.left.parent = currentParent;
    }

    return currentParent;
  }
  @Override
  public E remove(E data){
    Node<E> removeNode = getNode(data);
    Node<E> replaceNode = getReplacementNode(removeNode);
    replaceNodeWithNode(removeNode, replaceNode);
    return data;
  }
  public Node<E> removeAndGetNode(E data){
    Node<E> removeNode = getNode(data);
    if(removeNode != null){
      Node<E> replaceNode = getReplacementNode(removeNode);
      replaceNodeWithNode(removeNode, replaceNode);
    }
    return removeNode;
  }
  protected Node<E> getReplacementNode(Node<E> nodeToRemoved) {
    Node<E> replaceNode = null;
    if(nodeToRemoved.left != null && nodeToRemoved.right == null){
      replaceNode = nodeToRemoved.left;
    }else if(nodeToRemoved.right != null && nodeToRemoved.left == null){
      replaceNode = nodeToRemoved.right;
    }else if(nodeToRemoved.left != null && nodeToRemoved.right != null){
      // 오른쪽 노드에서 가장 왼쪽에 있는 노드를 찾는다.
      // 왼쪽 노드에서 가장 오른쪽에 있는 노드를 찾아도 된다.
      replaceNode = getLeafLeftNode(nodeToRemoved.right);
      if(replaceNode == null){
        // 삭제할 노드에 오른쪽 노드가 왼쪽 노드가 없다면
        // 그냥 오른쪽 노드로 대신함
        replaceNode = nodeToRemoved.right;
      }
    }
    return replaceNode;
  }
  protected void replaceNodeWithNode(Node<E> nodeToRemoved, Node<E> replacementNode) {
    // leaf 노드를 삭제한다면 replacementNode 가 null 일수도 있다.
    if(replacementNode != null){
      // 대체 할 노드의 오른쪽 왼쪽을 바꾸기 전에 미리 저장해 놓는다. 처음에 대체할 노드의 오른쪽 왼쪽부터 바꾼다.
      // 1.왼쪽에 가장 오른쪽을 선택했을경우 데체할 노드의 왼쪽 자식은 있을수도 있다.
      Node<E> replacementNodeLeft = replacementNode.left;
      // 2.오른쪽에 가징왼쪽을 선택했을경우 대체할 노드의 오른쪽 자식은 있을수도 있다.
      Node<E> replacementNodeRight = replacementNode.right;

      // 대체할 노드 <-> 삭제할 노드의 양쪽 자식
      // ** 삭제할 노드와 대체할노드가 바로 붙어 있다면 삭제할 노드의 부모를 대체할노드로 바꿔주기만하면됨**
      // 삭제할 노드에 양쪽 자식을 대체할 노드에 넣어준다.
      Node<E> nodeToRemoveLeft = nodeToRemoved.left;
      // 삭제할 노드의 왼쪽이 있다면, **근데 삭제할노드의 왼쪽이 대체할노드가 아니라면**
      if(nodeToRemoveLeft != null && !nodeToRemoveLeft.equals(replacementNode)){
        replacementNode.left = nodeToRemoveLeft;
        nodeToRemoveLeft.parent = replacementNode;
      }
      Node<E> nodeToRemoveRight = nodeToRemoved.right;
      // 삭제할 노드의 오른쪽이 있다면, **근데 삭제할 노드의 오른쪽이 대체할 노드가 아니라면**
      if(nodeToRemoveRight != null && !nodeToRemoveRight.equals(replacementNode)){
        replacementNode.right = nodeToRemoveRight;
        nodeToRemoveRight.parent = replacementNode;
      }

      // 대체할 노드의 부모 <-> 대체할 노드의 자식 (대체할 노드가 빠지므로)
      // 삭제할 노드의 오른쪽 노드의 맨왼쪽 노드(대체할노드) 의 오른쪽 자식은 있을수도 있다.

      Node<E> replacementParent = replacementNode.parent;
      // 대체할 노드의 부모가 있고, **대체할 노드의 부모가 삭제할것은 아니라면**
      if(replacementParent != null && !replacementParent.equals(nodeToRemoved)){
        // 대체할 노드가 부모의 왼쪽이라면(1.오른쪽에서 가장 왼쪽을 선택했을경우)
        if(replacementParent.left != null && replacementParent.left.equals(replacementNode)){
          // 대체할 노드의 오른쪽을 대체할 노드의 부모의 왼쪽으로 연결해준다.
          replacementParent.left = replacementNodeRight;
          if(replacementNodeRight != null){
            // 만약 대체노드의 오른쪽이 자식이 있다면 대체할 노드의 오른쪽의 부모를 대체할 노드의 부모로
            replacementNodeRight.parent = replacementParent;
          }
        }else if(replacementParent.right != null && replacementParent.right.equals(replacementNode)){
          // 1.삭제할 노드의 오른쪽의 가징 왼쪽 선택했으므로 대체할 노드의 부모의 오른쪽에 있을일이 없다.
          replacementParent.right = replacementNodeLeft;
          if(replacementNodeLeft != null){
            replacementNodeLeft.parent = replacementParent;
          }
        }
      }
    }
    // 삭제할 노드의 부모 <-> 대체 노드
    Node<E> parent = nodeToRemoved.parent;
    if(parent == null){
      // 삭제할 노드가 루트 노드
      root = replacementNode;
      if(root != null)
        root.parent = null;
    }else if(parent.left != null && parent.left.equals(nodeToRemoved)){
      // 삭제할노드가 부모의 왼쪽 이라면
      parent.left = replacementNode;
      if(replacementNode != null)
        replacementNode.parent = parent;

    }else if(parent.right != null && parent.right.equals(nodeToRemoved)){
      // 삭제할노드가 부모의 오른쪽 이라면
      parent.right = replacementNode;
      if(replacementNode != null)
        replacementNode.parent = parent;
    }
  }

  public E remove2(E data){
    Node<E> removeNode = getNode(data);
    if(removeNode.left == null && removeNode.right == null){
      // leaf node
      Node<E> parent = removeNode.parent;
      if(parent.left == removeNode){
        parent.left = null;
      }else if(parent.right == removeNode){
        parent.right = null;
      }
      removeNode = null;
    }
    else if(removeNode.left != null && removeNode.right == null){
      // 자식이 한개밖에없다.
      Node<E> parent = removeNode.parent;
      Node<E> child = removeNode.left;
      if(parent.left == removeNode){
        parent.left = child;
      }else if(parent.right == removeNode){
        parent.right = child;
      }
      removeNode = null;
    }
    else if(removeNode.right != null && removeNode.left == null){
      // 자식이 한개밖에없다.
      Node<E> parent = removeNode.parent;
      Node<E> child = removeNode.right;
      if(parent.left == removeNode){
        parent.left = child;
      }else if(parent.right == removeNode){
        parent.right = child;
      }
      removeNode = null;
    }
    else if(removeNode.right != null && removeNode.left != null){

      Node<E> parent = removeNode.parent;
      Node<E> replaceNode = getLeafLeftNode(removeNode.right);
      //System.out.println(replaceNode.element);

      if(parent.left == removeNode){
        parent.left = replaceNode;
        replaceNode.left = removeNode.left;
        if(replaceNode.right == null){
          if(replaceNode != removeNode.right)
            replaceNode.right = removeNode.right;
        }
        replaceNode.parent.left = null;
      }else if(parent.right == removeNode){
        parent.right = replaceNode;
        replaceNode.left = removeNode.left;
        // 대신할 노드에 왼쪽은 항상 없지만 오른쪽은 있을수도 있다.
        if(replaceNode.right == null){
          // 삭제할 노드에 오른쪽 노드가 대신할노드랑 같으면 서로 참조하게됨
          if(replaceNode != removeNode.right)
            replaceNode.right = removeNode.right;
        }
        replaceNode.parent.left = null;
      }
      removeNode = null;
    }

    return data;
  }

  public void rotateLeft(Node<E> node){
    System.out.println("ROTATE LEFT AT " + node);
    Node<E> parent = node.parent;
    Position parentPosition = null;
    if(parent != null){
      if(node.equals(parent.left)){
        parentPosition = Position.LEFT;
      }else{
        parentPosition = Position.RIGHT;
      }
    }
    Node<E> greater = node.right;
    Node<E> lesser = greater.left;
    node.right = null;
    greater.left = node;
    node.parent = greater;
    node.right = lesser;
    if(lesser != null)
      lesser.parent = node;

    if(parentPosition != null){
      if(parentPosition == Position.LEFT){
        parent.left = greater;
      }else{
        parent.right = greater;
      }
      greater.parent = parent;
    }else{
      root = greater;
      greater.parent = null;
    }
  }

  public void rotateRight(Node<E> node){
    System.out.println("ROTATE RIGHT AT " + node);
    Node<E> parent = node.parent;
    Position parentPosition = null;
    if(parent != null){
      if(node.equals(parent.left)){
        parentPosition = Position.LEFT;
      }else{
        parentPosition = Position.RIGHT;
      }
    }
    Node<E> lesser = node.left;
    Node<E> greater = lesser.right;
    node.left = null;
    lesser.right = node;
    node.parent = lesser;
    node.left = greater;
    if(greater != null)
      greater.parent = node;

    if(parentPosition != null){
      if(parentPosition == Position.LEFT){
        parent.left = lesser;
      }else{
        parent.right = lesser;
      }
      lesser.parent = parent;
    }else{
      root = lesser;
      lesser.parent = null;
    }
  }
}

public class BinaryTreePrinter{
  static public <T> void printPreOrder(BinaryTree.Node<T> node){
    if(node == null){
      return;
    }
    node.visit();
    System.out.print(" ");
    printPreOrder(node.left);
    printPreOrder(node.right);
  }

  static public <T> void printInOrder(BinaryTree.Node<T> node){
    if(node == null){
      return;
    }
    printInOrder(node.left);
    node.visit();
    System.out.print(" ");
    printInOrder(node.right);
  }

  static public <T> void printPostOrder(BinaryTree.Node<T> node){
    if(node == null){
      return;
    }
    printPostOrder(node.left);
    printPostOrder(node.right);
    node.visit();
    System.out.print(" ");
  }

  static public <T>  void printLevelOrder(BinaryTree.Node<T> node){
    // 레벨 별로 순회 하는 방법
    java.util.Queue<BinaryTree.Node<T>> queue = new java.util.LinkedList<BinaryTree.Node<T>>();
    queue.offer(node);
    while(queue.peek() != null){
        BinaryTree.Node<T> t = queue.poll();
        t.visit();
        System.out.print(" ");
        if(t.left != null){
            queue.offer(t.left);
        }
        if(t.right != null){
            queue.offer(t.right);
        }
    }
  }

  static public <T> void printBFS(BinaryTree.Node<T> node){
    java.util.Stack<BinaryTree.Node<T>> stack = new java.util.Stack<BinaryTree.Node<T>>();
    stack.push(node);
    while(!stack.isEmpty()){
        BinaryTree.Node<T> t = stack.pop();
        t.visit();
        System.out.print(" ");
        if(t.right != null){
            stack.push(t.right);
        }
        if(t.left != null){
            stack.push(t.left);
        }

    }
  }
  static public <T> void printInternal(java.util.List<BinaryTree.Node<T>> nodes,int level, int maxLevel){
    if (nodes.isEmpty() || isAllElementsNull(nodes))
      return;
    int floor = maxLevel - level;
    int endgeLines = (int) Math.pow(2, (Math.max(floor - 1, 0)));
    int firstSpaces = (int) Math.pow(2, (floor)) - 1;
    int betweenSpaces = (int) Math.pow(2, (floor + 1)) - 1;

    printWhitespaces(firstSpaces);

    java.util.List<BinaryTree.Node<T>> newNodes = new java.util.ArrayList<BinaryTree.Node<T>>();
    for (BinaryTree.Node<T> node : nodes) {
        if (node != null) {
            System.out.print(node.element);
            newNodes.add(node.left);
            newNodes.add(node.right);
        } else {
            newNodes.add(null);
            newNodes.add(null);
            System.out.print(" ");
        }

        printWhitespaces(betweenSpaces);
    }
    System.out.println("");

    for (int i = 1; i <= endgeLines; i++) {
        for (int j = 0; j < nodes.size(); j++) {
            printWhitespaces(firstSpaces - i);
            if (nodes.get(j) == null) {
                printWhitespaces(endgeLines + endgeLines + i + 1);
                continue;
            }

            if (nodes.get(j).left != null)
                System.out.print("/");
            else
                printWhitespaces(1);

            printWhitespaces(i + i - 1);

            if (nodes.get(j).right != null)
                System.out.print("\\");
            else
                printWhitespaces(1);

            printWhitespaces(endgeLines + endgeLines - i);
        }

        System.out.println("");
    }

    printInternal(newNodes, level + 1, maxLevel);
  }
  static public <T> void print(BinaryTree.Node<T> node){
    int maxLevel = getMaxLevel(node);
    java.util.LinkedList<BinaryTree.Node<T>> rootList = new java.util.LinkedList<BinaryTree.Node<T>>();
    rootList.add(node);
    printInternal(rootList,1,maxLevel);
  }

  static public <T> void printTest(BinaryTree.Node<T> node){
    java.util.LinkedList<BinaryTree.Node<T>> curLevel = new java.util.LinkedList<BinaryTree.Node<T>>();
    java.util.LinkedList<BinaryTree.Node<T>> nextLevel = curLevel;

    StringBuilder sb = new StringBuilder();
    curLevel.add(node);
    sb.append(node.element + "\n");

    while(nextLevel.size() > 0){
        nextLevel = new java.util.LinkedList<BinaryTree.Node<T>>();
        for (int i = 0; i < curLevel.size(); i++){
            BinaryTree.Node<T> cur = curLevel.get(i);

            if (cur.left != null) {
                nextLevel.add(cur.left);
                sb.append(cur.left.element + " ");
            }
            if (cur.right != null) {
                nextLevel.add(cur.right);
                sb.append(cur.right.element + " ");
            }
        }
        if (nextLevel.size() > 0) {
            sb.append("\n");
            curLevel = nextLevel;
        }
    }
    System.out.println(sb.toString());
  }
  private static <T> boolean isAllElementsNull(java.util.List<T> list) {
      for (Object object : list) {
          if (object != null)
              return false;
      }
      return true;
  }
  private static <T> void printWhitespaces(int count) {
      for (int i = 0; i < count; i++)
          System.out.print(" ");
  }

  protected static <T> int getMaxLevel(BinaryTree.Node<T> node){
    if(node == null)
        return 0;
    return java.lang.Math.max(getMaxLevel(node.left), getMaxLevel(node.right)) + 1;
  }
}