AVL-平衡二叉查找树-详解及Java插入示例

分手后的思念是犯贱 2023-06-11 13:27 9阅读 0赞

### AVL-平衡二叉查找树-详解及Java插入示例 ###

*  详解
 *   *   *  定义
         *  性质
 *  插入
 *   *   *  分析及效果图演示
         *   *   *  左左-左单旋转
                 *  右右-右单旋转
                 *  左右双旋转
                 *  右左双旋转
         *  Java例子
         *  测试
         *   *   *  代码
                 *  左单旋转-测试代码图示
                 *  其他图示
 *  参考

> 由于AVL删除比较复杂，下面不进行详解。仅对AVL概念及插入进行详解

# 详解 #

### 定义 ###

每个节点的左右子树的高度 最多 差1的二叉查找树。其中空树的高度为-1，单节点的高度为0。

### 性质 ###

高度n的最少节点数为：a(n) = a(n - 1) + a(n - 2) + 1  
a0 = 1  
a1 = 2  
a2 = 4  
a3 = 7  
a4 = 12  
a5 = 20  
a6 = 33  
a7 = 54  
a8 = 88  
a9 = 143  
n <= 1.44log(a(n) + 2) - 1.328。（证明略，参考《数据结构与算法分析-C语言描述》P80）

# 插入 #

### 分析及效果图演示 ###

会存在下面四种不平衡情况

*  1）a的左儿子的左子树进行一次插入；
 *  2）a的右儿子的右子树进行一次插入；
 *  3）a的左儿子的右子树进行一次插入；
 *  4）a的右儿子的左子树进行一次插入；

##### 左左-左单旋转 #####

下面k2节点处不符合条件，左向右单旋转入下下图所示，即k1变为根节点，k1的右儿子Y变为k2的左儿子

##### 右右-右单旋转 #####

下面k1节点处不符合条件，右向左单旋转入下下图所示，即k2变为根节点，k2的左儿子Y变为k1的右儿子

##### 左右双旋转 #####

下图再k3处不符合条件，即需要对K3->k1->k2（路径先左后右），则可以先k1和k2进行右单旋转、再k2和k3进行左单旋转实现再平衡，如下下图、下下下图所示。

##### 右左双旋转 #####

同理，先右单旋转、再左单旋转即可平衡

### Java例子 ###

AvlNode.java

package com.ydfind.datastructure.avl;
    
    import lombok.Data;
    
    import java.util.Objects;
    
    /**
     * 树节点 对象
     * @author ydifnd
     * @date 2019.10.30
     */
    @Data
    public class AvlNode {
    
        private Integer data;
        private AvlNode parent;
        private AvlNode left;
        private AvlNode right;
    
        public AvlNode(Integer data){
            this.data = data;
        }
    
        public void setChild(int left, int right){
            this.left = new AvlNode(left);
            this.right = new AvlNode(right);
        }
    
    
        public AvlNode insert(AvlNode node){
            int data = node.getData();
            AvlNode result = this;
            // 暂时不支持等于的情况
            if(data < this.data){
                this.left = Objects.isNull(left) ? node : this.left.insert(node);
                if(calcHeight(left) - calcHeight(right) == 2){
                    if(data < left.data){
                        result = singleRotateWithLeft(this);
                    }else {
                        result = doubleRotate(this, true);
                    }
                }
            }else if(data > this.data){
                this.right = Objects.isNull(right) ? node : this.right.insert(node);
                if(calcHeight(right) - calcHeight(left) == 2){
                    if(data > right.data){
                        result = singleRotateWithRight(this);
                    }else {
                        result = doubleRotate(this, false);
                    }
                }
            }
            return result;
        }
    
        /**
         * 计算高度 单节点为0
         * @return 高度
         */
        public static int calcHeight(AvlNode node){
            // 无节点为-1
            if(Objects.isNull(node) || Objects.isNull(node.data)){
                return -1;
            }
            int leftHeight = Objects.nonNull(node.left) ? calcHeight(node.left) : -1;
            int rightHeight = Objects.nonNull(node.right) ? calcHeight(node.right) : -1;
            int height = leftHeight > rightHeight ? 1 + leftHeight : 1 + rightHeight;
            return height;
        }
    
        /**
         * 单选择：左往右
         * @param k2
         * @return 返回旋转后的树
         */
        public static AvlNode singleRotateWithLeft(AvlNode k2){
            // k2.left修改。k1的右节点 变为 k2的左节点
            AvlNode k1 = k2.left;
            k2.left = k1.right;
            if(Objects.nonNull(k2.left)) {
                k2.left.parent = k2.left;
            }
            // k1作为新的根节点
            k1.right = k2;
            k1.parent = k2.parent;
            k2.parent = k1;
            return k1;
        }
    
        /**
         * 单选择：右往左
         * @param k1
         * @return 返回旋转后的树
         */
        public static AvlNode singleRotateWithRight(AvlNode k1){
            AvlNode k2 = k1.right;
            k1.right = k2.left;
            if(Objects.nonNull(k1.right)) {
                k1.right.parent = k2;
            }
            // k2作为新根节点
            k2.left = k1;
            k2.parent = k1.parent;
            k1.parent = k2;
            return k2;
        }
    
        /**
         * isLeft=true,先下面节点左旋转，再上面节点右旋转;否则相反
         * @param k3
         * @param isLeft 是否是左分支
         * @return
         */
        public static AvlNode doubleRotate(AvlNode k3, boolean isLeft){
            if(isLeft) {
                k3.left = singleRotateWithRight(k3.getLeft());
                k3.left.parent = k3;
    
                return singleRotateWithLeft(k3);
            }else{
                k3.right = singleRotateWithLeft(k3.getRight());
                k3.right.parent = k3;
    
                return singleRotateWithRight(k3);
            }
        }
    
    }

### 测试 ###

##### 代码 #####

package com.ydfind.datastructure.avl;
    
    import org.junit.Test;
    
    import java.util.Objects;
    
    /**
     * avl树测试
     * @author ydifnd
     * @date 2019.10.30
     */
    public class AvlNodeTest {
    
    
        /**
         * 树的中序遍历
         * @param node
         */
        public void printTree(AvlNode node){
            System.out.print(node.getData());
            if(Objects.nonNull(node.getLeft()) || Objects.nonNull(node.getRight())) {
                System.out.print("(");
                if (Objects.nonNull(node.getLeft())) {
                    printTree(node.getLeft());
                }
                System.out.print(",");
                if (Objects.nonNull(node.getRight())) {
                    printTree(node.getRight());
                }
                System.out.print(")");
            }
        }
    
        /**
         * 左右子节点和父节点关联
         * @param node
         */
        public void processParent(AvlNode node){
            if(Objects.nonNull(node.getLeft())){
                node.getLeft().setParent(node);
                processParent(node.getLeft());
            }
            if(Objects.nonNull(node.getRight())){
                node.getRight().setParent(node);
                processParent(node.getRight());
            }
        }
    
        /***************************************左单旋转***************************/
        /**
         * 左单旋转:加入6
         *             5
         *         /     \
         *       2         8
         *      /  \      /
         *    1     4    7
         *        /     /
         *      3     6
         *    结果：
         *             5
         *         /     \
         *       2         7
         *      /  \      /  \
         *    1     4    6     8
         *        /
         *      3
         */
        @Test
        public void testAvlNodeLeftSingle(){
            // 左单旋转:插入和直接单旋转比较
            System.out.println("\n左-单旋转1");
            AvlNode root = createLeftSingleData();
            printTree(root);
            System.out.print("\n");
            root.insert(new AvlNode(6));
            printTree(root);
    
            System.out.println("\n左-单旋转2");
            root = createLeftSingleData();
            printTree(root);
            System.out.print("\n");
            root.getRight().getLeft().setLeft(new AvlNode(6));
            // 对8节点进行左单旋转
            root.setRight(AvlNode.singleRotateWithLeft(root.getRight()));
            printTree(root);
            System.out.print("\n");
        }
    
        public AvlNode createLeftSingleData(){
            AvlNode root = new AvlNode(5);
            root.setChild(2, 8);
            root.getLeft().setChild(1, 4);
            root.getLeft().getRight().setLeft(new AvlNode(3));
    
            root.getRight().setLeft(new AvlNode(7));
            processParent(root);
            return root;
        }
    
        /**************************************右单旋转***************************/
        /**
         * 右单旋转：加入5
         *        2
         *      /   \
         *     1      3
         *              \
         *                4
         *                  \
         *                    5
         *    结果：
         *       2
         *     /   \
         *   1      4
         *        /  \
         *       3     5
         */
        @Test
        public void testAvlNodeRightSingle(){
            // 左单旋转:插入和直接单旋转比较
            System.out.println("\n右-单旋转1");
            AvlNode root = createRightSingleData();
            printTree(root);
            System.out.print("\n");
            root.insert(new AvlNode(5));
            printTree(root);
    
            System.out.println("\n右-单旋转2");
            root = createRightSingleData();
            printTree(root);
            System.out.print("\n");
            root.getRight().getRight().setRight(new AvlNode(5));
            root.setRight(AvlNode.singleRotateWithRight(root.getRight()));
            printTree(root);
            System.out.print("\n");
        }
    
        public AvlNode createRightSingleData(){
            AvlNode root = new AvlNode(2);
            root.setChild(1, 3);
    
            root.getRight().setRight(new AvlNode(4));
            processParent(root);
            return root;
        }
    
        /**************************************右双旋转***************************/
        /**
         * 右单旋转：加入14时，在6、15、7触发右双旋转
         *             4
         *         /     \
         *       2         6
         *      /  \      /  \
         *    1     3    5    15
         *                   /   \
         *                 7      16
         *                  \
         *                   14
         *    结果：
         *             4
         *         /     \
         *       2         7
         *      /  \      /  \
         *    1     3    6    15
         *              /    /   \
         *             5   14     16
         */
        @Test
        public void testAvlNodeLeftDouble(){
            // 左单旋转:插入和直接单旋转比较
            System.out.println("\n右双旋转1");
            AvlNode root = createLeftDoubleData();
            printTree(root);
            System.out.print("\n");
            root.insert(new AvlNode(14));
            printTree(root);
    
            System.out.println("\n右双旋转2");
            root = createLeftDoubleData();
            printTree(root);
            System.out.print("\n");
            root.getRight().getRight().getLeft().setRight(new AvlNode(14));
            root.setRight(AvlNode.doubleRotate(root.getRight(), false));
            printTree(root);
            System.out.print("\n");
        }
    
        public AvlNode createLeftDoubleData(){
            AvlNode root = new AvlNode(4);
            root.setChild(2, 6);
            root.getLeft().setChild(1, 3);
    
            root.getRight().setChild(5, 15);
            root.getRight().getRight().setChild(7, 16);
    
            processParent(root);
            return root;
        }
    
    }

##### 左单旋转-测试代码图示 #####

下图插入6后，不再平衡

左

##### 其他图示 #####

请参考测试用例函数上面的解释

# 参考 #

《数据结构与算法分析–C语言分析》