AVL树

今天药忘吃喽~ 2022-05-27 00:19 163阅读 0赞

一、AVL树继承自BinarySearchTree,

1，它是一棵平衡二叉树，他要求每个节点的左右子树的深度之差不能超过1。

2，每个节点都有一个平衡因子bf，取值为-1、0、1 。它的值等于右子树的深度减去左子树的深度。

3，有LL、RR、RL、LR四种旋转方式

import java.util.ArrayList;
    public class AVLTree<E extends Comparable<E>> extends BinarySearchTree<E>{
        public AVLTree(){}
    
        public AVLTree(E[] objects){
            super(objects);
        }
    
        public static class AVLTreeNode<E extends Comparable<E>> extends BinarySearchTree.TreeNode<E>{
            protected int height = 0;
    
            public AVLTreeNode(E element) {
                super(element);
            }
        }
    
        @Override
        protected AVLTreeNode<E> createNewNode(E e) {
            return new AVLTreeNode<>(e);
        }
    
        @Override
        public boolean insert(E e) {
            boolean successful = super.insert(e);
            if(!successful)
                return false;
            else
                balancePath(e);
            return true;
        }
    
        private void updateHeight(AVLTreeNode<E> node){//更新节点的高度
            if(node.leftNode==null && node.rightNode == null)
                node.height = 0;
            else if (node.leftNode == null)
                node.height = 1 + ((AVLTreeNode<E>)node.rightNode).height; // 注意括号
            else if (node.rightNode == null)
                node.height = 1+ ((AVLTreeNode<E>)node.leftNode).height;
            else
                node.height = 1 + Math.max(((AVLTreeNode<E>)node.rightNode).height,((AVLTreeNode<E>)node.leftNode).height);
        }
    
        private void balancePath(E e){//将该节点一直到根节点路径上的所有节点平衡
            ArrayList<TreeNode<E>> path = path(e);
            for(int i=0;i<path.size();i++){
                AVLTreeNode<E> A = (AVLTreeNode<E>)path.get(i);
                updateHeight(A);
                AVLTreeNode<E> parent = A==root ? null : (AVLTreeNode<E>)path.get(i-1);
                switch (balanceFactor(A)){
                    case -2:
                        if (balanceFactor((AVLTreeNode<E>) A.leftNode) <= 0)
                            balanceLL(A,parent);
                        else
                            balbanceLR(A,parent);
                    case +2:
                        if (balanceFactor((AVLTreeNode<E>) A.rightNode) <= 0)
                            balanceRL(A,parent);
                        else
                            balanceRR(A,parent);
                }
            }
        }
    
        private int balanceFactor(AVLTreeNode<E> node){//获取节点的平衡因子
            if (node.leftNode == null)
                return +node.height;
            else if(node.rightNode == null)
                return -node.height;
            else return ((AVLTreeNode<E>)node.rightNode).height - ((AVLTreeNode<E>)node.leftNode).height;
        }
    
        private void balanceLL(AVLTreeNode<E> A, AVLTreeNode<E> parent){
            AVLTreeNode<E> B = (AVLTreeNode<E>)A.leftNode;
            if (A == root)
                root = B;
            else {
                if(parent.leftNode == A)
                    parent.leftNode = B;
                else
                    parent.rightNode =B;
            }
            A.leftNode = B.rightNode;
            B.rightNode = A;
            updateHeight(A);
            updateHeight(B);
        }
    
        private void balanceRR(AVLTreeNode<E> A, AVLTreeNode<E> parent){
            AVLTreeNode<E> B = (AVLTreeNode<E>)A.rightNode;
    
            if (A == root)
                root = B;
            else {
                if(parent.leftNode == A)
                    parent.leftNode = B;
                else
                    parent.rightNode =B;
            }
            A.rightNode = B.leftNode;
            B.leftNode = A;
            updateHeight(A);
            updateHeight(B);
        }
    
        private void balanceRL(AVLTreeNode<E> A, AVLTreeNode<E> parent){
            AVLTreeNode<E> B = (AVLTreeNode<E>)A.rightNode;
            AVLTreeNode<E> C = (AVLTreeNode<E>)B.leftNode;
            if (A == root)
                root = C;
            else {
                if(parent.leftNode == A)
                    parent.leftNode = C;
                else
                    parent.rightNode =C;
            }
            A.rightNode = C.leftNode;
            B.leftNode = C.rightNode;
            C.leftNode = A;
            C.rightNode = B;
            updateHeight(A);
            updateHeight(B);
            updateHeight(C);
        }
    
        private void balbanceLR(AVLTreeNode<E> A, AVLTreeNode<E> parent){
            AVLTreeNode<E> B = (AVLTreeNode<E>)A.leftNode;
            AVLTreeNode<E> C = (AVLTreeNode<E>)B.rightNode;
            if (A == root)
                root = C;
            else {
                if(parent.leftNode == A)
                    parent.leftNode = C;
                else
                    parent.rightNode =C;
            }
            A.leftNode = C.rightNode;
            B.rightNode = C.leftNode;
            C.leftNode = B;
            C.rightNode = A;
            updateHeight(A);
            updateHeight(B);
            updateHeight(C);
        }
    
        public boolean delete(E e){
            if (root == null) // nothing in the tree
                return false;
            TreeNode<E> parent = null;
            TreeNode<E> current = root;
    
            while(current!=null){
                if (e.compareTo(current.element)>0){
                    parent = current;
                    current = current.rightNode;
                }
                else if (e.compareTo(current.element)<0){
                    parent = current;
                    current = current.leftNode;
                }
                else break;
            }
    
            if (current == null) return false; //元素不在二叉树中
            if (current.leftNode == null){ //没有左节点
                if (parent == null)
                    root = current.rightNode;
                else {
                    if (e.compareTo(parent.element)>0)
                        parent.rightNode = current.rightNode;
                    else
                        parent.leftNode = current.rightNode;
                    balancePath(parent.element);
                }
            }
            else{                           //有左节点
                TreeNode<E> parentOfRightMost = current;
                TreeNode<E> rightMost = current.leftNode;
                while (rightMost.rightNode != null){
                    parentOfRightMost = rightMost;
                    rightMost = rightMost.rightNode;
                }
                current.element = rightMost.element;
                if(parentOfRightMost.rightNode == rightMost)
                    parentOfRightMost.rightNode = rightMost.leftNode;
                else
                    parentOfRightMost.leftNode = rightMost.leftNode;
    
                balancePath(parentOfRightMost.element);
            }
            size--;
            return true;
        }
    }