C++ - AVL 树 介绍 和 实现 (上篇)

前言

 之前我介绍了 二叉搜索树,可看一下博客:C++ - 搜索二叉树_chihiro1122的博客-CSDN博客
二叉搜索树的效率可以达到 O(log n) 。这个复杂度的算法的效率是非常恐怖的,2 的 30 次方大概是 10亿左右。也就是说 如果用暴力查找 需要找 10 亿次,而 最好的效率的二叉搜索树 只用搜索 30 次。是非常恐怖的。

为什么说是 最好效率呢?因为 二叉搜索树有一个弊端,他不是平衡的,在最极端情况下 会退化成类似链表的结构。此时的 时间复杂度就到了 差不多 O(N)了,基本和链表顺序暴力查找没什么区别了 。

所以在上述二叉搜索树的基础之上,为了防止弊端,就有了AVL 树的存在。

关于文章当中的旋转部分的介绍,主要是 左单旋当中最为详细。

AVL树概念 

 AVL树是 二叉平衡搜索树的一种,红黑树也是二叉搜索树的一种,但是两者之间区别很大。

 我们知道,如果一组数据有序或者接近有序,这个可以二叉搜索树会退化成链表的情况,也就是会所单树枝的情况,此时效率相当于是 顺序表的暴力查找。所以,有人就想,如果这棵二叉搜索树的每个结点的高度差不超过1(如果对数当中进行某些操作调整的话),那么这个棵树的 增删查改的时间复杂度就会稳定在 高度次,也就是 O(log N)

 如上所示就是一个 二叉平衡搜索树,如果我们想构建一个AVL树,方法有很多,这里我们使用 平衡因子 的方式来帮助我们构建这个 AVL树。

首先我们来了解一下什么是 平衡因子。

平衡因子:任何一个结点都有平衡因子,一个结点的平衡因子是 这个结点的 右子树的高度 - 左子树的高度

  一个 AVL树 或者是 空树,他们都是在二叉搜索树当中多加了以下两个条件:

  • 一个结点的左右子树都是 AVL 树
  • 每个结点的左右子树高度之差(平衡因子)的绝对值不超过1(1/0/-1)。

 这里 平衡因子不是 0,是因为 如果 平衡因子是 0,那么这棵树就是一个 满二叉树,我们随机插入的结点个数不可能时时都满足 满二茶树的结点个数。比如:树当中只有2 个结点,或者4个结点都不好做到 平衡因子相等。

 AVL树实现

 大体框架

 直接实现 key-value模型的 AVL树;用 pair 类模版来对应存储一个 键值对。

每一个结点上,除了有一个 pair 对象存储键值对,左孩子 右孩子指针之外,还有一个 指向这个结点的父亲的指针。在此 AVL树当中,一个结点有三个链接关系。还有这个结点的 平衡因子 _bf。

template<class K, class V>
struct AVLTreeNode
{pair<K, V> _kv;AVLTreeNode* _left;AVLTreeNode* _right;AVLTreeNode* _parent;int _bf;  // 平衡因子AVLTreeNode(const pair<K, V>& kv):_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_bf(0)()
};template<class K, class V>
class AVLTree
{// 给结点类重命名,方便以后写typedef AVLTreeNode<K, V> Node;// 构造函数使用默认构造函数public:// 成员函数private:Node* _root = nullptr;
};

insert()插入函数

 insert()在首次寻找插入位置,和 普通的 二叉搜索树的插入 算法是一样的,只不过在插入之后,要判断对应结点的 平衡因子是否符合要求。同时,对于插入一个结点要影响那些结点的平衡因子,怎么影响,我们在下述当中讨论。

先把首次插入部分写出:
 

	bool insert(const pair<K, V>& kv){// 如果当前树为空,直接用头指针只想新结点if (_root == nullptr){_root = new Node(kv);return true;}// 不为空接着走Node* cur = _root;    // 用于首次插入时候指针的迭代Node* parent = _root; while (cur){// 如果当前新插入的 key 值比 当前遍历的结点 key 值大if (cur->_kv->first < kv.first){// 往右迭代器parent = cur;cur = cur->_right;}// 反之else if (cur->_kv->first > kv.first){parent = cur;cur = cur->_left;}else{// 如果相等,就不插入,即插入失败return false;}}// 此时已经找到 应该插入的位置cur = new Node(kv);// 再次判断大小,判断 cur应该插入到 parent 的那一边if (parent->_kv->first < kv.first){parent->_right = cur;}else{parent->_left = cur;}// 链接 新插入结点 cur 的_parent 指针cur->_praent = parent;// 利用平衡因子控制平衡//·········// 插入成功,返回 truereturn true;}

现在还有一个问题,是 利用平衡因子来控制 平衡。

平衡因子 控制平衡

我们先来看下述三种情况:

 利用 平衡因子 控制平衡的逻辑:

  •  当我们在 parent 的左右两边插入的时候,都有可能会影响 parent 这个结点的 平衡因子,而当 parent 的平衡因子被修改,parent 的 _parent 指针 一直链接到 根结点的 这一个 父类链 都有可能会修改。比如:第二个例子。在 6 的右边插入一个 cur ,6 的平衡因子修改了,同时,cur 的插入,影响到了 7 这个结点的 平衡因子;
  • 但是不是一个 结点的 平衡因子 修改了 ,一定会影响其父类结点。
  • 我们发现,当在某一个结点的左右孩子插入一个结点之后,这个结点的平衡因子被修改为了 0 ,那么,从这个结点网上链接的 父亲结点,都不会被修改
  •  而且,我们发现,当在 parent 结点的左右孩子插入 cur 之后, parent 结点的 平衡因子 的修改是有规律的,因为 结点的 平衡因子的 计算是 这个结点的 右子树高度 -  左子树高度。
  • 所以,当在 parent 的右边插入结点的时候,parent 的平衡因子 ++;当在 parent 的左边插入结点的时候,parent 的平衡因子 --;这个逻辑可以一直用到上述 在 往 root 根结点的 父亲结点的 平衡因子的修改。
  •  当 parent 的平衡因子 更新之后,变成0 了,说明这个 parent 的左右子树都平衡了,不会在影响 parent 的父亲了,不用在继续往上更新了
  •  当 parent 结点的平衡因子在修改之后,是 1 或者 -1 ,那么,说明这个 parent 的平衡因子的修改还是会影响到 parent 的父亲结点的 平衡因子,所以还是要继续往上更新。
  • 当 parent 结点的 平衡因子 在修改之后,是 2 或者 -2 ,那么,说明 新结点 的插入,影响了 这个 parent 结点的 平衡因子的 有效性,此时 parent 的对应子树已经不是 平衡的了
  •  而且,parent 结点的 平衡因子 在修改之后,是 2 或者 -2已经失衡了,就不用在网上更新了,因为,此时我们就要对 parent 这颗子树进行旋转,让这个棵子树平衡,当这个子树平衡之后,这颗子树的 父亲也就不需要在 更新 平衡因子了
  •  而且,parent 结点的 平衡因子在更新之后,不能是 3 或者 -3 这些比 2 更大的值,因为如果出现了,就代表在之前 就出现问题,也就是 前面有结点的 平衡因子 已经 被更新为 2 或者 -2 了,这对于上述的逻辑不符。
  • 一路往上更新父亲结点的 平衡因子,最多会更新到 root 根结点,如果一直更新到 root 根结点都没有出现 2 或者 -2 的话,那么说明新插入的结点,没有影响任何子树的 平衡因子的有效性。所以,更新到根结点之后就不用再更新了。也就是更新到当前结点的父亲结点为 nullptr 的时候,说明当前结点已经是 根结点了,后续即不用再更新了。
  • (此时就可以看出 结点的 _parent 指针的好处了,不仅可以帮助我们往上修改 父亲结点的 平衡因子,还可以帮我们判断是否到达 根结点)
左单旋过程说明 :

左单旋: cur 为 1 ,parent 为2 就是左单旋。如下图所示:

上述都是在右孩子处插入结点使得平衡失效,所以,我们首先的核心操作是把 这颗不平衡的右子树 移到 左边去,这样才能是实现平衡。

旋转之后要注意的问题:

但是,不能单纯的左移旋转,旋转之后,我们得保证这整棵树还是一个 搜索树,而且这颗树还得是平衡树。

左旋的核心修改步骤:
 

通过上述两个例子我们可以发现,我们要修改修改的是 parent 的平衡因子为 2 或者 -2 的这一刻子树,也就是上图标出的 parent 和 cur 的这一棵子树,对于 parent 和 cur 这两棵链接的结点,左旋就是把 cur 的 左孩子(可能为nullptr)给parent的右孩子,parent 成为 cur 的左孩子,以这种链接关系来实现左旋。

如下就是左单旋核心的代码 :

parent->_right = cur->_left;
cur->_left = parent;

左单旋向上述做的原因:

实际上, 左单旋完成的事情就是,当前 parent 的平衡因子为2 ,太高了,就把 parent 一下一层,移到 cur 的左孩子处,因为cur 的左孩子不一定为空,所以先要把 cur 的 左孩子 移动到 ,parent 的右孩子处,因为 在移动之前,cur 本来就是 parent 的右孩子;移动之后,parent 的右孩子位置就空出来了。(降低这颗子树的高度)

这个过程一直在做一件事情,保持这棵树是一颗搜索树。我们发现,我们移动的是 parent 的有孩子 ——cur 的左孩子,cur 的左孩子还是在 parent 的右边,只要是在 parent 右边的结点,在搜索树当中都是要比 parent 要大的。

因为上述操作降低这颗子树的高度,所以这颗原本不平衡的子树,现在一下平衡了,那么如果这颗子树有父亲结点,就不需要在工更新这棵子树的 父亲结点的 平衡因子。因为已经平衡了。

左单旋代码实现:

void RotateL(Node* parent){Node* cur = parent->_right; // 存储 parent 的右孩子Node* curleft = cur->_left; // 存储 cur 的左孩子parent->_right = curleft;  if (curleft)                // 判断 cur 的左孩子是否为空{ curleft->_parent = parent;  // 不为空就 修改 cur 的左孩子的_parent 指针}cur->_left = parent;// 留存一份 根结点指针Node* ppnode = parent->_parent;parent->_parent = cur;// 如果parent 是根结点if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}// 修改之后 两个结点的 平衡因子都是 0 了parent->_bf = cur->_bf = 0;}


 其实左单旋当中,上述情况都是单一的两个例子,下述才是包含左左-左单旋当中所有的情况。

 左左,左单旋的示意图:

 上述表示,除了 30 和 60 之外,下述的可能是一个孩子,也有可能是一颗子树,当 h == 0 ,或者 h == 1,的情况我们上述的两个单一的例子就已经说明了,

现在我们主要来看 当 h == 2的情况:

当 h >= 2 之后的情况,说明30 和 60 的下面不再是孩子结点,而是一颗子树,而子树就有很多种情况了,比如 当 h == 2 的时候,对于 高度为 2 的子树就有三种情况
 

 如上图所示,当h == 2 的时候,对于 a 和 b 两棵子树就有 x/y/z 三种情况;而对于子树 c 就只可能有 z 这一种情况

因为,假设 c 是 x 或者 y 这两种情况,在插入之前,这颗c子树就已经有点往右边高的倾向了,当在 后序的左边或者右边插入一个结点之后,这颗子树已经不平衡了,不平衡就要发生旋转(逻辑因为是在c子树出插入结点,所以要旋转还是按照左左的方式旋转),而旋转之后,c这颗子树就平衡了。

比如 此时 c 就是 y 这种子树,假设是往子树根结点的左边插入新结点,形成的新的子树就是 z 这种形状的平衡子树,如果是在 根的右孩子的 左右孩子插入结点,那么这棵子树就不平衡了。就要往上更新父亲结点的 平衡因子,当更新到 c 子树的根结点的时候,发现此时 根结点的 平衡因子就不符合规则了,就需要旋转,而旋转之后就是 z 这种 的 子树。

那么,按照上述的逻辑,c子树只能是 z 这种形状的子树,那么当有新的结点的在 c 的后面插入之后,就会引发 c 子树根结点的平衡因子变化,从 0 -> 1。从而就会影响到 整棵树的根结点 30 的平衡因子的变化,1->2,此时就会在 根结点 30 为 paren来旋转。

所以,当 h == 2 的时候,插入之前 这颗数的形状就有 3 * 3 * 1 = 9种;插入新结点的位置就有 4 个位置(即 c 子树的 左右孩子的 左右孩子,总共6中情况)。所以,插入之后 这棵树就有 36 种情况。

我们发现,h == 2 的时候,所引发的情况已经很多了,而且 h 还有 3 4 5 ······等等。

纵使情况很多,但是其实 实现的规则都是一样的,还是按照上述的 左单旋的方式来处理,为什么可以按照上述来处理呢?如下图:

 上述当中, 30 结点的平衡因子已经 == 2了,此时 30 就作为 parent, 60 作为cur,然后来左单旋。 所以就要把 b 这颗子树 给给 30 的右指针,60  的左指针直线 30 ,让 60 作为根结点。

我们为什么可以像上述一样操作呢?因为 b 是已经是一颗 二叉平衡搜索树了,而且 b 其中的结点都比 30 大,都比 60 小,满足作为 30 右子树的条件,加上 30 又满足作为60 的左子树的条件

 而且修改之后 ,30 和 60 的平衡因子都是 0 ,也就是说 旋转之后,parent 和 cur 两个结点的平衡因子都是 0


左单旋当中需要注意的问题:

  • 上述对左单旋的核心代码做出了说明,但是,实际当中还有一些细节,如果只是用单纯的 核心代码是不能实现左单旋的:
  • 除了修改左右孩子的指针,我们使用的是三叉链的结构,还需要修改 parent 和 cur 的_parent 指针。
  • 而且,在上述修改 cur 的左孩子的_parent 指针的时候,还需要判断 cur 的左孩子 是否为空,不为空再去修改。
  • 我们修改的可能是 parent 位于根结点的,还有可能是 一颗子树,如果是一颗子树,说明在 parent的上面还有结点,而且,在旋转之后,这颗子树的根结点不再是 parent了,而是 cur,cur 的父亲结点应该指向 原本 parent 的 _parent 指针指向的结点。也就是说,我们在修改 parent 的 _parent 指针指向的时候,还需要把 原本 parent 的 _parent 指针指向的结点 留存一份,不然修改之后就找不到了。
  • 上述是 parent 的 _parent 指针指向的结点 不为空的情况,也就就是修改的是子树的情况。还有一种情况是 parent 本来就是这整棵树的根结点,此时只需要直接修改 旋转之后 cur 的 _parent指针指向nullptr 就行了。
  • 如果 此时 到 parent 和 cur 旋转,就代表着 parent 和 cur 的子树都是 平衡搜索树。
右单旋过程说明:
void RotateR(Node* parent){Node* curRight = cur->_right;Node* cur = parent->_left;parent->_left = curRight;if (curLeft){curLeft->_parent = parent;}cur->_right = parent;Node* ppnode = parent->_parent;parent->_parent = cur;if (parent == _root){_root = cur;cur->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}cur->_parent = ppnode;}parent->_bf = cur->_bf = 0;}

右单旋和 左单旋 实现过程其实差不多,两者之间只是旋转的方向不一样,比如之前的 parent 和 cur 的关系是 父亲的 和 右孩子的关系,这个时候如果 父亲的平衡因子 不有效的话就需要左单旋,而 需要右单旋的情况是 cur 是 parent 的左孩子,此时需要右单旋;

右单旋 和 左单旋旋转方式就像是 对称一样,右单旋 就是把cur 的右孩子 给给 parent,然后使得 parent 作为 cur 的右孩子。

右单旋代码实现:

 

 左右双旋 和 右左双旋 的 过程说明:

上述 两个单旋,比如左单旋就是 在parent的右孩子 的 右子树,或者说是在 cur 的 右子树上插入结点才会进行左单旋;在parent的左孩子的左子树,在cur 的左子树上插入结点会进行右单旋。如下所示:

 但是如果反过来,比如 上述左单旋的例子,不在 c 上插入新结点而是在 b 上插入新结点;上述右单旋例子,不在 a 上插入结点,而是在 b 上插入结点;如果只是进行单纯的 左单旋或者 右单旋是不能解决问题的

 比如上述,如果只是进行单纯的左单旋之后,变成如下模样:
 

 发现,旋转之后依然是不平衡的

再看这个例子:

也就是说,此处一次 左单旋是不能解决问题的,插入结点之后 30 的 平衡因子变为了2,我们此时就像使用 左单旋把 30 这颗子树 旋转平衡,就要满足 左单旋的 旋转结构,所以,这里如果我们想使用 左单旋把 30 这颗子树 旋转平衡,就要线使用 右单旋 旋转 60 这颗子树,使得旋转之后,30 这颗子树满足 左单旋的 结构。

当  60 右单旋之后
 

发现,把60 这颗子树进行右单旋之后, 30 这棵树就满足左单旋的 结构了,此时我们在进行左单旋就可以平衡 30 这颗树:
 

 上述就是 右左双旋的过程,同样的 ,左右双旋 类似,只不过树高的位置不同而已,但是过程完全一样,旋转是对称的。

判断 单旋还是双旋,只需要判断需要旋转的子树是沿着根结点是一条直线还是一条 折现;如果是一条直线,只用单旋就可以解决,如果是一条折现,需要双旋
 

 也就是说:

  • 如果 parent 的平衡因子 = 2,cur 的平衡因子 = 1,说明,只是单纯的左边高,只需要进行左单旋;
  • 如果 parent 的平衡因子 = -2,cur 的平衡因子 = -1,说明只,只是单纯的右边高,需要进行右单旋;
  • 如果 parent 的平衡因子 = 2,cur 的平衡因子 = -1,说明,此时是一条折线 需要进行右左双旋;
  • 如果 parent 的平衡因子 = 2,cur 的平衡因子 = 1,说明,此时是一条折线 需要进行左右双旋;

 右左旋转代码:

	//直接复用 左单旋和右单旋void RotateRL(Node* praent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0)       // 平衡因子为 0{cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0;}else if (bf == 1)       // 平衡因子为 1{cur->_bf = 0;curleft->_bf = 0;parent->_bf = -1;}else if (bf == -1)       // 平衡因子为 -1{cur->_bf = 1;curleft->_bf = 0;parent->_bf = 0;}else                  // 平衡因子为 不可能为其他值,如果是 ,说明程序写的有问题{assert(false);}}

但是,上述只是旋转部分代码。之前说过,单旋之后,parent 和 cur 两个结点的平衡因子一定是 0 ,但是双旋不一样,双旋之后两个结点的 平衡因子不一定是 0 ,而且在分析看来是随机的。

其实双旋的本质是(如上述例子):

  • 把 60 的左边给 30 的右边;
  • 把 60 的右边给 90 的左边;
  • 60 就成了这颗树的根。

 但是上述是在 60 的左边插入新的结点,如果是在 60 的右边插入结点,结果就不一样了:
 

 我们发现,两种情况再同一双旋当中的位置都不一样。

根据插入位置的不同,旋转之后新结点位置也会不一样,那么就导致不同的插入结果对于 parent 和cur两个结点的平衡因子就有不同的结果。

 那么我们要区分上述两种情况才能解决 平衡因子的问题,我们发现,可以用 60 的平衡因子 来判断 新插入的结点是插入在左孩子还有在右孩子的,如果平衡因子是 1 则在 60 的右孩子位置插入;如果平衡因子是 -1 则在 60 的左孩子位置插入

 但是,还有一种情况,就是 60 的平衡因子是 0 ,也就是 60 本身就是 新插入的结点的情况也会发生双旋:

 上述是 h == 1 ;h == 2 的情况,和 单旋一样,h 可能有很多值,但其实也是和 单选一样,都是一样的处理方式:

 如果 h == 0,此时 60 结点就是 新插入的结点;如果 h > 0 就是上图当中一样的模型,有两种方式的插入可以诱发双旋。

  • 当在 c 子树当中插入结点,诱发的双旋结果如上,关于 60 30 90 这三个结点的平衡因子 分别是 -1 0 0。
  • 当 h == 0 时候,60 30 90 三个结点的 平衡因子 都是 0。
  • 当在 b 子树当中插入结点,诱发的双旋结果如喜爱,关于 60 30 90 这三个结点的平衡因子 分别是 0 0 1。

 上述是 b 子树 或者是 c 子树的 高度 从 h -1 变为了h (相当于是插入了结点),所诱发了两种不同的 双旋,而 b 和 c 两个子树的高度不可能同时为 h ,因为,如果 b c 两个子树的 高度同时为 h 的话,60 这个结点的 平衡因子就是 0了,那么当 60 这个 平衡因子已经是 0 就不会在网上更新 平衡因子,也就不会在诱发双旋。

 所以,右左双旋的代码如下:

	//直接复用 左单旋和右单旋void RotateRL(Node* praent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;RotateR(parent->_right);RotateL(parent);if (bf == 0)       // 平衡因子为 0{cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0;}else if (bf == 1)       // 平衡因子为 1{cur->_bf = 0;curleft->_bf = 0;parent->_bf = -1;}else if (bf == -1)       // 平衡因子为 -1{cur->_bf = 1;curleft->_bf = 0;parent->_bf = 0;}else                  // 平衡因子为 不可能为其他值,如果是 ,说明程序写的有问题{assert(false);}}

 注意

  • 上述我们在实现单旋函数的时候,其中已经对 两个结点的 平衡因子 修改为0了,那么对于双旋当中,在旋转之后,判断情况修改平衡因子的三种情况当中,就有全部改为 0 的情况,此时有人就问,那么我们在外部是不是可以就不对 全修改为 0 的情况进行修改了呢?
  • 如果按照逻辑是哪个来说,可以不修改。但是从耦合上来说,如果不在 双旋函数当中的对 这种情况进行修改,判断修改,那么这个双旋函数就会依赖上 单旋函数的其中的修改规则,如果以后双旋函数像脱离 单旋函数来使用的或者实现的话,那么还得重写对这种情况进行重写。也就是说不写修改0 的话,双旋函数和单旋函数耦合性就变强了。

 对于 左右旋转,和 上述说明的右左旋转是完全类似的,讨论的情况都是一样,要发生 左右旋转,同样是三种情况:

 首先是 60 本来就是 新增的结点;

其次两种是各自在 b 或者 c 子树当中插入结点。

只是旋转方式不同,但是左右双旋和右左双旋两者之间旋转方式是对称的。和 右单旋,左单选一样。

两者的本质都是把 60 的左右子树瓜分在 30 和 90 的下面。30 和 90 分别做了 60 的左右。

对于 左右双旋的 三种情况的判断,同样是判断 60 的平衡因子:

  • 是0 的时候,说明此时 60 就是 新增的结点;
  • 是1 的时候,说明在 c 子树当中插入,此时 30  60 90 三者的 平衡因子是 -1 0 0
  • 是 -1 时候,说是在的 b 子树当中插入,此时 30 60 90 三者的 平衡因子分别是 0 0 1。

具体过程就不画了,过程和 有做双旋当中差不多,按如下图是 在b  子树插入情况示意图:
 

左右双旋 代码实现:

 

void RotateLR(Node* praent){Node* cur = parent->_right;Node* curleft = cur->_left;int bf = curleft->_bf;RotateL(parent->_left);RotateR(parent);if (bf == 0)       // 平衡因子为 0{cur->_bf = 0;curleft->_bf = 0;parent->_bf = 0;}else if (bf == 1)       // 平衡因子为 1{cur->_bf = -1;curleft->_bf = 0;parent->_bf = 0;}else if (bf == -1)       // 平衡因子为 -1{cur->_bf = 0;curleft->_bf = 0;parent->_bf = 1;}else                  // 平衡因子为 不可能为其他值,如果是 ,说明程序写的有问题{assert(false);}}

 

总结旋转

 在旋转过程当中,我们一直强调上述的两个或者是三个结点的平衡因子,而修改的也只是这两三个结点的平衡因子,这是因为每一次遇见不符合规则的 平衡因子的结点只会遇到一个,那么我们就只需要使用 左单旋或者右单旋来平衡这个结点为 根结点的子树,但是,这个子树不一定是 满足左单选 或者 右单旋的结构,所以这时候,在左单旋或者右单旋 之前,还要在 把下面的结构旋转一下,使之构成符合 该子树根结点开始 单旋的结构。

但是在单旋的过程当中,只是对这 两个或者 三个结点进行 链接上是修改,对于他们的 以上所以父亲结点(除 当子树根结点不是 整棵树的根结点时候,需要修改子树根结点和上一个父亲结点链接关系,但是这种情况也只需要修改一个父亲结点的链接关系),还有三个结点的子树,都是整体跟着一起旋转的,不会受到影响。因为父亲的 改变不会影响到 孩子的 平衡因子,孩子的 改变可能会影响到 父亲的 平衡因子。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/137342.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

护网行动,最全攻略来啦!!!

随着网络技术的不断发展&#xff0c;网络领域被发现的安全威胁越来越多。 病毒入侵、数据窃取、网络攻击等安全事件时常发生&#xff0c;网络已然成为各国无声较量的重要战略空间。 为应对网络安全威胁&#xff0c;严守网络安全底线&#xff0c;公安部自2016年开始组织多家机构…

Windows:虚拟内存的使用

文章目录 简介如何开启并设置虚拟内存如何查看虚拟内存参考文献 简介 windows里什么是虚拟内存&#xff1f; 其实类似Linux里的交换内存/交换页&#xff0c;即将硬盘上一块空间作为虚拟的内存&#xff0c;当物理内存不足时&#xff0c;则可以将不常用的数据从物理内存中转移到…

Godot 和 VScode配置C#环境注意事项

前言 尽管有些博主会建议如果我们熟悉C#的话&#xff0c;最好还是使用GDscript&#xff0c;而且对于小白上手也相对简单&#xff0c;但是C#的性能终究还是比动态语言好&#xff0c;也相比CPP简单些&#xff0c;尽管现在Godot还是有些问题&#xff0c;比如不像unity那样适配swit…

学习笔记-接口测试(postman、jmeter)

目录 一、什么是接口测试 二、前端和后端 三、get请求和post请求的区别 四、cookie和session 五、接口测试的依据 六、HTTP状态码 七、通用接口用例 八、postman接口测试 九、Jmeter接口测试 一、什么是接口测试 通常做的接口测试指的是系统对外的接口&#xff0c;比…

【Spring面试】八、事务相关

文章目录 Q1、事务的四大特性是什么&#xff1f;Q2、Spring支持的事务管理类型有哪些&#xff1f;Spring事务实现方式有哪些&#xff1f;Q3、说一下Spring的事务传播行为Q4、说一下Spring的事务隔离Q5、Spring事务的实现原理Q6、Spring事务传播行为的实现原理是什么&#xff1f…

MySQL数据库查缺补漏——基础篇

MySQL数据库查缺补漏-基础篇 基础篇 net start mysql80[服务名] net stop mysql80 create database pshdhx default charset utf8mb4; 为什么不使用utf8&#xff1f;因为其字符占用三个字节&#xff0c;有四个字节的字符&#xff0c;所有需要设置为utf8mb4; 数值类型&…

SpringCloud Ribbon--负载均衡 原理及应用实例

&#x1f600;前言 本篇博文是关于SpringCloud Ribbon的基本介绍&#xff0c;希望你能够喜欢 &#x1f3e0;个人主页&#xff1a;晨犀主页 &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是晨犀&#xff0c;希望我的文章可以帮助到大家&#xff0c;您的满意是我的动力…

​​​​MyBatis友人帐之基础入门

一、简介 1.1什么是MyBatis MyBatis 是一个开源的、轻量级的数据持久层框架&#xff0c;它可以简化 JDBC 的操作&#xff0c;让开发者只需要关注 SQL 语句本身&#xff0c;而不用处理加载驱动、创建连接、创建语句等繁琐的过程。 MyBatis 支持自定义 SQL、存储过程和高级映射&…

Kotlin中函数的基本用法以及函数类型

函数的基本用法 1、函数的基本格式 2、函数的缺省值 可以为函数设置指定的初始值&#xff0c;而不必要传入值 private fun fix(name: String,age: Int 2){println(name age) }fun main(args: Array<String>) {fix("张三") }输出结果为&#xff1a;张三2 …

论文笔记 DETR

detr 摘要和引言 2020论文facebook不需要proposal&#xff0c;不需要基于anchor的先验知识(比如预训练的模型)&#xff0c;也不需要NMS进行筛选&#xff0c;直接端到端不需要后处理利用transformer的全局建模能力&#xff0c;看成集合预测问题&#xff0c;不会输出很多冗余的…

浅谈DBT的一些不足之处

DBT的好处是显而易见的&#xff0c;它支持连接多达41种数据库。而且不需要你写DDL语句&#xff0c;只要写select语句&#xff0c;DBT会自动帮你推断schema结构&#xff0c;将数据写入到数据库中&#xff1a; 但是使用了一段时间之后&#xff0c;发现DBT也存在着如下这些不足之处…

竞赛 基于机器学习与大数据的糖尿病预测

文章目录 1 前言1 课题背景2 数据导入处理3 数据可视化分析4 特征选择4.1 通过相关性进行筛选4.2 多重共线性4.3 RFE&#xff08;递归特征消除法&#xff09;4.4 正则化 5 机器学习模型建立与评价5.1 评价方式的选择5.2 模型的建立与评价5.3 模型参数调优5.4 将调参过后的模型重…

JumpServer未授权访问漏洞 CVE-2023-42442

JumpServer未授权访问漏洞 CVE-2023-42442 一、漏洞描述二、漏洞影响三、网络测绘四、漏洞复现poc通过burp发送请求包小龙POC检测 五、修复建议 免责声明&#xff1a;请勿利用文章内的相关技术从事非法测试&#xff0c;由于传播、利用此文所提供的信息或者工具而造成的任何直接…

Redis代码实践总结

一、背景&#xff1a; redis从安装到实践&#xff0c;做一些具体的记录。 1.1 Redis和 RedisStack和Redis Enterprise redis简介 Redis 是一种开源&#xff08;BSD 许可&#xff09;内存中数据结构存储&#xff0c;用作数据库、缓存、消息代理和流引擎。 Redis 提供数据结构…

(JavaEE)(多线程案例)线程池 (简单介绍了工厂模式)(含经典面试题ThreadPoolExector构造方法)

线程诞生的意义&#xff0c;是因为进程的创建/销毁&#xff0c;太重了&#xff08;比较慢&#xff09;&#xff0c;虽然和进程比&#xff0c;线程更快了&#xff0c;但是如果进一步提高线程创建销毁的频率&#xff0c;线程的开销就不能忽视了。 这时候我们就要找一些其他的办法…

pte初步认识学习

我们的时间的确很少&#xff0c;但是我们每天都乐意将珍贵的时间浪费在大量毫无意义的事情上 目录 pte介绍 PTE口语评分规则 pte架构 计算机科学23 QS排名 《芭比》 pte介绍 PTE口语评分规则 有抑扬顿挫 对于连读 不能回读 native pte对于个别单词没有读好&#xff0c…

【探索C语言中VS调试技巧】:提高效率和准确性

文章目录 前言1. 什么是bug&#xff1f;2. 调试是什么&#xff1f;有多重要&#xff1f;2.1 调试是什么&#xff1f;2.2 调试的基本步骤2.3 Debug和Release的介绍 3. Windows环境调试介绍3.1 调试环境的准备3.2 学会快捷键3.3 调试的时候查看程序当前信息3.3.1 查看临时变量的值…

C语言生成随机数、C++11按分布生成随机数学习

C语言生成随机数 如果只要产生随机数而不需要设定范围的话&#xff0c;只要用rand()就可以&#xff1b;rand()会返回一随机数值, 范围在0至RAND_MAX 间&#xff1b;RAND_MAX定义在stdlib.h, 其值为2147483647&#xff1b; 如果想要获取在一定范围内的数的话&#xff0c;直接做…

【数据分享】2023年全国地级市点位数据(免费获取\shp格式\excel格式)

地级市点位数据是我们各项研究中经常使用到的数据&#xff0c;在之前的文章中我们分享过2022年度的地级市及以上城市的点位数据&#xff08;可查看之前的文章获悉详情&#xff09;。本次我们带来的是2023年度的全国范围的地级市及以上城市的点位数据&#xff0c;点位位置为市政…

大数据Flink(八十四):SQL语法的DML:窗口聚合

文章目录 SQL语法的DML:窗口聚合 一、滚动窗口(TUMBLE)