avl树的java实现（平衡二叉树）

Bertha 。 2023-07-17 15:44 18阅读 0赞

**平衡二叉树定义(AVL)：**  
（1）它的左子树和右子树的深度之差(平衡因子)的绝对值不超过1。  
（2）它的左子树和右子树都是一颗平衡二叉树。

**平衡因子：**  
将二叉树上节点的左子树深度减去右子树深度的值称为平衡因子BF。则平衡二叉树上所有节点的平衡因子只可能是1，-1，0。只要二叉树上有一个节点的平衡因子的绝对值大于1，那么该二叉树就是不平衡的。  
**最小不平衡子树：**  
距离插入节点最近的，且平衡因子的绝对值大于1的节点为根的子树，我们称之为最小不平衡子树。

我们之间通过代码来看实现：  
1、二叉树的定义

class AVLNode {
            /**
             * 保存节点的数据
             */
            private int data;
            /**
             * 当前节点的深度
             * 深度是常用参数，保存深度数据，
             * 不用多次递归去计算节点的深度
             */
            private int depth;
    
            /**
             * 平衡指数（左边深度-右边深度）
             * 左子树高则为正，左边子树第则为负数
             */
            private int balance;
            /**
             * 指向父节点（简化后面关于循环父节点获取）
             */
            public AVLNode parent;
    
            /**
             * 左子树
             */
            public AVLNode left;
    
            /**
             * 右子树
             */
            public AVLNode right;
    
            public AVLNode(int data) {
                this.data = data;
                depth = 1;
                balance = 0;
                left = null;
                right = null;
            }
        }

2、关于树的深度的计算（因为这里的二叉树定义了高度，直接用左右子树的最高深度就可以了）

/**
         * 计算当前节点深度
         *
         * @param node
         * @return
         */
        private int calculateDepth(AVLNode node) {
            int depth = 0;
            if (node.left != null) {
                depth = node.left.depth;
            }
            if (node.right != null && node.right.depth > depth) {
                depth = node.right.depth;
            }
            depth++;
            return depth;
        }

3、计算平衡因子（）

/**
         * 计算平衡因子
         *
         * @param node
         * @return
         */
        private int calculateBalance(AVLNode node) {
            int leftDepth;
            int rightDepth;
            //获取节点左边深度
            if (node.left != null) {
                leftDepth = node.left.depth;
            } else {
                leftDepth = 0;
            }
    
            if (node.right != null) {
                rightDepth = node.right.depth;
            } else {
                rightDepth = 0;
            }
            return leftDepth - rightDepth;
        }

4、右旋  
![在这里插入图片描述][20200322224645236.png]

/**
         * 右旋
         *
         * @param node
         */
        private void rightRotate(AVLNode node) {
            AVLNode nParent = node.parent;
            AVLNode nLeftSon = node.left;
            AVLNode nLeftRightGrandSon = nLeftSon.right;
    
    
            if (nParent == null) {
                //更改更改根节点
                this.root = nLeftSon;
            }
            //1、更改父节点指向
            //在操作的时候只改变指针指向，故可以用==
            else if (node == nParent.left) {
                nParent.left = nLeftSon;
            } else if (node == nParent.right) {
                nParent.right = nLeftSon;
            }
    
    
            //2、更改左子节点指针指向（父节点和右子节点改变）
            nLeftSon.parent = nParent;
            nLeftSon.right = node;
    
            //3、更改当前节点
            node.parent = nLeftSon;
            node.left = nLeftRightGrandSon;
    
            //4、更改右子节点
            if (nLeftRightGrandSon != null) {
                nLeftRightGrandSon.parent = node;
            }
    
            //此时改变平衡度/深度其实就左子节点和当前节点
            //需要先计算当前节点的深度和平衡度，
            // 因为原来的左子节点变成当前节点的父节点
            node.depth = calculateDepth(node);
            node.balance = calculateBalance(node);
    
            nLeftSon.depth = calculateDepth(nLeftSon);
            nLeftSon.balance = calculateBalance(nLeftSon);
        }

5、左旋  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZhamluZ19mZWl5dWU_size_16_color_FFFFFF_t_70]

/**
         * 左旋
         *
         * @param node
         */
        private void leftRotate(AVLNode node) {
            AVLNode nParent = node.parent;
            AVLNode nRightSon = node.right;
            AVLNode nRightLeftGrandSon = nRightSon.left;
    
    
            if (nParent == null) {
                //更改更改根节点
                this.root = nRightSon;
                //1、更改父节点指向
            } else if (node == nParent.right) {
                nParent.right = nRightSon;
            } else if (node == nParent.left) {
                nParent.left = nRightSon;
            }
    
    
            //2、更改右子节点指向
            nRightSon.parent = node;
            nRightSon.left = node;
    
            //3、更改当前节点指向
            node.parent = nRightSon;
            node.right = nRightLeftGrandSon;
    
            //4、更改右左节点指向
            if (nRightLeftGrandSon != null) {
                nRightLeftGrandSon.parent = node;
            }
    
            //此时改变平衡度/深度其实就右子节点和当前节点
            //需要先计算当前节点的深度和平衡度，
            // 因为原来的右子节点变成当前节点的父节点
            node.depth = calculateDepth(node);
            node.balance = calculateBalance(node);
    
            nRightSon.depth = calculateDepth(nRightSon);
            nRightSon.balance = calculateBalance(nRightSon);
    
        }

6、插入数据方法;

public boolean insert(int data) {
            return insert(root, data);
        }
    
        /**
         * 插入平衡树数据
         *
         * @param node 当前数值比较的节点
         * @param data 数值
         */
        public boolean insert(AVLNode node, int data) {
            if (node == null) {
                node = new AVLNode(data);
                root = node;
                return true;
            }
            //插入相同数值的二叉树
            if (data == node.data) {
                return false;
            }
            //二叉树左边数值小，右边数值大【根据这个特性对数据进行递归插入】
            //当插入数据小于当前比较的节点时候，从左边递归插入
            if (data < node.data) {
                //由于左边 还有数值，需要和下一个左边值比较
                if (node.left != null) {
                    insert(node.left, data);
                } else {
                    //左边数值为空，可以直接插入
                    //将比较节点左边指向 新节点
                    node.left = new AVLNode(data);
                    //给新节点parent的父节点参数指向 比较节点
                    node.left.parent = node;
                }
            } else {
                //当插入数据大于当前比较的节点时候，从右边递归插入
                if (node.right != null) {
                    //由于右边 还有数值，需要和下一个右边边值比较
                    insert(node.right, data);
    
                } else {
                    //左边数值为空，可以直接插入
                    //将比较节点左边指向 新节点
                    node.right = new AVLNode(data);
                    node.right.parent = node;
                }
            }
            //更新当前节点上面的balance和depth,并作出旋转
            rebuild(node);
            return true;
        }
         /**
         * 更新当前节点上面的balance和depth,并作出旋转
         *
         * @param node
         */
        private void rebuild(AVLNode node) {
            //获取当前节点的平衡度
            node.balance = calculateBalance(node);
            //此时左树更改，且大于最大平衡度，应该右旋
            if (node.balance >= MAX_LEFT) {
                //此时左子节点的右子树更高需要，先左旋
                if (node.left.balance == RIGHT) {
                    leftRotate(node.left);
                }
                rightRotate(node);
            }
            //此时右树更改，且大于最大平衡度，应该左旋
            if (node.balance <= MAX_RIGHT) {
                //此时右子节点的左子树更高需要，先右旋
                if (node.right.balance == LEFT) {
                    rightRotate(node.right);
                }
                leftRotate(node);
            }
            node.balance = calculateBalance(node);
            node.depth = calculateDepth(node);
        }

查看完整代码：

public class AVLTree {
    
        private AVLNode root;
        private final int LEFT = 1;
        private final int RIGHT = -1;
        private final int MAX_LEFT = 2;
        private final int MAX_RIGHT = -2;
    
    
        public boolean insert(int data) {
            return insert(root, data);
        }
    
        /**
         * 插入平衡树数据
         *
         * @param node 当前数值比较的节点
         * @param data 数值
         */
        public boolean insert(AVLNode node, int data) {
            if (node == null) {
                node = new AVLNode(data);
                root = node;
                return true;
            }
            //插入相同数值的二叉树
            if (data == node.data) {
                return false;
            }
            //二叉树左边数值小，右边数值大【根据这个特性对数据进行递归插入】
            //当插入数据小于当前比较的节点时候，从左边递归插入
            if (data < node.data) {
                //由于左边 还有数值，需要和下一个左边值比较
                if (node.left != null) {
                    insert(node.left, data);
                } else {
                    //左边数值为空，可以直接插入
                    //将比较节点左边指向 新节点
                    node.left = new AVLNode(data);
                    //给新节点parent的父节点参数指向 比较节点
                    node.left.parent = node;
                }
            } else {
                //当插入数据大于当前比较的节点时候，从右边递归插入
                if (node.right != null) {
                    //由于右边 还有数值，需要和下一个右边边值比较
                    insert(node.right, data);
    
                } else {
                    //左边数值为空，可以直接插入
                    //将比较节点左边指向 新节点
                    node.right = new AVLNode(data);
                    node.right.parent = node;
                }
            }
            //更新当前节点上面的balance和depth,并作出旋转
            rebuild(node);
            return true;
        }
    
        /**
         * 更新当前节点上面的balance和depth,并作出旋转
         *
         * @param node
         */
        private void rebuild(AVLNode node) {
            //获取当前节点的平衡度
            node.balance = calculateBalance(node);
            //此时左树更改，且大于最大平衡度，应该右旋
            if (node.balance >= MAX_LEFT) {
                //此时左子节点的右子树更高需要，先左旋
                if (node.left.balance == RIGHT) {
                    leftRotate(node.left);
                }
                rightRotate(node);
            }
            //此时右树更改，且大于最大平衡度，应该左旋
            if (node.balance <= MAX_RIGHT) {
                //此时右子节点的左子树更高需要，先右旋
                if (node.right.balance == LEFT) {
                    rightRotate(node.right);
                }
                leftRotate(node);
            }
            node.balance = calculateBalance(node);
            node.depth = calculateDepth(node);
        }
    
        /**
         * 计算当前节点深度
         *
         * @param node
         * @return
         */
        private int calculateDepth(AVLNode node) {
            int depth = 0;
            if (node.left != null) {
                depth = node.left.depth;
            }
            if (node.right != null && node.right.depth > depth) {
                depth = node.right.depth;
            }
            depth++;
            return depth;
        }
    
        /**
         * 右旋
         *
         * @param node
         */
        private void rightRotate(AVLNode node) {
            AVLNode nParent = node.parent;
            AVLNode nLeftSon = node.left;
            AVLNode nLeftRightGrandSon = nLeftSon.right;
    
    
            if (nParent == null) {
                //更改更改根节点
                this.root = nLeftSon;
            }
            //1、更改父节点指向
            //在操作的时候只改变指针指向，故可以用==
            else if (node == nParent.left) {
                nParent.left = nLeftSon;
            } else if (node == nParent.right) {
                nParent.right = nLeftSon;
            }
    
    
            //2、更改左子节点指针指向（父节点和右子节点改变）
            nLeftSon.parent = nParent;
            nLeftSon.right = node;
    
            //3、更改当前节点
            node.parent = nLeftSon;
            node.left = nLeftRightGrandSon;
    
            //4、更改右子节点
            if (nLeftRightGrandSon != null) {
                nLeftRightGrandSon.parent = node;
            }
    
            //此时改变平衡度/深度其实就左子节点和当前节点
            //需要先计算当前节点的深度和平衡度，
            // 因为原来的左子节点变成当前节点的父节点
            node.depth = calculateDepth(node);
            node.balance = calculateBalance(node);
    
            nLeftSon.depth = calculateDepth(nLeftSon);
            nLeftSon.balance = calculateBalance(nLeftSon);
        }
    
        /**
         * 左旋
         *
         * @param node
         */
        private void leftRotate(AVLNode node) {
            AVLNode nParent = node.parent;
            AVLNode nRightSon = node.right;
            AVLNode nRightLeftGrandSon = nRightSon.left;
    
    
            if (nParent == null) {
                //更改更改根节点
                this.root = nRightSon;
                //1、更改父节点指向
            } else if (node == nParent.right) {
                nParent.right = nRightSon;
            } else if (node == nParent.left) {
                nParent.left = nRightSon;
            }
    
    
            //2、更改右子节点指向
            nRightSon.parent = node;
            nRightSon.left = node;
    
            //3、更改当前节点指向
            node.parent = nRightSon;
            node.right = nRightLeftGrandSon;
    
            //4、更改右左节点指向
            if (nRightLeftGrandSon != null) {
                nRightLeftGrandSon.parent = node;
            }
    
            //此时改变平衡度/深度其实就右子节点和当前节点
            //需要先计算当前节点的深度和平衡度，
            // 因为原来的右子节点变成当前节点的父节点
            node.depth = calculateDepth(node);
            node.balance = calculateBalance(node);
    
            nRightSon.depth = calculateDepth(nRightSon);
            nRightSon.balance = calculateBalance(nRightSon);
    
        }
    
        /**
         * 计算平衡因子
         *
         * @param node
         * @return
         */
        private int calculateBalance(AVLNode node) {
            int leftDepth;
            int rightDepth;
            //获取节点左边深度
            if (node.left != null) {
                leftDepth = node.left.depth;
            } else {
                leftDepth = 0;
            }
    
            if (node.right != null) {
                rightDepth = node.right.depth;
            } else {
                rightDepth = 0;
            }
            return leftDepth - rightDepth;
        }
    
    
        class AVLNode {
            /**
             * 保存节点的数据
             */
            private int data;
            /**
             * 当前节点的深度
             * 深度是常用参数，保存深度数据，
             * 不用多次递归去计算节点的深度
             */
            private int depth;
    
            /**
             * 平衡指数（左边深度-右边深度）
             * 左子树高则为正，左边子树第则为负数
             */
            private int balance;
            /**
             * 指向父节点（简化后面关于循环父节点获取）
             */
            public AVLNode parent;
    
            /**
             * 左子树
             */
            public AVLNode left;
    
            /**
             * 右子树
             */
            public AVLNode right;
    
            public AVLNode(int data) {
                this.data = data;
                depth = 1;
                balance = 0;
                left = null;
                right = null;
            }
        }
    
        public static void main(String[] args) {
    
            AVLTree node = new AVLTree();
           // com.yin.dynamic_elasticjob.util.AVLNode node = new com.yin.dynamic_elasticjob.util.AVLNode(3);
            node.insert(3);
            node.insert(2);
            node.insert(1);
            node.insert(4);
            node.insert(5);
            node.insert(6);
            node.insert(7);
            node.insert(10);
            node.insert(9);
    
            System.out.println("-----验证是否平衡-----");
    
    
    
        }
    }

[20200322224645236.png]: /images/20230528/6b3e573ac199444581c0f941756bd4db.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZhamluZ19mZWl5dWU_size_16_color_FFFFFF_t_70]: /images/20230528/c67db1d4f2664293aa14bb4b304d63aa.png