AVL树

亦凉 2022-06-03 07:47 177阅读 0赞

package avl;
    
    /**
     * Created by long.chen  on 2017/12/21.
     * 平衡二叉树
     */
    public class AVLTree<T extends Comparable<T>> {//泛型
        private AVLTreeNode<T> root;//根节点
    
        class AVLTreeNode<T extends Comparable<T>> {
            T key;//键值
            int height;//高度
            AVLTreeNode<T> left;//左子树
            AVLTreeNode<T> right;//右字树
    
            public AVLTreeNode(T key, AVLTreeNode<T> left, AVLTreeNode<T> right) {
                this.key = key;
                this.left = left;
                this.right = right;
                this.height = -1;//定义空树的深度为-1
            }
        }
    
        public AVLTree() {
            root = null;
        }
    
        /**
         * 新建AVL树,或者插入节点->就是new 一个新的节点 然后放置合适的位置进而调节平衡树
         */
        private AVLTreeNode<T> insert(AVLTreeNode<T> tree, T key) {
            if (tree == null) {
                //新建树
    //            System.out.println("新建AVLTree!");
                tree = new AVLTreeNode<>(key, null, null);
                if (tree == null) {
                    System.out.println("创建AVLTree 失败");
                    return null;
                }
            } else {
                //插入节点
                int temp = key.compareTo(tree.key);
                //temp < 0 ,插入左节点 ;> 0 右节点 ;=0 不添加
                if (temp < 0) {
                    tree.left = insert(tree.left, key);
                    if (height(tree.left) - height(tree.right) == 2) {//失衡
                        if (key.compareTo(tree.left.key) < 0)
                            tree = leftleftRotation(tree);
                        else
                            tree = leftrightRatotion(tree);
                    }
                } else if (temp == 0) {
                    System.out.println("节点相同，不添加");
                } else {//  >0
                    tree.right = insert(tree.right, key);
                    if (height(tree.right) - height(tree.left) == 2) {
                        if (key.compareTo(tree.right.key) > 0)
                            tree = rightrightRotation(tree);
                        else
                            tree = rightleftRaration(tree);
                    }
                }
            }
            tree.height = max(height(tree.left), height(tree.right)) + 1;
            return tree;
        }
    
        public void insert(T key) {
            root = insert(root, key);
    
        }
    
        /**
         * 删除节点
         */
        private AVLTreeNode<T> delete(AVLTreeNode<T> tree, AVLTreeNode<T> delteTree) {
            if (tree == null || delteTree == null) {
                return null;
            }
            int temp = delteTree.key.compareTo(tree.key);
            if (temp < 0) {//delteTree 在根节点的左侧
                tree.left = delete(tree.left, delteTree);
                if (height(tree.right) - height(tree.left) == 2) {
                    if (height(tree.right.left) > height(tree.right.right)) {
                        tree = rightleftRaration(tree);
                    } else {
                        tree = rightrightRotation(tree);
                    }
                }
            } else if (temp > 0) {
                tree.right = delete(tree.right, delteTree);
                if (height(tree.left) - height(tree.right) == 2)
                    if (height(tree.left.left) > height(tree.left.right))
                        tree = leftleftRotation(tree);
                    else
                        tree = leftrightRatotion(tree);
            } else {//删除的key
                if (tree.left != null && tree.right != null) {
                    if (height(tree.left) > height(tree.right)) {
                        AVLTreeNode<T> maxTree = maxKey(tree.left);
                        tree.key = maxTree.key;
                        tree.left = delete(tree.left, maxTree);
                    } else {
                        AVLTreeNode<T> minTree = minKey(tree.right);
                        tree.key = minTree.key;
                        tree.right = delete(tree.right, minTree);
                    }
                } else {
                    AVLTreeNode<T> tmp = tree;
                    tree = (tree.left != null) ? tree.left : tree.right;
                    tmp = null;
                }
            }
            return tree;
        }
    
        public void delete(T key) {
            AVLTreeNode<T> tree;
            if ((tree = search(root, key)) != null)
                root = delete(root, tree);
        }
    
        //打印二叉树
        private void printAVLTree(AVLTreeNode<T> tree, T key, int direction) {
            if (tree != null) {
                if (direction == 0) {
                    System.out.printf("%2d is root\n", tree.key, key);
                } else
                    System.out.printf("%2d is %2d's %6s child\n", tree.key, key, direction == 1 ? "right" : "left");
                printAVLTree(tree.left, tree.key, -1);
                printAVLTree(tree.right, tree.key, 1);
            }
        }
    
        public void printAVLTree() {
            if (root != null)
                printAVLTree(root, root.key, 0);
        }
    
        //查找节点
        private AVLTreeNode<T> search(AVLTreeNode<T> tree, T key) {
            if (tree == null)
                return null;
            int temp = key.compareTo(tree.key);
            if (temp < 0) {
                return search(tree.left, key);
            } else if (temp > 0) {
                return search(tree.right, key);
            } else
                return tree;
        }
    
        public AVLTreeNode<T> search(T key) {
            return search(root, key);
        }
    
        //查找AVL最小的节点
        private AVLTreeNode<T> minKey(AVLTreeNode<T> tree) {
            if (tree == null)
                return null;
            while (tree.left != null)
                tree = tree.left;
            return tree;
        }
    
        public T minKey() {
            AVLTreeNode<T> treeNode = minKey(root);
            if (treeNode != null) {
                return treeNode.key;
            }
            return null;
        }
    
        //查找AVL 最大的节点
        private AVLTreeNode<T> maxKey(AVLTreeNode<T> tree) {
            if (tree == null)
                return null;
            while (tree.right != null)
                tree = tree.right;
            return tree;
        }
    
        public T maxKey() {
            AVLTreeNode<T> treeNode = maxKey(root);
            if (treeNode != null) {
                return treeNode.key;
            }
            return null;
        }
    
        //Tree height
        private int height(AVLTreeNode<T> tree) {
            if (tree != null) {
                return tree.height;
            }
            return -1;
        }
    
        public int height() {
            return height(root);
        }
    
        //比较大小 计算高度
        public int max(int a, int b) {
            return a > b ? a : b;
        }
    
        //LL 旋转 k->发生失衡的节点  返回值k1->根节点
        private AVLTreeNode<T> leftleftRotation(AVLTreeNode<T> k) {
            AVLTreeNode<T> k1;
            k1 = k.left;
            k.left = k1.right;
            k1.right = k;
            k.height = max(height(k.left), height(k.right)) + 1;
            k1.height = max(height(k1.left), k.height) + 1;
            return k1;
        }
    
        //RR 旋转
        private AVLTreeNode<T> rightrightRotation(AVLTreeNode<T> k) {
            AVLTreeNode<T> k1;
            k1 = k.right;
            k.right = k1.left;
            k1.left = k;
            k.height = max(height(k.left), height(k.right)) + 1;
            k1.height = max(height(k1.right), k.height) + 1;
            return k1;
        }
    
        //LR旋转
        private AVLTreeNode<T> leftrightRatotion(AVLTreeNode<T> k) {
            AVLTreeNode<T> k1;
            k.left = rightrightRotation(k.left);
            k1 = leftleftRotation(k);
            return k1;
        }
    
        //RL旋转
        private AVLTreeNode<T> rightleftRaration(AVLTreeNode<T> k) {
            AVLTreeNode<T> k1;
            k.right = leftleftRotation(k.right);
            k1 = rightrightRotation(k);
            return k1;
        }
    
        private static int arr[] = {3, 2, 1, 4, 5, 6, 7, 16, 15, 14, 13, 12, 11, 10, 8, 9};//,
    
        public static void main(String[] args) {
            int i;
            AVLTree<Integer> tree = new AVLTree<Integer>();
            System.out.printf("== 依次添加: ");
            for (i = 0; i < arr.length; i++) {
                System.out.printf("%d ", arr[i]);
                tree.insert(arr[i]);
            }
            System.out.printf("== 高度: %d\n", tree.height());
            tree.printAVLTree();
            tree.delete(11);
    //        tree.printAVLTree();
        }
    }