AVL树的Java实现

avl树：平衡的二叉搜索树，其子树也是avl树。

以下是我实现avl树的源码（使用了泛型）：

import java.util.comparator;

public class avltree<t extends comparable<t>> {
    /*
    avl树：
    左右子树高度绝对值最多差1的二叉搜索树
    子树也是avl树
     */
    private node<t> root;
    class node<t extends comparable<t>>{
        t key;
        int height;
        node<t> left;
        node<t> right;

        public node(t key, int height, node<t> left, node<t> right) {
            this.key = key;
            this.height = height;
            this.left = left;
            this.right = right;
        }
        public node(t key){
            this.key = key;
            this.height = 0;
        }
    }
    public int getheight(node<t> node){
        return node == null ? 0 : node.height;
    }
    public node<t> ll(node<t> node){
        //左子树插入节点在左导致不平衡，需要旋转，以下不再赘述
        node<t> leftnode = node.left;
        node.left = leftnode.right;
        leftnode.right = node;
        node.height = math.max(node.left.height,node.right.height) + 1;
        leftnode.height = math.max(leftnode.left.height, leftnode.right.height) + 1;
        return leftnode;
    }
    public node<t> rr(node<t> node) {
        node<t> rightnode;
        rightnode = node.right;
        node.right = rightnode.left;
        rightnode.left = node;

        node.height = math.max( node.left.height, node.right.height) + 1;
        rightnode.height = math.max( rightnode.left.height, rightnode.right.height) + 1;
        return rightnode;
    }
    public node<t> lr(node<t> node){
        //lr先对左子树rr再对本树ll
        node.left = rr(node.left);
        return ll(node);
    }
    public node<t> rl(node<t> node){
        node.right = ll(node.right);
        return rr(node);
    }
    public node<t> insert(node<t> root,t key){
        /*
        插入：先判断插入点，再判断是否需要翻转
         */
        if(root == null){
            return new node<t>(key);
        }
        else{
            if(key.compareto(root.key)<0)
            //t是实现了comparable接口的，所以这里可以比较，但不能用大小于号
            {
                root.left = insert(root.left,key);
                if(root.left.height - root.right.height == 2){
                    if (key.compareto(root.left.key) < 0)
                        root = ll(root);
                    else
                        root = lr(root);
                }
            }else if(key.compareto(root.key)>0){
                root.right = insert(root.right,key);
                if(root.left.height - root.right.height == -2){
                    if (key.compareto(root.right.key) < 0)
                        root = rl(root);
                    else
                        root = rr(root);
                }
            }else{
                return root;//相同的节点不添加
            }
        }
        return root;
    }
    public node<t> delete(node<t> root,t key){
        /*
        删除：找到删除点，判断是否需要翻转
         */
        if(root == null || key == null){
            return root;
        }
        else{
            if(key.compareto(root.key)<0)
            //t是实现了comparable接口的，所以这里可以比较，但不能用大小于号
            {
                root.left = delete(root.left,key);
                if(root.left.height - root.right.height == -2){
                    node<t> rightnode = root.right;
                    if (rightnode.right.height>root.left.height)
                        root = rl(root);
                    else
                        root = rr(root);
                }
            }else if(key.compareto(root.key)>0){
                root.right = delete(root.right,key);
                if(root.left.height - root.right.height == 2){
                    node<t> leftnode = root.left;
                    if (leftnode.left.height>leftnode.right.height)
                        root = ll(root);
                    else
                        root = lr(root);
                }
            }else {
                //找到了要删除的节点
                if (root.left == null) root = root.right;
                else if (root.right == null) root = root.left;
                else {
                    if (root.left.height < root.right.height) {
                        node<t> tempnode = root.right;
                        while (tempnode.left != null) {
                            tempnode = tempnode.left;
                        }//为保证二叉树的平衡性、搜索性
                        //这里选择了高度较高的子树，选取中序遍历与root相邻的节点作为root，这样不会破坏搜索性
                        root.key = tempnode.key;
                        delete(tempnode, key);
                    } else {
                        node<t> tempnode = root.left;
                        while (tempnode.right != null) {
                            tempnode = tempnode.right;
                        }//为保证二叉树的平衡性、搜索性
                        //这里选择了高度较高的子树，选取中序遍历与root相邻的节点作为root
                        root.key = tempnode.key;
                        delete(tempnode, key);
                    }
                }
            }
        }
        return root;
    }
}