AVLTree

AVLtree.java

public class AVLtree<T extends Comparable<? super T>>
{
    private class TreeNode {
        T data;
        TreeNode left, right;
        TreeNode(T data, TreeNode left, TreeNode right) {
            this.data = data;
            this.left = left;
            this.right = right;
        }
    }
    TreeNode root;
    public int height() {
        return height(root);
    }
    private int height(TreeNode n) {
        if (n == null) return 0;
        return 1 + Math.max(height(n.left), height(n.right));
    }
    int checkBalanceFactor(TreeNode n) {
        if ( n==null ) return 0;
        int PoopDawg = height(n.left)-height(n.right);
        return PoopDawg;
    }
    public void Balance(TreeNode n) {
        int BalanceFactor = checkBalanceFactor(n);
        int BalanceFactorRight = checkBalanceFactor(n.right);
        int BalanceFactorLeft = checkBalanceFactor(n.left);
        
        if(BalanceFactor==0 || BalanceFactor==-1 || BalanceFactor==1) {
            return;
        }
        if(BalanceFactor==-2) {
            LeftRotate(root);
            if(BalanceFactorRight==-1) {
                RightRotate(root);
            }else if(BalanceFactorRight==1) {
                RightRotate(n.right);
                LeftRotate(root);
            }
        } else if(BalanceFactor==2) {
            RightRotate(root);
            if(BalanceFactorLeft==-1) {
                LeftRotate(n.left);
                RightRotate(root);
            }else if(BalanceFactorRight==1) {
                RightRotate(root);
            }
        }
    }
    public void RightRotate(TreeNode n) {
        TreeNode pivot=root.left;
        root.left=pivot.right;
        pivot.right=root;
        root=pivot;
    }
    public void LeftRotate(TreeNode n) {
        TreeNode pivot=root.right;
        root.right=pivot.left;
        pivot.left=root;
        root=pivot;
    }
    public void insert(T data)
    {
        if(root==null) {
            root = new TreeNode(data, null, null);
            return;
        }
        TreeNode current=root;
        while(current!=null)
        {
            if(current.data.compareTo(data) > 0) {
                if(current.left==null) {
                    TreeNode newNode = new TreeNode(data, null, null);
                    current.left=newNode;
                    Balance(root);
                    break;
                } else {
                    current=current.left;
                    continue;
                }
            } else {
                if(current.right==null) {
                    TreeNode newNode2 = new TreeNode(data, null, null);
                    current.right=newNode2;
                    Balance(root);
                    break;
                } else {
                    current=current.right;
                    continue;
                }
            }
        }
    }
    T find(T data) {
        TreeNode n = root;
        while (n != null) {
            int c = data.compareTo(n.data);
            if (c == 0) return n.data;
            else if (c < 0) n = n.left;
            else if (c > 0) n = n.right;
        }
        return null;
    }
    // return the minimum value in the subtree rooted at n
    TreeNode findMin(TreeNode n) {
        if (n.left == null) return n;
        else return findMin(n.left);
    }
    // driver method
    void remove(T data) {
        if (root == null) return;
        root = remove(data, root);
        Balance(root);
    }
    TreeNode remove(T data, TreeNode n) {
        int c = data.compareTo(n.data);
        if (c < 0) {
            n.left = remove(data, n.left);
        } else if (c > 0) {
            n.right = remove(data, n.right);
        } else if (c == 0) {
            if (n.left == null) {
                return n.right;
            } else if (n.right == null) {
                return n.left;
            } else {
                n.data = findMin(n.right).data;
                n.right = remove (n.data, n.right);
            }
        }
        return n;
    }
    void removeMin(TreeNode current) {
        TreeNode parent = null;
        while (current.left != null) {
            parent = current;
            current = current.left;
        }
        parent.left = current.right;
    }
    public String toString() {
        return _toString(root, 0);
    }
    private String _toString(TreeNode node, int indent) {
        if ( node == null )
            return "";

        StringBuffer indentString = new StringBuffer();
        for ( int i = 0; i < indent + 2; i++ ) {
            indentString.append(' ');
        }

        StringBuffer buffer = new StringBuffer();
        buffer.append(node.data.toString());
        buffer.append("\n" + indentString.toString());
        if ( node.left != null ) {
            buffer.append(_toString(node.left, indent + 2));
        } else {
            buffer.append("null");
        }

        buffer.append("\n" + indentString.toString());
        if ( node.right != null ) {
            buffer.append(_toString(node.right, indent + 2));
        } else {
            buffer.append("null");
        }
        return buffer.toString();
    }
    public static void main(String args[]) {
        AVLtree<Integer> tree = new AVLtree<Integer>();
        tree.insert(2);
        tree.insert(1);
        tree.insert(4);
        tree.insert(5);
        tree.insert(9);
        tree.insert(3);
        tree.insert(6);
        tree.insert(7);
        System.out.println(tree);
    }
}