AVL 트 리 구현 (전체 코드)

public class AvlTree<T extends Comparable<? super T>> {
  private static class AvlNode<T> {     } // AVL     
  
  private AvlNode<T> root; //          AVL 
  
  public void makeEmpty(){ root = null; }
  public boolean isEmpty(){ return root == null; }
  
  public int height() { return height(root); } //     
  
  public boolean contains(T t){ return contains(t, root); } //   
  public void insert(T t){ root = insert(t, root); } //   
  public void remove(T t){ root = remove(t, root); } //   (  boolean    contains  )
  
  private int height(AvlNode<T> root){     }
  private AvlNode<T> contains(T t, AvlNode<T>){     }
  private AvlNode<T> insert(T t, AvlNode<T>){     }
  private AvlNode<T> remove(T t, AvlNode<T>){     }
  private AvlNode<T> balance(AvlNode<T>){     }
  private AvlNode<T> rotateWithLeft(AvlNode<T>){     }
  private AvlNode<T> doubleWithLeft(AvlNode<T>){     }
  private AvlNode<T> rotateWithRight(AvlNode<T>){     }
  private AvlNode<T> doubleWithRight(AvlNode<T>){     }
}

private static class AvlNode<T> {
  T element;
  AvlNode<T> left;
  AvlNode<T> right;
  int height; //           ,      
  
  AvlNode(T t){ this(t,null,null); } 
  
  AvlNode(T t, AvlNode<T> le, AvlNode<T> ri){
    this.t = t;
    left = le; right = ri;
    height = 0; //           ,       (  /  )    
  }
}

private int height(AvlNode<T> root){
  return root==null?-1:root.height; // null     -1,       0
}

private boolean contains(T t, AvlNode<T> root){
  if(t == null)
    return false;
  
  int result = t.compareTo(root.element);
  
  if(result > 0)
    return contains(t, root.right);
  else if(result < 0)
    return contains(t, root.left);
  else
    return true;
}

private AvlNode<T> insert(T t, AvlNode<T> root){
  if(root == null)
    return new AvlNode<T>(t);
  
  int result = t.compareTo(root.element);
  
  if(result > 0)
    root.right = insert(t, root.right);
  else if(result < 0)
    root.left = insert(t, root.left);
  else {} // exist. do nothing.
    
  return balance(root); //       ,       (             )
}

private AvlNode<T> remove(T t, AvlNode<T> root){
  if(root == null)
    return null;
  
  int result = t.compareTo(root.element);
  
  if(result > 0)
    root.right = remove(t, root.right);
  else if(result < 0)
    root.left =  remove(t, root.left);
  else{
    if(root.left == null && root.right == null)
      return null;
    else if(root.left != null && root.right != null){
      root.element = findMin(root.right).element;
      root.right = remove(root.element, root.right);
    } else
      root = (root.left==null)?root.right:root.left; 
  }
  
  return balance(root); //         
}

private BinaryNode<T> findMin(BinaryNode<T> root){
  if(root == null)
    throw new Exception();
  
  if(root.left != null)
    return findMin(root.left);
  else
    return root;
}

private static final int ALLOWED_IMBALANCE = 1; //         
private AvlNode<T> balance(AvlNode<T> root){
  if(root == null)
	return null;
  
  if( height(root.left) - height(root.right) > ALLOWED_IMBALANCE){ 
    if(height(root.left.left) >= height(root.left.right)) //    :   
      // >=                  
      root = rotateWithLeft(root);
    else //     
      root = doubleWithLeft(root);
  } else if(height(root.right) - height(root.left) > ALLOWED_IMBALANCE){ 
    if(height(root.right.right) >= height(root.right.left)) //    :   
      root = rotateWithRight(root);
    else //     
      root = doubleWithRight(root);
  } else {} // balance.do nothing
  
  root.height = Math.max(height(root.left), height(root.right)) + 1; //     
  //        ,           ,    balance         
  
  return root;
}

private AvlNode<T> rotateWithLeft(AvlNode<T> k1){
  AvlNode<T> k2 = k1.left;
  k1.left = k2.right;
  k2.right = k1;
  //     
  k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
  k2.height = Math.max(height(k2.left), k1.height) + 1;
  
  return k2;
}

private AvlNode<T> rotateWithRight(AvlNode<T> k1){
  AvlNode<T> k2 = k1.right;
  k1.right = k2.left;
  k2.left = k1;
  //     
  k1.height = Math.max(height(k1.left), height(k1.right)) + 1;
  k2.height = Math.max(height(k2.right), k1.height) + 1;
  
  return k2;
}

private AvlNode<T> doubleWithLeft(AvlNode<T> k1){
  k1.left = rotateWithRight(k1.left);
  return rotateWithLeft(k1);
}

private AvlNode<T> doubleWithRight(AvlNode<T> k1){
  k1.right = rotateWithLeft(k1.right);
  return rotateWithRight(k1);
}

AvlNode:    height  ,    balance     .
--           Node   .   Tree   .Tree          Node   
--null    -1,  0;         0(    )
--          balance     (              ,      ),   .
--      ,           

Avl        :     (    )       .      (    )      ,             ,     .

      :   n  ( )    ( )     ,   1
balance:          ,  n               :
--  n           :   n    (   )
--  n           :   n    (   )
--  n           :    :  n      ,  n   .
--  n           :    :  n      ,  n