AVL树（Java）

ゞ浴缸里的玫瑰 2024-02-05 23:04 14阅读 0赞

**目录**

一、什么是AVL树

二、AVL树的实现

AVL树的节点

AVL树的插入

AVL树的旋转

右单旋

左单旋

左右双旋

右左双旋

AVL树的验证

三、AVL树的性能分析

--------------------

## 一、什么是AVL树 ##

在了解什么是AVL树之前，我们先回顾**二叉搜索树**的概念

二叉搜索树（二叉排序树），它或是一棵**空树**，或具有以下性质：

> **1. 若它的左子树不为空，则左子树上所有节点的值都小于根节点的值**
> 
> **2. 若它的右子树不为空，则右子树上所有节点的值都大于根节点**
> 
> **3. 它的左右子树也分别是二叉搜索树**

![8b095004a48c4241a83fee1b804129c2.png][]

根据二叉搜索树的性质，我们可以发现：

**1. 二叉搜索树中最左侧的节点是树中最小的节点，最右侧的节点是树中最大的节点**

**2. 若采用中序遍历二叉搜索树，则可得到一个有序的序列**

二叉搜索树最主要的作用就是用于进行查询：

![669d9cfdd3b348d9b07fdf8c6e1c8b51.png][]

当二叉搜索树是一颗**完全二叉树**时：

![70b8428e565941c2afdcfa5f7c5c49a6.png][]

其查询的平均查找次数为:![log\_\{2\}^\{\}n][log_2_n]

而当二叉搜索树是一颗**单支树**时：

![d2e1f3db10d24c06a897bbfe48ad8f3f.png][]

其平均查找次数为：![\\frac\{n\}\{2\}][frac_n_2]

由此可见二叉搜索树的**平均查找次数**与二叉搜索树的**深度成正相关**，即**深度越深，比较查找的次数越多**。而当其是单支树时，二叉搜索树的性能就降低了，此时，能否对其进行改进，使其无论怎样插入，都能够使二叉搜索树的性能最佳？

AVL树的出现解决了这个问题。

ALV树（也就是**平衡二叉查找树**，简称**平衡二叉树**）或是一颗空树，或具有以下性质：

> **1. 它的左右子树高度之差（简称平衡因子）的绝对值不超过1**
> 
> **2. 它的左右子树都是AVL树**

![f96ed055b0bc43298a20f7175809095d.png][]

由AVL树的性质，我们可以发现：

**1. 每当向AVL树中插入新的节点时，都要保证每个节点的左右子树高度差（平衡因子）的绝对值不超过1（当超过时需要对树中的节点进行调整，即降低树的高度，从而减少平均搜索长度）**

**2. 若一颗AVL树有n个节点，它的高度能够保持在![log\_\{2\}^\{\}N][log_2_N]，因此，其搜索的时间复杂度为O(![log\_\{2\}^\{\}N][log_2_N])**

## 二、AVL树的实现 ##

### AVL树的节点 ###

在这里，我们通过一个**内部类**来实现AVL树节点的定义，通过维护节点的**左孩子、右孩子和父亲节点**来实现AVL树，同时定义一个**平衡因子bf**，通过平衡因子来判断是否需要调整树中节点。同时，我们需要定义根节点：

**当前节点的平衡因子 = 右子树的高度 - 左子树的高度**

### AVL树的插入 ###

AVL树就是在**二叉搜索树的基础上引入了平衡因子**，因此，我们可以将AVL树的插入过程分为**两步**：

> **1. 插入新的节点**
> 
> **2. 调整节点的平衡因子**

现在我们对新的节点进行插入：

**1. 当AVL树为空时，插入的节点即为根节点**

**2. AVL树不为空，则寻找新节点的插入位置**

> **如何寻找新节点的插入位置？**

**若新节点node的值val > 当前节点cur的值val，则在cur的右子树寻找插入位置；**

**若node.val < cur.val，则在cur的左子树寻找插入位置；**

**若node.val = cur.val，则AVL树中已有该节点，插入失败，直接返回false**

![34b342b48a3d4fc48afcacfc679a2578.png][]

在找到插入位置后，我们需要知道**其父亲节点**，从而进行插入，因此在查找过程中，我们可以定义当前节点cur的父亲节点parent，用于最后进行插入新节点：

//节点的插入
        public boolean insert(int val){
            TreeNode node = new TreeNode(val);
            //若根节点为空，则直接将插入为根节点
            if(root == null){
                root = node;
                return true;
            }
            //根节点不为空，查找其插入位置
            TreeNode parent = null;
            TreeNode cur = root;
            while (cur != null){
                if(cur.val < val){
                    parent = cur;
                    cur = cur.right;
                }else if(cur.val > val){
                    parent = cur;
                    cur = cur.left;
                }else{
                    return false;//若已有该节点，则插入失败，直接返回false
                }
            }
            //将节点插入
            node.parent = parent;
            cur = node;
        }

### AVL树的旋转 ###

在插入新的节点之后，此时AVL树中某些节点的平衡因子会发生改变，因此我们需要对平衡因子进行修改，而在插入新节点后，节点的平衡因子的绝对值可能超过1，此时我们需要对节点进行调整

**我们首先对平衡因子进行修改：**

在插入新节点时，我们定义了其父亲节点parent，由于在这里**平衡因子 = 右子树的高度 - 左子树的高度**

因此，若**新插入的节点在parent的左子树，则其平衡因子 -1**；而若**新插入的节点在parent的右子树，则平衡因子 +1**

![bb08e0945a3a4235b299631b831550fd.png][]

在修改完当前平衡因子后，我们需要对当前平衡因子进行检查，判断其是否符合条件：

**1. 若修改后的平衡因子 = 0**，则表明未修改时parent的平衡因子bf = 1 或 -1，在插入后被调整成为0，**此时子树parent已经平衡了**，且其**高度并未发生改变**，不会影响上面节点的平衡因子，因此**不用再继续向上判断**

![9b45a2ca55e34e62a87a9935b8c2d09b.png][]

**2. 若修改后的平衡因子 = 1 或 -1**，则表明未修改时parent的平衡因子bf = 0，在插入之后被调整成 1 或 -1，此时**子树parent的高度增加**，上面节点的平衡因子也会被影响，因此**需要继续向上更新平衡因子**

![66e63c5d3bc44513a293364372b88bb1.png][]

**3. 若修改后的平衡因子的绝对值 > 1**，此时则**需要对AVL树的节点进行调整，重新使其平衡**

在这里，我们通过旋转来调整节点的平衡因子，AVL树的旋转分为**四种**情况：

#### 右单旋 ####

**（1）新节点插入较高左子树的左侧->右单旋**

当新节点插入较高左子树的左侧时：

![5a28d0c91c344f57af5dc2f2aade0b4b.png][]

此时 **patent.bf = -2, cur.bf = -1**，要想办法降低左子树的高度，因此对其进行调整：

![436d5e76464e4ee9b69ad11fe6e217c1.png][]

将对于**以parent 为根的子树**：

将cur作为其根；parent作为cur的右子树；cur原右子树（若有的话）作为parent的左子树，

这样重新调整后，**cur和parent的平衡因子都被调整为0**，此时**以cur为根的子树已经平衡**

因此，我们调整的步骤为：

**我们设parent的左孩子cur为subL，cur的右孩子为subLR（因为要考虑cur的右孩子不存在的情况）**

**1. 将parent的左孩子更新为subLR，将subLR的父亲节点更新为parent**

**注：此时要考虑subLR为空的情况，若subLR为空，则不需要更新**

![25c20cadb39a43c1bdf851d39e4a9f62.png][]

**2. 将subL的右孩子更新为parent，将parent的父亲节点更新为subL**

**注：在更新parent的父亲节点时，我们首先要将parent的父亲节点pParent保存起来，因为我们需要将subL的父亲节点更新为parent的父亲节点**

**3. 更新subL的父亲节点，**

**若parent原为根节点**，此时需要将根节点更新为subL，同时将subL的父亲节点更新为null；

**若parent原不为根节点**，则更新subL的父亲节点为pParent，同时需要更新pParent的孩子节点，此时需要判断parent为pParent的左孩子还是右孩子，并更新

**右单旋代码：**

//右单旋
    private void rotateRight(TreeNode parent){
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
    
        parent.left = subLR;
        if(subLR != null){//只有当subLR不为空时，才能修改其父亲节点
            subLR.parent = parent;
        }
        
        subL.right = parent;
        //在修改parent的父亲节点时，必须先记录其父亲节点，以便修改subL的父亲节点
        TreeNode pParent = parent.parent;
        parent.parent = subL;
        //判断subL是否被修改为根节点
        if(parent == root){
            root = subL;
            root.parent = null;
        }else {
            subL.parent = pParent;
            //判断是左子树还是右子树
            if(pParent.left == parent){
                pParent.left = subL;
            }else {
                parent.right = subL;
            }
        }
        //修改平衡因子
        subL.bf = 0;
        parent.bf = 0;
    }

#### 左单旋 ####

**新节点插入较高右子树的右侧->左单旋**

左单旋与右单旋类似：

当新的节点插入到较高右子树的右侧时：

![2423b5c63d7b42eebb9028ebeb78f70d.png][]

此时 **parent.bf = 2, cur.bf = 1**，要想办法降低右子树的高度，对以parent为根的子树进行调整：

设parent的右孩子cur为subR，subR的左孩子为subRL（要考虑subR的左孩子为空的情况）

![1de3bff41685473e8df2ec71d6504ea8.png][]

> **1. 将parent的右孩子更新为subRL，将subRL的父亲节点更新为parent（若subRL不为空）**
> 
> **2. 将subR的左孩子更新为parent，保存parent的父亲节点pParent，再更新parent的父亲节点为subR**
> 
> **3. 更新subR的父亲节点，若parent原为根节点，则更新根节点为subR，并将其父亲节点更新为null；若parent原不为根节点，则更新subR的父亲节点为pParent，判断parent原为pParent的左孩子还是右孩子，并将subR更新为pParent的孩子节点**

**左单旋代码：**

//左单旋
    private void rotateLeft(TreeNode parent){
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        
        parent.right = subRL;
        if(subRL != null){//只有当subRL不为空时，才能修改其父亲节点
            subRL.parent = parent;
        }
        
        subR.left = parent;
        //在修改parent父亲节点前将其进行记录，以便后续修改subR的父亲节点
        TreeNode pParent = parent.parent;
        parent.parent = subR;
        //判断subR是否被修改为根节点
        if(parent == root){
            root = subR;
            root.parent = null;
        }else {
            //判断是其左子树还是右子树
            if(pParent.left == parent){
                pParent.left = subR;
            }else{
                pParent.right = subR;
            }
            subR.parent = pParent;
        }
        //修改平衡因子
        subR.bf = 0;
        parent.bf = 0;
    }

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

**新节点插入较高左子树的右侧->左右双旋（先左单旋再右单旋）**

当新的节点插入较高左子树的右侧时：

![0f452b1d0fef4d6784078470cfb07829.png][]

此时 **parent.bf = -2, cur.bf = 1**，此时对于以parent为根的子树，无论是进行右单旋，还是进行左单旋，都不能使其平衡。因此，此时不能只进行一次旋转，而需要进行两次旋转：  
首先，我们需要对以cur为根的子树进行一次左单旋：

![b60773dc763d4dd1ad2702ff8b861449.png][]

然后再对以parent为根的子树进行一次右单旋：

![09a79af7c2434960a9767bd55c8f11b6.png][]

此时调整后的子树达到平衡状态，由于进行的左单旋和右单旋会更改其中节点的平衡因子，因此我们需要对被修改的平衡因子进行重新调整：

平衡因子被修改的节点有：parent、parent的左孩子subL、subL的右孩子subLR

它们的平衡因子都被修改为0，

然而经过两次旋转后，它们的平衡因子并不都为0

![d6d42efd37d64555ba5a1f50dbae8115.png][]

通过观察我们发现，当subLR的平衡因子原为-1时，经过调整后，parent的平衡更新为1

![1bfcc013fe964940b8d9d8859dc3573b.png][] 当subLR的平衡因子原为1时，经过调整后，subL的平衡因子被更新为-1：

![eea5c27f2926469297d0ef433103104f.png][]

当subLR的平衡因子原为0时，经过调整后，parent、subL和subLR的平衡因子都为0：

![7f9e7deafa7d41d885b1953c45e40380.png][]

因此，我们根据subLR原平衡因子来调整旋转两次之后的平衡因子

> **为什么subLR的平衡因子不同，两次旋转后的平衡因子也不同呢？**

当subLR的平衡因子为**-1**时，经过一次左单旋，subRL的左子树变为subR的右子树，由于subR的平衡因子为1，经过这次左旋后，其右子树的高度减一（少了subRL），此时subR的平衡因子变为0，且subRL变为subR的父亲节点。

当subLR变为subR的父亲节点时，其平衡因子变为 -2 ，这是因为subRL的原平衡因子为-1，经过一次左旋后，其左子树高度增加1（增加了subR），右子树高度不变，因此平衡因子变为 -2。

而parent的平衡因子不变，仍是 -2，这是因为在经过一次左单旋后，其右子树高度不变，虽其左孩子变为了subRL，但其高度未改变，因此parent的平衡因子不变

其过程更新过程如下图：

![36f55a30347a4c96bde3b07bd07e6894.png][]

此时，我们假设subLR的左子树高度为m，由于其平衡因子为-2，则subLR的右子树高度为m-2，而parent的左子树高度为m+1，parent的右子树高度为m-1

当进行一次右旋后，由于subR的左右子树不变，因此其平衡因子仍为0

而parent变为subLR的右子树，且其左子树变为subLR的右子树，parent的右子树高度未改变，任为m - 1，而parent的左子树变为subLR的右子树，因此其高度变为m-2，则parent子树的高度为m-1，平衡因子变为 1

subLR的左子树为改变，高度任为m，而右子树变为以parent为根的子树，parent子树的高度为m-1，再加上parent，则为m，因此subLR的平衡因子变为0

![d500a1c55cae4d0e861423679da9d3de.png][]

当subLR的平衡因子为1和为0时也是同样的分析过程，大家可自行进行分析，这里就不再进行分析了

**左右双旋代码：**

//左右双旋
    private void rotateLR(TreeNode parent){
        TreeNode subL = parent.left;
        TreeNode subLR = subL.right;
        //记录subLR平衡因子
        int bf = subLR.bf;
        rotateLeft(parent.left);//先左旋
        rotateRight(parent);//再右旋
        //修改平衡因子
        if(bf == -1){
            parent.bf = 1;
        }else if(bf == 1){
            subL.bf = -1;
        }
    }

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

**新节点插入较高右子树的左侧->右左双旋（先右单旋再左单旋）**

右左双旋与左右双旋的情况类似

当新节点插入较高右子树的左侧时：

![89537b56fbc8410e9ef79a5acbdd68a9.png][]

此时 **parent.bf = 2, cur.bf = -1**，仍要进行两次旋转，才能将以parent为根的子树调整为平衡的子树

此时要先对其进行右旋：

![da45bf477f424050a0b782077ffca6c6.png][]

再对其进行左旋：

![36ecc0fdee4545c5b5928d144b8f74b8.png][]

最后，我们再根据原subRL的平衡因子对平衡因子对其修改：

> **当subRL原平衡因子为1时，更新后的parent的平衡因子为-1**
> 
> **当subRL原平衡因子为-1时，更新后的subR的平衡因子为1**
> 
> **当subRL原平衡因子为0时，更新后parent、subR和subRL的平衡因子都为0**

**右左双旋的代码为：**

//右左双旋
    private void rotateRL(TreeNode parent){
        TreeNode subR = parent.right;
        TreeNode subRL = subR.left;
        //记录subRL的平衡因子
        int bf = subRL.bf;
        rotateRight(subR);//先右旋
        rotateLeft(parent);//再左旋
        //修改平衡因子
        if(bf == 1){
            parent.bf = -1;
        }else if(bf == -1){
            subR.bf = 1;
        }
    }

由上述四种旋转过程可知：**经过旋转后，都能使节点的平衡因子到达平衡，此时无需再向上调整**，因此修改平衡因子的代码为：

//修改平衡因子
            //平衡因子 = 右子树高度 - 左子树高度
            while (parent != null){
                //判断cur是parent的左还是右，从而决定其平衡因子是++还是--
                if(cur == parent.right){
                    parent.bf++;
                }else {
                    parent.bf--;
                }
    
                //检查当前平衡因子 判断是否符合条件（-1 0 1）
                if(parent.bf == 0){
                    //已经平衡
                    break;
                }else if(parent.bf == 1 || parent.bf == -1){
                    //需要继续向上判断是否需要修改平衡因子
                    cur = parent;
                    parent = cur.parent;
                }else {
                    //不平衡，需要进行旋转，使其平衡
                    if(parent.bf == 2){//右树高，需要左旋，从而降低右树高度
                        if(cur.bf == 1){
                           //直接左旋
                            rotateLeft(parent);
                        }else {
                            //右左双旋
                            rotateRL(parent);
                        }
    
                    }else {//左树高，需要右旋，从而降低左树高度
                        if(cur.bf == -1){
                            //直接右旋
                            rotateRight(parent);
                        }else {
                            //左右双旋
                            rotateLR(parent);
                        }
                    }
                    //旋转之后，平衡
                    break;
                }
            }

### AVL树的验证 ###

在我们插入节点后，如何验证我们创建出的树是否是AVL树？

> **AVL树是高度平衡的二叉搜索树，其平衡因子的绝对值不超过1，能否通过节点的平衡因子来验证？**

不能通过平衡因子来验证，因为平衡因子是我们通过计算得出的，若我们在计算时出现错误，那我们通过平衡因子验证的结果也是错误的（例如在左右双旋时，未在最后修改平衡因子，则此时计算的平衡因子不完全正确）

>  **那么我们应该如何进行验证呢？**

首先，AVL树也是二叉搜索树，二叉搜索树中序遍历的结果是有序的，因此我们可以通过中序遍历来验证

public void inorder(TreeNode root) {
            if(root == null) return;
            inorder(root.left);
            System.out.print(root.val+" ");
            inorder(root.right);
        }

其次，AVL树节点的平衡因子绝对值不超过1，即左右子树的高度差不超过1，我们可以通过计算左右子树的高度差来判断树是否是高度平衡的，同时，通过比较计算出的高度差和平衡因子，我们也可以验证当前节点的平衡因子是否正确

private int height(TreeNode root) {//计算子树高度
            if(root == null) return 0;
            int leftH = height(root.left);
            int rightH = height(root.right);
    
            return leftH > rightH ? leftH+1 : rightH+1;
        }
    
        public boolean isBalanced(TreeNode root) {
            if(root == null) return true;
            int leftH = height(root.left);
            int rightH = height(root.right);
            //判断平衡因子是否正确
            if(rightH-leftH != root.bf) {
                System.out.println("节点："+root.val+" 平衡因子异常");
                return false;
            }
            //判断左右子树高度差绝对值是否不超过1
            return Math.abs(leftH-rightH) <= 1
                    && isBalanced(root.left)
                    && isBalanced(root.right);
        }

**完整代码：**

public class AVLTree {
        static class TreeNode{
            public int val;//节点的值
            public int bf;//平衡因子
            public TreeNode left;//左孩子
            public TreeNode right;//右孩子
            public TreeNode parent;//父亲节点
            public TreeNode(int val){
                this.val = val;
            }
        }
    
        public TreeNode root;//根节点
    
        //节点的插入
        public boolean insert(int val) {
            TreeNode node = new TreeNode(val);
            //若根节点为空，则直接将插入为根节点
            if (root == null) {
                root = node;
                return true;
            }
            //根节点不为空，查找其插入位置
            TreeNode parent = null;
            TreeNode cur = root;
            while (cur != null) {
                if (cur.val < val) {
                    parent = cur;
                    cur = cur.right;
                } else if (cur.val > val) {
                    parent = cur;
                    cur = cur.left;
                } else {
                    return false;//若已有该节点，则插入失败，直接返回false
                }
            }
            //将节点插入
            node.parent = parent;
            cur = node;
    
            //修改平衡因子
            //平衡因子 = 右子树高度 - 左子树高度
            while (parent != null){
                //判断cur是parent的左还是右，从而决定其平衡因子是++还是--
                if(cur == parent.right){
                    parent.bf++;
                }else {
                    parent.bf--;
                }
    
                //检查当前平衡因子 判断是否符合条件（-1 0 1）
                if(parent.bf == 0){
                    //已经平衡
                    break;
                }else if(parent.bf == 1 || parent.bf == -1){
                    //需要继续向上判断是否需要修改平衡因子
                    cur = parent;
                    parent = cur.parent;
                }else {
                    //不平衡，需要进行旋转，使其平衡
                    if(parent.bf == 2){//右树高，需要左旋，从而降低右树高度
                        if(cur.bf == 1){
                           //直接左旋
                            rotateLeft(parent);
                        }else {
                            //先右旋，再左旋
                            rotateRL(parent);
                        }
    
                    }else {//左树高，需要右旋，从而降低左树高度
                        if(cur.bf == -1){
                            //直接右旋
                            rotateRight(parent);
                        }else {
                            //先左选，再右旋
                            rotateLR(parent);
                        }
                    }
                    //经过旋转之后，就平衡
                    break;
                }
            }
            return true;
        }
        //左单旋
        private void rotateLeft(TreeNode parent){
            TreeNode subR = parent.right;
            TreeNode subRL = subR.left;
    
            parent.right = subRL;
            if(subRL != null){//只有当subRL不为空时，才能修改其父亲节点
                subRL.parent = parent;
            }
    
            subR.left = parent;
            //在修改parent父亲节点前将其进行记录，以便后续修改subR的父亲节点
            TreeNode pParent = parent.parent;
            parent.parent = subR;
            //判断subR是否被修改为根节点
            if(parent == root){
                root = subR;
                root.parent = null;
            }else {
                //判断是其左子树还是右子树
                if(pParent.left == parent){
                    pParent.left = subR;
                }else{
                    pParent.right = subR;
                }
                subR.parent = pParent;
            }
            //修改平衡因子
            subR.bf = 0;
            parent.bf = 0;
        }
    
        //右单旋
        private void rotateRight(TreeNode parent){
            TreeNode subL = parent.left;
            TreeNode subLR = subL.right;
    
            parent.left = subLR;
            if(subLR != null){//只有当subLR不为空时，才能修改其父亲节点
                subLR.parent = parent;
            }
    
            subL.right = parent;
            //在修改parent的父亲节点时，必须先记录其父亲节点，以便修改subL的父亲节点
            TreeNode pParent = parent.parent;
            parent.parent = subL;
            //判断subL是否被修改为根节点
            if(parent == root){
                root = subL;
                root.parent = null;
            }else {
                subL.parent = pParent;
                //判断是左子树还是右子树
                if(pParent.left == parent){
                    pParent.left = subL;
                }else {
                    parent.right = subL;
                }
            }
            //修改平衡因子
            subL.bf = 0;
            parent.bf = 0;
        }
    
        //左右双旋
        private void rotateLR(TreeNode parent){
            TreeNode subL = parent.left;
            TreeNode subLR = subL.right;
            //记录subLR平衡因子
            int bf = subLR.bf;
            rotateLeft(parent.left);//先左旋
            rotateRight(parent);//再右旋
            //修改平衡因子
            if(bf == -1){
                parent.bf = 1;
            }else if(bf == 1){
                subL.bf = -1;
            }
        }
    
        //右左双旋
        private void rotateRL(TreeNode parent){
            TreeNode subR = parent.right;
            TreeNode subRL = subR.left;
            //记录subRL的平衡因子
            int bf = subRL.bf;
            rotateRight(subR);//先右旋
            rotateLeft(parent);//再左旋
            //修改平衡因子
            if(bf == 1){
                parent.bf = -1;
            }else if(bf == -1){
                subR.bf = 1;
            }
        }
    
        //验证
        public void inorder(TreeNode root) {//中序遍历
            if (root == null) return;
            inorder(root.left);
            System.out.print(root.val + " ");
            inorder(root.right);
        }
    
        private int height(TreeNode root) {//计算子树高度
            if(root == null) return 0;
            int leftH = height(root.left);
            int rightH = height(root.right);
    
            return leftH > rightH ? leftH+1 : rightH+1;
        }
    
        public boolean isBalanced(TreeNode root) {
            if(root == null) return true;
            int leftH = height(root.left);
            int rightH = height(root.right);
            //判断平衡因子是否正确
            if(rightH-leftH != root.bf) {
                System.out.println("节点："+root.val+" 平衡因子异常");
                return false;
            }
            //判断左右子树高度差绝对值是否不超过1
            return Math.abs(leftH-rightH) <= 1
                    && isBalanced(root.left)
                    && isBalanced(root.right);
        }
    }

## 三、AVL树的性能分析 ##

AVL树是一颗**绝对平衡**的二叉搜索树，要求每个节点的左右子树高度差的绝对值都不超过1，这样能够保证查询时的高效，即查询的时间复杂度为O（![log\_\{2\}N][log_2_N 1]）。但当对AVL树进行一些结构的修改操作时，性能就会比较低下（在插入时为了保持其绝对平衡，就需要进行旋转）。因此，若需要一种**查询高效且有序的数据结构**，且**数据的个数为静态的（不改变）**，可以考虑使用AVL树，但若是其经常进行修改，就不太适合使用AVL树。

[8b095004a48c4241a83fee1b804129c2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/45b16585173d4780af933d1abe890c1f.png
[669d9cfdd3b348d9b07fdf8c6e1c8b51.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/b32449c3008c4ddc912854420ac0eff6.png
[70b8428e565941c2afdcfa5f7c5c49a6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/81125534698d4fc3a3df2343d7577aa3.png
[log_2_n]: https://latex.csdn.net/eq?log_%7B2%7D%5E%7B%7Dn
[d2e1f3db10d24c06a897bbfe48ad8f3f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/740a301b54e9405188a21d857c8c650e.png
[frac_n_2]: https://latex.csdn.net/eq?%5Cfrac%7Bn%7D%7B2%7D
[f96ed055b0bc43298a20f7175809095d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/96c0224e86cf458a94847c18ca82a225.png
[log_2_N]: https://latex.csdn.net/eq?log_%7B2%7D%5E%7B%7DN
[34b342b48a3d4fc48afcacfc679a2578.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/fdde32a172f5468f93619443dbcc7fe8.png
[bb08e0945a3a4235b299631b831550fd.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/cbe5b7c5bc04442c83019de929332dc5.png
[9b45a2ca55e34e62a87a9935b8c2d09b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/ed2220ec592b491bacea5e7763053614.png
[66e63c5d3bc44513a293364372b88bb1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/a4d5faf3326b4731abfd11456f6aa550.png
[5a28d0c91c344f57af5dc2f2aade0b4b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/27525980de204d67ac4fb8c2ef3aa6ad.png
[436d5e76464e4ee9b69ad11fe6e217c1.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/49d399ae08424fce854c41078e2df160.png
[25c20cadb39a43c1bdf851d39e4a9f62.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/499ffff72b0649a2921beb3ac8ebdca0.png
[2423b5c63d7b42eebb9028ebeb78f70d.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/40f606b2e794470381a88232d24b349b.png
[1de3bff41685473e8df2ec71d6504ea8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/d7e5220d3ae6499e818dc9dbebd4ec65.png
[0f452b1d0fef4d6784078470cfb07829.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/28fd41c09eb14230aed588771a378f54.png
[b60773dc763d4dd1ad2702ff8b861449.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/22638c5a838f4caaa05aebe6fb28a011.png
[09a79af7c2434960a9767bd55c8f11b6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/09fd22051e8c4661acdb46233b36294d.png
[d6d42efd37d64555ba5a1f50dbae8115.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/b5c4246c5ab44ff194846ac804571bbc.png
[1bfcc013fe964940b8d9d8859dc3573b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/299dc68ff0a74acaa4168f678f69b8a1.png
[eea5c27f2926469297d0ef433103104f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/5cc7d7c29fb44f5ba6565dabe7095e22.png
[7f9e7deafa7d41d885b1953c45e40380.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/45660aa70fd847bcb8cfb0e1825797b4.png
[36f55a30347a4c96bde3b07bd07e6894.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/ebf86854e07e4e999d48c4334f34b29a.png
[d500a1c55cae4d0e861423679da9d3de.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/8967dedba0704e52b5b1be9cb76ce701.png
[89537b56fbc8410e9ef79a5acbdd68a9.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/36192ae780db442a872f88c3a688bf09.png
[da45bf477f424050a0b782077ffca6c6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/f4c3081896bc432aa2a66e10a3b523f9.png
[36ecc0fdee4545c5b5928d144b8f74b8.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/01/30/b2e3d0bd306f46f780c0c94248399765.png
[log_2_N 1]: https://latex.csdn.net/eq?log_%7B2%7DN