平衡二叉树的原理及实现

末蓝、 2022-10-22 04:16 161阅读 0赞

今天分析平衡二叉树的原理及实现：

详解平衡二叉树之前先大致普及一下二叉树的基础。

一、二叉树

1、定义

1)结点的度：结点的子树个数

2)树的度：树中所有结点中最大的度

3)结点的层次：规定根结点在1层，子结点的层数是它父结点的层数加1

4)树的高度：树中所有结点中最大的层次是这棵树的高度

度为2的树（树中所有结点中最大的度） ,子树有左右顺序之分

2、二叉排序树

二叉排序树（BST，Binary Sort Tree） 也称二叉查找树（Binary Search Tree），或二叉搜索树。

定义：一颗二叉树，满足以下属性

左子树的所有的值小于根节点的值;右子树的所有的值大于根节点的值 。左、右子树满足以上两点。

错误示例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70][]

正确示例：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1][]

3、二叉排序树的查找操作：Find

查找的值X从根节点开始

1)如果X小于根节点值，则在左子树中继续查找；

2)如果X大于根节点值，则在右子树中继续查找；

3)如果X值等于根节点值，则返回该节点；

4)如果都查不到，则返回空Null；

5)查找的效率决定于树的高度

6)最大元素一定是在树的最右分支的节点上

7)最小元素一定是在树的最左分支的节点上

4、二叉排序树的插入操作：Insert

插入的值X从根节点开始查找

1)X值小于该节点值，在左子树中继续；

2)X值大于该节点值，在右子树中继续；

3)如果节点是叶节点，X值小于该节点值则插入左子节点，否则插入右节点；

5、二叉排序树的删除操作：Delete

插入的值X从根节点开始查找

1)如果节点的值等于X，则删除；

2)X值小于该节点值，在左子树中继续；

3)X值大于该节点值，在右子树中继续；

二、平衡二叉树

1、平衡二叉树定义

平衡二叉树（AVL树，Balance Binary Search Tree ）

它是一 棵二叉排序树，它的左右两个子树的高度差（平衡因子）的绝对值不超过1， 并且左右两个子树都是一棵平衡二叉树。

目的：使得树的高度最低，因为树查找的效率决定于树的高度。

示例：错误与正确的示例。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 2][]

2、平衡二叉树的调整：

如果A是一颗平衡二叉树，如果新插入一个元素，会有两个结果：

1)平衡没有被打破，不用调整。

2)平衡被打破，需要调整。

3)调整原则：根据插入节点与失衡结点的位置关系来划分。

（左右旋时新的根节点多出来一个节点重新调整指向）左旋时——自己（多出来的）变为右孩子的左孩子；右旋——自己（多出来的）变为左孩子的右孩子。

3、RR旋转

插入节点在失衡结点的左子树的左边 只需要经过一次右旋即可达到平衡，右旋——自己（多出来的0025节点）变为左孩子的右孩子。

![20210403204521896.png][]

右旋动态图：

![这里写图片描述][20180722222413303]

4、LL旋转

插入节点在失衡结点的右子树的右边 只需要经过一次左旋即可达到平衡，右旋——自己（多出来的0025节点）变为左孩子的右孩子。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 3][]

左旋动态图：

![这里写图片描述][20180722220546910]

5、LR旋转

需要进行两次旋转才能达到平衡

1)插入节点在失衡结点的左子树的右边

2)失衡结点的左子树先做LL旋转

3)失衡结点再做RR旋转即可达到平衡

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDM2MjEw_size_16_color_FFFFFF_t_70]

6、RL旋转

需要进行两次旋转才能达到平衡

1)插入节点在失衡结点的右子树的左边

2)失衡结点的右子树先做RR旋转

3)失衡结点再做LL旋转即可达到平衡

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 4][]

7、java代码实现：

public class NandaoAVLTree {
        //节点
        public static class Node {
            int data; //数据
    
            Node leftChild; //左子节点
            Node rightChild;//右子节点
            int height; // 记录该节点所在的高度
    
            public Node(int data) {
                this.data = data;
            }
        }
        //获取节点的高度
        public static int getHeight(Node p){
            return p == null ? -1 : p.height; // 空树的高度为-1
        }
        public static void main(String[] args) {
            Node root = null;
            root = insert(root,30);
            root = insert(root,20);
            root = insert(root,40);
            root = insert(root,10);
            root = insert(root,25);
            //插入节点在失衡结点的左子树的左边
            root = insert(root,5);
            //打印树，按照先打印左子树，再打印右子树的方式
            printTree(root);
    
        }
    
        public static void printTree(Node root) {
            System.out.println(root.data);
            if(root.leftChild !=null){
                System.out.print("left:");
                printTree(root.leftChild);
            }
            if(root.rightChild !=null){
                System.out.print("right:");
                printTree(root.rightChild);
            }
        }
        // AVL树的插入方法
        public static Node insert(Node root, int data) {
            if (root == null) {
                root = new Node(data);
                return root;
            }
            if (data <= root.data) { // 插入到其左子树上
                root.leftChild = insert(root.leftChild, data);
                //平衡调整
                if (getHeight(root.leftChild) - getHeight(root.rightChild) > 1) {
                    if (data <= root.leftChild.data) { // 插入节点在失衡结点的左子树的左边
                        System.out.println("RR旋转");
                        root = RRRotate(root); // RR旋转调整
                    }else{ // 插入节点在失衡结点的左子树的右边
                        System.out.println("LR旋转");
                        root = LRRotate(root);
                    }
                }
            }else{ // 插入到其右子树上
                root.rightChild = insert(root.rightChild, data);
                //平衡调整
                if(getHeight(root.rightChild) - getHeight(root.leftChild) > 1){
                    if(data <= root.rightChild.data){//插入节点在失衡结点的右子树的左边
                        System.out.println("RL旋转");
                        root = RLRotate(root);
                    }else{
                        System.out.println("LL旋转");//插入节点在失衡结点的右子树的右边
                        root = LLRotate(root);
                    }
                }
            }
            //重新调整root节点的高度值
            root.height = Math.max(getHeight(root.leftChild), getHeight(root.rightChild)) + 1;
            return root;
        }
        // LR旋转
        public static Node LRRotate(Node p){
            p.leftChild = LLRotate(p.leftChild); // 先将失衡点p的左子树进行LL旋转
            return RRRotate(p); // 再将失衡点p进行LL平衡旋转并返回新节点代替原失衡点p
    
        }
        // RL平衡旋转
        public static Node RLRotate(Node p){
            p.rightChild = RRRotate(p.rightChild); // 先将失衡点p的右子树进行RR平衡旋转
            return LLRotate(p); // 再将失衡点p进行LL平衡旋转并返回新节点代替原失衡点p
        }
    
        /*
         * RR旋转
         * 左旋示意图(对结点20进行左旋)
         *      30                       20
         *     /  \                     /  \
         *    20  40                  10   30
         *   /  \      --RR旋转-       /   /  \
         *  10   25                  5   25   40
         *  /
         * 5
         *
         */
        public static Node RRRotate(Node p){ // 30为失衡点
            Node lsubtree = p.leftChild;   //失衡点的左子树的根结点20作为新的结点
            p.leftChild = lsubtree.rightChild; //将新节点的右子树25成为失衡点30的左子树
            lsubtree.rightChild = p; // 将失衡点30作为新结点的右子树
            // 重新设置失衡点30和新节点20的高度
            p.height = Math.max(getHeight(p.leftChild), getHeight(p.rightChild)) + 1;
            lsubtree.height = Math.max(getHeight(lsubtree.leftChild), p.height) + 1;
            return lsubtree; // 新的根节点取代原失衡点的位置
        }
        /*
         * LL旋转
         * 右旋示意图(对结点30进行左旋)
         *      20                          30
         *     /  \                        /  \
         *    10  30                     20   40
         *       /  \      --LL旋转-     /  \   \
         *      25  40                 10  25  50
         *           \
         *           50
         *
         */
        // LL旋转
        public static Node LLRotate(Node p){ // 20为失衡点
            Node rsubtree = p.rightChild;  //失衡点的右子树的根结点30作为新的结点
            p.rightChild = rsubtree.leftChild; //将新节点的左子树25成为失衡点20的右子树
            rsubtree.leftChild = p; // 将失衡点20作为新结点的左子树
            // 重新设置失衡点20和新节点30的高度
            p.height = Math.max(getHeight(p.leftChild), getHeight(p.rightChild)) + 1;
            rsubtree.height = Math.max(getHeight(rsubtree.leftChild), getHeight(rsubtree.rightChild)) + 1;
            return rsubtree; // 新的根节点取代原失衡点的位置
        }
    }

8、执行结果：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 5][]

到此，平衡二叉树分享完毕，下篇我们分享红黑树的原理和实现，敬请期待！

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70]: /images/20221022/5a8004d833c54641a95ed205717d1645.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 1]: /images/20221022/3d1cd359e87d4d69ade5219267169a57.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 2]: /images/20221022/bd066cc7d9c6417cb8384ac87eeaee7d.png
[20210403204521896.png]: /images/20221022/acafe347b40b4db1a54c281740ae639f.png
[20180722222413303]: /images/20221022/f91a4fd64d7745158140f3fdd9b9a6b2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 3]: /images/20221022/e47401d5ff444289ad60ce6b1a810948.png
[20180722220546910]: /images/20221022/a7b4037b7dbb4c08b44aab420bd4a330.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L20wXzM4MDM2MjEw_size_16_color_FFFFFF_t_70]: /images/20221022/4f72ed930a0f487aa42f54bee1e38487.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 4]: /images/20221022/3e45a4d2cf9e485295c2de0ecfe66728.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L25hbmRhbzE1OA_size_16_color_FFFFFF_t_70 5]: /images/20221022/bd8d03e26f274ec9a631286a6ae5b001.png