JAVA

• java 를 통한 AVL 구현
• AVL 회전
• RedBlack 이해

/// AVLTree.java
public class AVLTree<E extends Comparable<E>> extends BinarySearchTree<E> implements ITree<E>, BinaryTree.INodeCreator<E>{
  private enum Balance {
      LEFT_LEFT, LEFT_RIGHT, RIGHT_LEFT, RIGHT_RIGHT
  };

  public int height = 1;

  public AVLTree(){
    this.creator = this;
  }

  @Override
  public boolean add(E data){
    Node<E> t = super.addAndGetNode(data);
    AVLNode<E> addedNode = (AVLNode<E>)t;

    while(addedNode != null){
      addedNode.updateHeight();
      balnaceAfterInsert(addedNode);
      addedNode = (AVLNode<E>) addedNode.parent;

    }
    return true;
  }

  @Override
  public E remove(E data){
    Node<E> nodeToRemoved = this.getNode(data);
    if (nodeToRemoved != null) {
      Node<E> replacementNode = this.getReplacementNode(nodeToRemoved);

      // 삭제후에 제조정 되어할 노드
      AVLNode<E> nodeToRefactor = null;
      if (replacementNode != null) // 부모부터
          nodeToRefactor = (AVLNode<E>) replacementNode.parent;
      if (nodeToRefactor == null) // 대체할 노드가 널인경우는 leaf 노드 이므로 삭제할 노드의 부모부터 제조정
          nodeToRefactor = (AVLNode<E>) nodeToRemoved.parent;
      // 재조정 노드가 삭제할 노드랑 같다면 부모부터가 아닌 대체할 노드부터
      if (nodeToRefactor != null && nodeToRefactor.equals(nodeToRemoved))
          nodeToRefactor = (AVLNode<E>) replacementNode;

      replaceNodeWithNode(nodeToRemoved, replacementNode);

      if (nodeToRefactor != null) {
            while (nodeToRefactor != null) {
                nodeToRefactor.updateHeight();
                balanceAfterDelete(nodeToRefactor);
                nodeToRefactor = (AVLNode<E>) nodeToRefactor.parent;
            }
        }
    }
    return data;
  }

  private void balnaceAfterInsert(AVLNode<E> node){
    int balanceFactor = node.getBalanceFactor();

    if(balanceFactor < -1 || balanceFactor > 1){
      // 크기 차이가 2보다 커짐
      AVLNode<E> parent = null;
      AVLNode<E> child = null;
      Balance balnace = null;
      if(balanceFactor < 0){
        // 왼쪽에 추가됨
        parent = (AVLNode<E>)node.left;
        balanceFactor = parent.getBalanceFactor();
        if(balanceFactor < 0){
          // 추가된 노드가 부모의 왼쪽에
          child = (AVLNode<E>)parent.left;
          balnace = Balance.LEFT_LEFT;
        }else{
          // 추가된 노드에 부모의 오른쪽에
          child = (AVLNode<E>)parent.right;
          balnace = Balance.LEFT_RIGHT;
        }
      }else{
        // 오른쪽에 추가됨
        parent = (AVLNode<E>)node.right;
        balanceFactor = parent.getBalanceFactor();
        if(balanceFactor < 0 ){
          // 추가된 노드가 부모의 왼쪽에
          child = (AVLNode<E>)parent.left;
          balnace = Balance.RIGHT_LEFT;
        }else{
          child = (AVLNode<E>)parent.right;
          balnace = Balance.RIGHT_RIGHT;
        }
      }
      print();
      if(balnace == Balance.LEFT_LEFT){
        System.out.println("LL");
        rotateRight(node);
      }else if(balnace == Balance.LEFT_RIGHT){
        System.out.println("LR");
        rotateLeft(parent);
        print();
        rotateRight(node);
        print();
      }else if(balnace == Balance.RIGHT_LEFT){
        System.out.println("RL");
        rotateRight(parent);
        rotateLeft(node);
      }else if(balnace == Balance.RIGHT_RIGHT){
        System.out.println("RR");
        rotateLeft(node);
      }
      print();
      node.updateHeight();
      child.updateHeight();
      parent.updateHeight();
    }
  }

  private void balanceAfterDelete(AVLNode<E> node) {
    int balanceFactor = node.getBalanceFactor();
    if (balanceFactor == -2 || balanceFactor == 2) {
      // TODO
      if (balanceFactor == -2) {
        // 왼쪽이 더 높이가 높다
        // 1. (LL) 왼쪽 자식의 왼쪽이 높이가 더 높다면 => 오른쪽 회전(노드) => 노드, 노드의 부모 높이 재조정
        // 2. (LR) 왼쪽 자식의 오른쪽이 높이가 더 높다면 => 왼쪽 회전(왼쪽자식),오른쪽회전(노드) => 노드의 부모, 노드의 양쪽자식 높이 재조정

      }
      else if(balanceFactor == 2){
        // 오른쪽이 더 높이가 높다.
        // 3. (RR) 오른쪽 자식의 오른쪽이 높이가 더 높다면 => 왼쪽 회전(노드) => 노드, 노드의 부모 높이 재조정
        // 4. (RLL) 오른쪽 자식의 왼쪽이 높이가 더 높다면 => 오른쪽 회전(오른쪽),왼쪽회전(노드) => 노드의 부모, 노드의 양쪽자식 높이 재조정
      }
    }
  }
  @Override
  public Node<E> createNewNode(E element, Node<E> parent) {
      return (new AVLNode<E>(element, parent));
  }

  protected static class AVLNode<E extends Comparable<E>> extends Node<E>{
    public int height = 1;

    protected AVLNode(E element,Node<E> parent) {
        super(element, parent);
    }

    protected void updateHeight() {
        int leftHeight = 0;
        int rightHeight = 0;
        if (left != null) {
            AVLNode<E> leftNode = (AVLNode<E>) left;
            leftHeight = leftNode.height;
        }
        if (right != null) {
            AVLNode<E> rightNode = (AVLNode<E>) right;
            rightHeight = rightNode.height;
        }

        if (leftHeight > rightHeight) {
            this.height = leftHeight + 1;
        } else {
            this.height = rightHeight + 1;
        }
    }

    protected int getBalanceFactor(){
        int leftHeight = 0;
        int rightHeight = 0;
        if(this.left != null){
          AVLNode<E> avlNode = (AVLNode<E>)left;
          leftHeight = avlNode.height;
        }
        if(this.right != null){
          AVLNode<E> avlNode = (AVLNode<E>)right;
          rightHeight = avlNode.height;
        }
        return rightHeight-leftHeight;
    }
    @Override
    public String toString(){
      return "element : " + element +" : height : "+ height+ " balanceFactor : " + getBalanceFactor();
    }
  }
}

public class RedBlackTree<E extends Comparable<E>> extends BinarySearchTree<E> implements ITree<E>, BinaryTree.INodeCreator<E>{
  protected static final boolean BLACK = false;
  protected static final boolean RED = true;

  public RedBlackTree() {
      this.creator = this;
  }
  @Override
  public boolean add(E data){
    RedBlackNode<E> nodeAdded = null;
    boolean added = false;
    if(root == null){
      root = this.creator.createNewNode(data, null);
      ((RedBlackNode<E>) root).color = BLACK;
      root.left = this.creator.createNewNode(null, root);
      ((RedBlackNode<E>) root.left).color = BLACK;
      root.right = this.creator.createNewNode(null, root);
      ((RedBlackNode<E>) root.right).color = BLACK;

      nodeAdded = (RedBlackNode<E>) root;
      added = true;
    }else{
      Node<E> node = root;
      while (node != null) {
        if (node.element == null) {
          node.element = data;
          ((RedBlackNode<E>) node).color = RED;
          node.left = this.creator.createNewNode(null, node);
          ((RedBlackNode<E>) node.left).color = BLACK;
          node.right = this.creator.createNewNode(null, node);
          ((RedBlackNode<E>) node.right).color = BLACK;
          nodeAdded = (RedBlackNode<E>) node;
          added = true;
          break;
        }else if (data.compareTo(node.element) <= 0) {
            node = node.left;
        } else {
            node = node.right;
        }
      }
    }
    if (added == true) {
        balanceAfterInsert(nodeAdded);
    }
    return true;
  }
  private void balanceAfterInsert(RedBlackNode<E> node) {
    RedBlackNode<E> parent = (RedBlackNode<E>) node.parent;

    if (parent == null) {
      // 1.현재노드의 루트
      node.color = BLACK;
      return;
    }
    if (parent.color == BLACK) {
      // 2. 현재노드의 부모가 블랙 => 문제없다.
      return;
    }
    RedBlackNode<E> grandParent = node.getGrandParent();
    RedBlackNode<E> uncle = node.getUncle();
    if (parent.color == RED && uncle.color == RED) {
        // 3. 부모와 삼춘이 모두 RED => 두사람 모두 블랙이되고 할머니를 레드로
        parent.color = BLACK;
        uncle.color = BLACK;
        if (grandParent != null) {
            grandParent.color = RED;
            balanceAfterInsert(grandParent);
        }
    } else {
        if (parent.color == RED && uncle.color == BLACK) {
            // 4. 부모는 레드 삼촌은 블랙
            // 부모의 오른쪽에 있는 노드라면, 엄마가 할머니의 왼쪽에 있다면
            if (node.equals(parent.right) && parent.equals(grandParent.left)) {
                // right-left
                rotateLeft(parent);
                node = (RedBlackNode<E>) node.left;

                grandParent = node.getGrandParent();
                parent = (RedBlackNode<E>) node.parent;
                uncle = node.getUncle();
            } else if (node.equals(parent.left) && parent.equals(grandParent.right)) {
                // left-right
                rotateRight(parent);
                node = (RedBlackNode<E>) node.right;

                grandParent = node.getGrandParent();
                parent = (RedBlackNode<E>) node.parent;
                uncle = node.getUncle();
            }
        }

        if (parent.color == RED && uncle.color == BLACK) {
            // 5. 부모가 레드 삼촌이 블랙
            parent.color = BLACK;
            grandParent.color = RED;
            if (node.equals(parent.left) && parent.equals(grandParent.left)) {
                // left-left
                rotateRight(grandParent);
            } else if (node.equals(parent.right) && parent.equals(grandParent.right)) {
                // right-right
                rotateLeft(grandParent);
            }
        }
    }
  }
  @Override
  public Node<E> createNewNode(E element, Node<E> parent) {
      return (new RedBlackNode<E>(element, parent, BLACK));
  }
  protected static class RedBlackNode<E extends Comparable<E>> extends Node<E> {
    protected boolean color = BLACK;

    protected RedBlackNode(E element, Node<E> parent,boolean color) {
        super(element, parent);
        this.color = color;
    }
    protected RedBlackNode<E> getGrandParent() {
        if (parent == null || parent.parent == null) return null;
        return (RedBlackNode<E>) parent.parent;
    }

    protected RedBlackNode<E> getUncle() {
        RedBlackNode<E> grandParent = getGrandParent();
        if (grandParent == null) return null;
        if (grandParent.left != null && grandParent.left.equals(parent)) {
            // 부모에가 할머니에 왼쪽에 있다면 => 삼촌은 오른쪽
            return (RedBlackNode<E>) grandParent.right;
        } else if (grandParent.right != null && grandParent.right.equals(parent)) {
            // 부모에가 할머니에 오른쪽에 있다면 => 삼촌은 왼쪽
            return (RedBlackNode<E>) grandParent.left;
        }
        return null;
    }

    protected RedBlackNode<E> getSibling() {
        if (parent == null) return null;
        if (parent.left.equals(this)) {
            // 내가 부모의 왼쪽이라면 형재자매는 오른쪽
            return (RedBlackNode<E>) parent.right;
        } else if (parent.right.equals(this)) {
            // 내가 부모의 오른쪽이라면 형재자매는 왼쪽
            return (RedBlackNode<E>) parent.left;
        } else {
            System.err.println("opps no sibling");
        }
        return null;
    }

    protected boolean isLeaf() {
        // RedBlack 에서는 자식 모두 null 이면 leat
        if (left != null) return false;
        if (right != null) return false;
        return true;
    }

    @Override
    public String toString(){
      String colorStr = color == BLACK ? "BLACK" : "RED";
      return "element : " + element +" : COLOR : " + colorStr;
    }
  }

}