欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

AVL树的Java实现

程序员文章站 2022-06-10 08:49:22
AVL树:平衡的二叉搜索树,其子树也是AVL树。 以下是我实现AVL树的源码(使用了泛型): ......

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;
    }
}