数据结构之二叉树（三） AVL树

青旅半醒 2022-05-25 05:15 190阅读 0赞

### 1.0 简介 ###

AVL树 （叫这个名字是因为发明这个算法的两个人的名字来的）

在计算机科学中，AVL树是最先发明的自平衡二叉查找树。在AVL树中任何节点的两个子树的高度最大差别为一，

所以它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下都是O（log n）。

增加和删除可能需要通过一次或多次树旋转来重新平衡这个树。

> 线搞搞预备知识 简单的一逼

### 2.0 二叉排序树（也叫二叉查找树） ###

#### 2.1 定义 ####

他或者是一科空树

或者是一颗这样的树

1.  若他的左子树不为空 则左子树的所有节点值小于根结点的值
2.  若他的右子树不为空，则右子树上的所有节点的值都大于根节点
3.  他的左右子树均是二叉排序树

对二叉排序树进行中序遍历，就会得到一个按关键码的有序序列 这也就是二叉排序树的由来

#### 2.2 存储结构 ####

二叉链表

#### 2.3 操作 ####

#### 2.3.1 插入 ####

伪代码

1.0 如果root是空树 就把节点s插入
    2.0 否则  如果s的值小于root 就插入左子树  大于就插入右子树

代码：

void InsertBST(Node* root,Node* s){
    
    if(root == NULL) root = s;
    else if(s->data < root->data){
        InsertBST(root->lchild,s);
    }else{
            InsertBST(root->rchild,s);
    }
    
    }

#### 2.3.2 二叉排序树的构造 ####

这个就是不断调用上面插入函数

BST(int a[],n){
       //数据在数组a[]中
        for(int i = 0;i < n;i++){
                s = new Node;
                s->data = a[i];
                s->lchild = s->rchild  = NULL;
                InsertBST(root,s);
        }
    }

#### 2.3.3 删除 ####

因为插入的时候都是作为叶子结点的 不影响树的结构 所以比较简单.  
但是删除的时候会更改树结构 所以比较复杂一些

1.  删除二叉树中值最小的点  
    怎么找到最小的结点呢？很简单毕竟我们的额二叉树是排序的

就是沿着左子树下移找到最左下的结点

然后删除 同时让这个节点的父节点的左孩子指向这个节点的右孩子，因为这个节点肯定没有左孩子  
2. p为叶子节点  
直接删除就ok  
3. p只有左子树 pl 或者右子树 pr  
让这个节点的父节点的左孩子指向这个节点的左孩子或者右孩子就可以  
4. p 既有左子树又有右子树  
这个一个简单但是代价大的方法就是

让这个节点的父节点的左孩子指向这个节点的其中一个孩子节点 然后把另一个孩子节点重新插入  
一般来说没人这么搞 因为增加了二叉排序树的高度 并且结构也变了

一般这么搞

简单的理解就是 找到这个节点p的左孩子的右孩子 或者右孩子的左孩子 我们把找到的这个节点叫做节点s  
（实际上不是这么的 实际上是找这个节点右子树中的最小值 或者左子树中的最大值）

然后我们把p->data = s->data;

然后删除节点s 就ok了

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

图中是删除47的两种情况 至于原理吗 自己想吧 不懂留言吧

所以删除节点f的左孩子p的伪代码描述如下：

1.0 如果节点p是叶子结点 直接删除
    2.0 如果节点p只有左子树 就重新连接p的左子树
    3.0 如果节点p只有右子树 就重新连接p的右子树
    4.0 如果节点p的左右子树都存在 则
        4.1 查找节点p的右子树的左下节点s 以及s的双亲结点par
        4.2 让p->data = s->data;
        4.3 如果p的右孩子没有左子树，
        4.4 那么就把s的右子树接到par的右子树上
        4.5 否则 s的右子树接到par的左子树上
        4.6 删除s

#### 2.3.4 查找 ####

这个就是按照插入的算法 如果相等 那么就返回 如果不相等 或者说待查找的子树是空 那么就说明是查找失败

### 3.0 AVL树 ###

#### 3.1 为什么要搞这个 ####

很简单 为了效率 也就是操作方便 一个形态均衡的二叉排序树的查找效率会很高

#### 3.2 什么叫平衡二叉树 ####

他要么是一颗空的二叉排序树，要么就有如下性质的二叉排序树

1.  根结点的左右子树均是平衡二叉树
2.  根节点的左子树与有子树的深度最多不能差1

#### 3.3 掌握几个概念 ####

1.结点的 平衡因子

结点的左子树的深度-该结点的右子树深度  
2. 最小不平衡子树

距离插入结点最近的不平衡子树

下图中的7-13 结点的数字代表该节点的平衡因子

![这里写图片描述][70 1]

![这里写图片描述][70 2]

#### 3.4 假设A是最小不平衡子树的根结点 对该子树调整分为以下四种情况 ####

关于下面的图 我建议先看书中的图 看懂之后再看一下文字说明就ok了

##### 3.4.1 LL #####

简单说一下什么是LL 就是插入的点在A的左孩子的左子树上 这里的重点是调整后 根据旋转优先法则  
旋转过来的结点作为新的根结点的右子树 原来的右子树变为新的右子树的左子树 就是右子树变为左子树

具体怎么搞看上面的图中说明 由于需要许多图 所以我直接把书上的内容照下来了

##### 3.4.2 RR #####

这个就是插入的结点在A的右孩子的右子树上 就是RR 针对子树冲突问题 还是原来的右子树变为左子树具体看图  
![这里写图片描述][70 3]

##### 3.4.1 LR #####

![这里写图片描述][70 4]

##### 3.4.1 RL #####

理解了LR 就很容易理解RL了  
![这里写图片描述][70 5]

[70]: /images/20220525/68859cda67a74dbc924a2055faac41a8.png
[70 1]: /images/20220525/3a9024684fce44bf9825eefc3e857606.png
[70 2]: /images/20220525/0a61d1115010446bb3d03fc23708407e.png
[70 3]: /images/20220525/ab7b178bed484a0fb79691457f817a14.png
[70 4]: /images/20220525/e567d8c9e86f405ebd8e1e94dc039a3a.png
[70 5]: /images/20220525/85f3fc9ad6c841d7b65a60204a52da0a.png