【C++】手撕AVL树

> 作者简介：დ旧言~，目前大二，现在学习Java，c，c++，Python等
> 座右铭：松树千年终是朽，槿花一日自为荣。

> 目标：能直接手撕AVL树。

> 毒鸡汤：放弃自己，相信别人，这就是失败的原因。

> 望小伙伴们点赞👍收藏✨加关注哟💕💕 

🌟前言  

相信大家肯定听过在C++大名鼎鼎的两颗树，这两颗树分别是AVL树和红黑树，学过的小伙伴听到都是瑟瑟发抖，像一些大厂中可能会考手撕AVL树或红黑树。学习这两棵树确实难度很大，正所谓难度越大动力就越大，那本篇我们学习这两棵树的一颗树--AVL树。

⭐主体

学习AVL树咱们按照下面的图解：

🌙AVL树的概念

在计算机科学中，AVL树是最早被发明的自平衡二叉查找树。在AVL树中，任一节点对应的两棵子树的最大高度差为1，因此它也被称为高度平衡树。查找、插入和删除在平均和最坏情况下的时间复杂度都是O(logn)。

AVL树的定义

  • 一棵空的树是AVL树
  • 如果T是一棵非空的二叉树，T(L)和T(R)分别是其左子树高和右子树高，那么当T满足以下条件时，T是一棵AVL树，|h(L)-h(R)|<=1，其中h(L)和h(R)分别是T(L)和T(R)的高（简称平衡因子）

AVL树的状态：

AVL树的特性：

  • 一棵n个元素的AVL树，其高度是O(logn)
  • 对于每一个n，n>=0，都存在一棵AVL树
  • 对一棵n元素的AVL搜索树，在O(高度)=O(logn)的时间内可以完成查找
  • 将一个新元素插入一棵n元素的AVL搜索树中，可以得到一棵n+1个元素的AVL树，而且插入用时为O(logn)
  • 一个元素从一棵n元素的AVL搜索树中删除，可以得到一棵n-1个元素的AVL树，而且删除用时为O(logn)

🌙AVL树的结点

  • 按照 KV 模型来构造 AVL 树，需要把结点定义为 三叉链结构（左、右、父）。
  • 构造函数，由于新构造结点的左右子树均为空树，所以将新构造结点的平衡因子初始设置为 0 。

代码示例：

// 创建AVL树的结点
template<class K,class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;  // 左子树AVLTreeNode<K, V>* _right; // 右子树AVLTreeNode<K, V>* _parent;// 父亲结点pair<K, V> _kv; // 存储的键值对int _bf;       // 平衡因子（右子树高度 - 左子树高度）// 构造函数AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};

🌙AVL树的插入

其实AVL树插入操作，本质上比二叉搜索树的插入操作多了一个平衡操作：

  1. 按照二叉搜索树的方式，找到待插入的位置，然后将新结点插入到该位置。
  2. 调整节点的平衡因子，如果出现不平衡，则需要进行旋转。

当 AVL 树插入一个新结点以后，需要更新插入结点的祖先的平衡因子，因为新结点（也就是叶子结点）的平衡因子为 0，但是它影响的是它的父亲，它父亲的父亲…，所以要更新到祖先结点。

上面的图就需要改变父亲爷爷的平衡因子，我们知道，树的状态有很多，无法穷举，但是我们也有规律可寻，这个规律就在于我们的平衡因子，所以我总结如下：

  • 如果新增结点插入在 parent 的右边，只需要给 parent 的平衡因子 +1 即可
  • 如果新增结点插入在 parent 的左边，只需要给 parent 的平衡因子 -1 即可

当 parent 的平衡因子更新完以后，可能出现三种情况：0，正负 1，正负 2。

（1）parent 的平衡因子为 0

如果parent的平衡因子是0：说明之前parent的平衡因子是1或-1，说明之前parent一边高、一边低；这次插入之后填入矮的那边，parent所在的子树高度不变，不需要继续往上更新。如图：

（2）如果 parent 的平衡因子为正负 1

如果parent的平衡因子是1或者-1：说明之前parent的平衡因子是0，两边一样高，插入之后一边更高，parent所在的子树高度发生变化，继续往上更新。

①parent为1

②parent为 -1

（3）如果 parent 的平衡因子为正负 2

平衡因子是2或-2，说明之前parent的平衡因子是1或-1，现在插入严重不平衡，违反规则，需要进行旋转处理

  • 如果parent的平衡因子是2，cur的平衡因子是1时，说明右边的右边比较高，我们需要进行左单旋
  • 如果parent的平衡因子是-2，cur的平衡因子是-1时，说明左边的左边比较高，我们需要进行右单旋
  • 如果parent的平衡因子是-2，cur的平衡因子是1时，我们需要进行左右双旋
  • 如果parent的平衡因子是2，cur的平衡因子是-1时，我们需要进行右左双旋

这里我们就举一个栗子：

代码实现：

public:// 插入函数bool Insert(const pair<K, V>& kv){// 如果AVL树是空树，把插入节点直接作为根节点if (_root == nullptr){_root = new Node(kv);_root->_bf = 0;return true;}// 1.按照二叉搜索树的规则插入Node* parent = nullptr;Node* cur = _root;while (cur){if (cur->_kv.first < kv.first) // 待插入节点的key值大于当前节点的key值{// 往右子树走parent = cur;cur = cur->_right;}else if (cur->_kv.first > kv.first) // 待插入节点的key值小于当前节点的key值{// 往左子树走parent = cur; cur = cur->_left;}else // 待插入节点的key值等于当前节点的key值{return false; // 插入失败，返回false}}// 2.当循环结束，说明cur找到了空的位置，那么就插入cur = new Node(kv); // 构造一个新节点if (parent->_kv.first < kv.first) // 如果新节点的key值大于当前parent节点的key值{// 就把新节点链接到parent的右边parent->_right = cur;}else // 如果新节点的key值小于当前parent节点的key值{// 就把新节点链接到parent的左边parent->_left = cur;}cur->_parent = parent; // 别忘了把新节点里面的_parent指向parent(因为我们定义的是一个三叉链)// 3.更新平衡因子,如果出现不平衡,则需要进行旋转while (parent) // 最远要更新到根节点去{if (cur == parent->_right) // 如果cur插在parent的右边，说明parent的右子树增高{parent->_bf++; // 那么parent的平衡因子要++}else // 如果cur插在parent的左边，说明parent的左子树增高{parent->_bf--; // 那么parent的平衡因子要--}// 判断是否更新结束，或者是否需要进行旋转if (parent->_bf == 0) // 如果parent的bf等于0，说明左右子树高度一致，就更新结束(原因是新插入的节点把parent左右子树中矮的那一边给填补了）{// 高度不变,更新结束break;}else if (parent->_bf == 1 || parent->_bf == -1) // 继续往上更新平衡因子(插入节点导致某一边变高了，说明parent所在的子树高度改变了){// 子树的高度变了，就要继续往上更新祖先cur = cur->_parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2) // 说明插入节点导致本来高的一边又变高了，子树不平衡了，那么此时需要做旋转处理{// 旋转的四种处理方式// 1.左单旋// 2.右单旋// 3.左右双旋// 4.右左双旋// 旋转完成，跳出break;}else{// 如果程序走到了这里，说明在插入节点之前AVL树就存在不平衡的子树，也就是存在平衡因子 >= 2的节点// 所以这里加一个断言进行处理assert(false);}}// 插入成功，返回truereturn true;}

🌙AVL树的旋转

在一棵原本是平衡的AVL树中插入一个新节点，可能造成不平衡，此时必须调整树的结构，使之平衡化。根据节点插入位置的不同，采用不同的旋转方法。

AVL树的旋转分为四种：

  • 左单旋（LL）
  • 右单旋（RR）
  • 左右双旋（LR）
  • 右左双旋（RL）

旋转规则：

  • 让这颗子树左右高度差不超过1
  • 旋转过程中继续保持它是搜索树
  • 更新调整孩子节点的平衡因子
  • 让这颗子树的高度根插入前保持一致

💫左单旋

左单旋的步骤如下：

  • 先让 subR 的左子树（subRL）作为 parent 的右子树。
  • 然后让 parent 作为 subR 的左子树。
  • 接下来让 subR 作为整个子树的根。
  • 最后更新平衡因子

我们就以下面的抽象图来看看左单旋如何实现：

代码示例：

// 左单旋（右边高需要左单旋）void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;Node* ppNode = parent->_parent; // 先保存parent的parent// 1.建立parent和subRL之间的关系parent->_right = subRL;if (subRL) // 如果subRL节点不为空，那么要更新它的parent{subRL->_parent = parent;}// 2.建立subR和parent之间的关系subR->_left = parent;parent->_parent = subR;// 3.建立ppNode和subR之间的关系（分情况讨论parent是整颗树的根，还是局部子树）if (parent == _root) // 当parent是根节点时{_root = subR; // subR就变成了新的根节点_root->_parent = nullptr; // 根节点的的parent为空}else // 当parent是整个树的局部子树时{if (parent == ppNode->_left) // 如果parent在ppNode的左边{ppNode->_left = subR; // 那么subR就是parent的左子树}else // 如果parent在ppNode的右边{ppNode->_right = subR; // 那么subR就是parent的右子树}subR->_parent = ppNode; // subR的parent还要指向ppNode}// 更新平衡因子parent->_bf = 0;subR->_bf = 0;}

💫右单旋

右单旋的步骤如下：

  • 先让 subL 的右子树（subLR）作为 parent 的左子树。
  • 然后让 parent 作为 subL 的右子树。
  • 接下来让 subL 作为整个子树的根。
  • 最后更新平衡因子。

我们就以下面的抽象图来看看右单旋如何实现：

代码示例：

// 右单旋（左边高就右单旋）void RotateR(Node* parent){Node* subL = parent->_left; Node* subLR = subL->_right;Node* ppNode = parent->_parent;// 1.建立parent和subLR之间的关系parent->_left = subLR;if (subLR) // 如果subLR节点不为空，那么要更新它的parent{subLR->_parent = parent;}// 2.建立subL和parent之间的关系subL->_right = parent;parent->_parent = subL;// 3.建立ppNode和subL之间的关系（分情况讨论parent是整颗树的根，还是局部子树）if (parent == _root) // 当parent是根节点时{_root = subL; // subL就变成了新的根节点_root->_parent = nullptr; // 根节点的的parent为空}else // 当parent是整个树的局部子树时{if (parent == ppNode->_left) // 如果parent在ppNode的左边{ppNode->_left = subL; // 那么subL就是parent的左子树}else // 如果parent在ppNode的右边{ppNode->_right = subL; // 那么subL就是parent的右子树}subL->_parent = ppNode; // subR的parent还要指向ppNode}// 更新平衡因子parent->_bf = 0;subL->_bf = 0;}

💫左右单旋

左右单旋的步骤如下：

  • 先以 subL 为旋转点进行左单旋。
  • 然后以 parent 为旋转点进行右单旋。
  • 最后再更新平衡因子。

我们就以下面的抽象图来看看左右单旋如何实现：

再次分类讨论：

（1）当 subLR 原始平衡因子是 -1 时，左右双旋后 parent、subL、subLR 的平衡因子分别更新为 1、0、0

（2）当 subLR 原始平衡因子是 1 时，左右双旋后 parent、subL、subLR 的平衡因子分别更新为 0、-1、0

（3）当 subLR 原始平衡因子是 0 时（说明 subLR 为新增结点），左右双旋后 parent、subL、subLR 的平衡因子分别更新为0、0、0

代码示例：


// 左右双旋（先左单旋，再右单旋）void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;// 1.先以subL为旋转点进行左单旋RotateL(parent->_left);// 2.再以parent为旋转点进行右单旋RotateR(parent);// 3.更新平衡因子if (bf == 0){parent->_bf = 0;subL->_bf = 0;subLR->_bf = 0;}else if (bf == 1){parent->_bf = 0;subL->_bf = -1;subLR->_bf = 0;}else if (bf == -1){parent->_bf = 1;subL->_bf = 0;subLR->_bf = 0;}else{// 如果走到了这里，说明subLR的平衡因子在旋转前就有问题assert(false);}}

💫右左单旋

右左单旋的步骤如下：

  • 先以 subR 为旋转点进行右单旋。
  • 然后以 parent 为旋转点进行左单旋。
  • 最后再更新平衡因子。

我们就以下面的抽象图来看看右左单旋如何实现：

再次分类讨论：

（1）当 subRL 原始平衡因子是 1 时，左右双旋后 parent、subR、subRL 的平衡因子分别更新为 -1、0、0

（2）当 subRL 原始平衡因子是 -1 时，左右双旋后 parent、subR、subRL 的平衡因子分别更新为 0、1、0

（3）当 subRL 原始平衡因子是 0 时（说明 subRL为新增结点），左右双旋后 parent、subR、subRL 的平衡因子分别更新为0、0、0

代码示例：

// 右左双旋（先右单旋，再左单旋）void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;// 1.先以subR为旋转点进行右单旋RotateR(parent->_right);// 2.再以parent为旋转点进行左单旋RotateL(parent);// 3.更新平衡因子if (bf == 0){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 0;}else if (bf == 1){subRL->_bf = 0;parent->_bf = -1;subR->_bf = 0;}else if (bf == -1){subRL->_bf = 0;parent->_bf = 0;subR->_bf = 1;}else{// 如果走到了这里，说明subRL的平衡因子在旋转前就有问题assert(false);}}

🌙AVL树的删除

这里的删除过于复杂，我这里就直接上代码了，如果对这里感兴趣的小伙伴们可以查阅资料。

// 删除函数bool Erase(const K& key){//用于遍历二叉树Node* parent = nullptr;Node* cur = _root;//用于标记实际的删除结点及其父结点Node* delParentPos = nullptr;Node* delPos = nullptr;while (cur){if (key < cur->_kv.first) //所给key值小于当前结点的key值{//往该结点的左子树走parent = cur;cur = cur->_left;}else if (key > cur->_kv.first) //所给key值大于当前结点的key值{//往该结点的右子树走parent = cur;cur = cur->_right;}else //找到了待删除结点{if (cur->_left == nullptr) //待删除结点的左子树为空{if (cur == _root) //待删除结点是根结点{_root = _root->_right; //让根结点的右子树作为新的根结点if (_root)_root->_parent = nullptr;delete cur; //删除原根结点return true; //根结点无祖先结点，无需进行平衡因子的更新操作}else{delParentPos = parent; //标记实际删除结点的父结点delPos = cur; //标记实际删除的结点}break; //删除结点有祖先结点，需更新平衡因子}else if (cur->_right == nullptr) //待删除结点的右子树为空{if (cur == _root) //待删除结点是根结点{_root = _root->_left; //让根结点的左子树作为新的根结点if (_root)_root->_parent = nullptr;delete cur; //删除原根结点return true; //根结点无祖先结点，无需进行平衡因子的更新操作}else{delParentPos = parent; //标记实际删除结点的父结点delPos = cur; //标记实际删除的结点}break; //删除结点有祖先结点，需更新平衡因子}else //待删除结点的左右子树均不为空{//替换法删除//寻找待删除结点右子树当中key值最小的结点作为实际删除结点Node* minParent = cur;Node* minRight = cur->_right;while (minRight->_left){minParent = minRight;minRight = minRight->_left;}cur->_kv.first = minRight->_kv.first; //将待删除结点的key改为minRight的keycur->_kv.second = minRight->_kv.second; //将待删除结点的value改为minRight的valuedelParentPos = minParent; //标记实际删除结点的父结点delPos = minRight; //标记实际删除的结点break; //删除结点有祖先结点，需更新平衡因子}}}if (delParentPos == nullptr) //delParentPos没有被修改过，说明没有找到待删除结点{return false;}//记录待删除结点及其父结点（用于后续实际删除）Node* del = delPos;Node* delP = delParentPos;//更新平衡因子while (delPos != _root) //最坏一路更新到根结点{if (delPos == delParentPos->_left) //delParentPos的左子树高度降低{delParentPos->_bf++; //delParentPos的平衡因子++}else if (delPos == delParentPos->_right) //delParentPos的右子树高度降低{delParentPos->_bf--; //delParentPos的平衡因子--}//判断是否更新结束或需要进行旋转if (delParentPos->_bf == 0)//需要继续往上更新平衡因子{//delParentPos树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子delPos = delParentPos;delParentPos = delParentPos->_parent;}else if (delParentPos->_bf == -1 || delParentPos->_bf == 1) //更新结束{break; //delParent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子}else if (delParentPos->_bf == -2 || delParentPos->_bf == 2) //需要进行旋转（此时delParentPos树已经不平衡了）{if (delParentPos->_bf == -2){if (delParentPos->_left->_bf == -1){Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点RotateR(delParentPos); //右单旋delParentPos = tmp; //更新根结点}else if (delParentPos->_left->_bf == 1){Node* tmp = delParentPos->_left->_right; //记录delParentPos左右旋转后新的根结点RotateLR(delParentPos); //左右双旋delParentPos = tmp; //更新根结点}else //delParentPos->_left->_bf == 0{Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点RotateR(delParentPos); //右单旋delParentPos = tmp; //更新根结点//平衡因子调整delParentPos->_bf = 1;delParentPos->_right->_bf = -1;break; //更正}}else //delParentPos->_bf == 2{if (delParentPos->_right->_bf == -1){Node* tmp = delParentPos->_right->_left; //记录delParentPos右左旋转后新的根结点RotateRL(delParentPos); //右左双旋delParentPos = tmp; //更新根结点}else if (delParentPos->_right->_bf == 1){Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点RotateL(delParentPos); //左单旋delParentPos = tmp; //更新根结点}else //delParentPos->_right->_bf == 0{Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点RotateL(delParentPos); //左单旋delParentPos = tmp; //更新根结点//平衡因子调整delParentPos->_bf = -1;delParentPos->_left->_bf = 1;break; //更正}}//delParentPos树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子delPos = delParentPos;delParentPos = delParentPos->_parent;//break; //error}else{assert(false); //在删除前树的平衡因子就有问题}}//进行实际删除if (del->_left == nullptr) //实际删除结点的左子树为空{if (del == delP->_left) //实际删除结点是其父结点的左孩子{delP->_left = del->_right;if (del->_right)del->_right->_parent = parent;}else //实际删除结点是其父结点的右孩子{delP->_right = del->_right;if (del->_right)del->_right->_parent = parent;}}else //实际删除结点的右子树为空{if (del == delP->_left) //实际删除结点是其父结点的左孩子{delP->_left = del->_left;if (del->_left)del->_left->_parent = parent;}else //实际删除结点是其父结点的右孩子{delP->_right = del->_left;if (del->_left)del->_left->_parent = parent;}}delete del; //实际删除结点return true;}

🌙AVL树的遍历

中序是递归遍历（左  根  右），由于涉及到传参，所以需要写一个子函数。

代码实现：

	// 中序遍历void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left); // 走左cout << root->_kv.first << "[" << root->_bf << "]" << endl; // 遍历根_InOrder(root->_right); // 走右}void InOrder(){_InOrder(_root);}

🌙AVL树的查找

查找步骤：

  • 若 key 值小于当前结点的值，则应该在该结点的左子树当中进行查找。
  • 若 key 值大于当前结点的值，则应该在该结点的右子树当中进行查找。
  • 若 key 值等于当前结点的值，则查找成功，返回对应结点。

代码实现：

	// 查找元素Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return NULL;}

🌙AVL树的高度

由于涉及到传参，所以需要写一个子函数。

代码实现：

	// 计算树的高度int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}int Height(){return _Height(_root);}

🌙AVL树的验证

AVL树是在二叉搜索树的基础上加入了平衡性的限制，因此要验证AVL树，可以分为下面两步：

（1）验证其为二叉搜索树

  • 如果中序遍历可得到一个有序的序列，就说明为二叉搜索树
​void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left);cout << root->_kv.first << ":" << root->_kv.second << endl;_InOrder(root->_right);}​

（2）验证其为平衡树

  • 每个节点子树高度差的绝对值不超过 1（注意节点中如果没有平衡因子）
  • 节点的平衡因子是否计算正确

🌙AVL树的高度

//求高度
int Height(Node* root){if (root == nullptr)return 0;int lh = Height(root->_left);int rh = Height(root->_right);return lh > rh ? lh + 1 : rh + 1;}
//判断平衡
bool IsBalance(Node* root){if (root == nullptr){return true;}int leftHeight = Height(root->_left);int rightHeight = Height(root->_right);if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}return abs(rightHeight - leftHeight) < 2&& IsBalance(root->_left)&& IsBalance(root->_right);}

🌙AVL树优缺点

优点：

  • 平衡二叉树的优点不言而喻，相对于二叉排序树（BST）而言，平衡二叉树避免了二叉排序树可能出现的最极端情况（斜树）问题，其平均查找的时间复杂度为 O ( l o g N ) O(logN)O(logN)

缺点：

  • 平衡二叉树为了保持平衡，动态进行插入和删除操作的代价也会增加。因此出现了后来的红黑树

AVL树是一棵绝对平衡的二叉搜索树，其要求每个节点的左右子树高度差的绝对值都不超过 1，这样可以保证查询时高效的时间复杂度，即O ( l o g N ) O(logN)O(logN)。但是如果要对AVL树做一些结构修改的操作，性能非常低下，比如：插入时要维护其绝对平衡，旋转的次数比较多，更差的是在删除时，有可能一直要让旋转持续到根的位置。因此：如果需要一种查询高效且有序的数据结构，而且数据的个数为静态的（即不会改变），可以考虑AVL树，但一个结构经常修改，就不太适合。

🌙整体代码

#include <iostream>
#include <assert.h>
#include<vector>
#include <time.h>
using namespace std;// 创建AVL树的结点
template<class K,class V>
struct AVLTreeNode
{AVLTreeNode<K, V>* _left;  // 左子树AVLTreeNode<K, V>* _right; // 右子树AVLTreeNode<K, V>* _parent;// 父亲结点pair<K, V> _kv; // 存储的键值对int _bf;       // 平衡因子（右子树高度 - 左子树高度）// 构造函数AVLTreeNode(const pair<K, V>& kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _bf(0){}
};template<class K,class V>
class AVLTree
{typedef AVLTreeNode<K, V> Node;
public:// 插入元素bool Insert(const pair<K, V>& kv){if (_root == nullptr) // 如果没有结点{_root = new Node(kv);return true;}Node* parent = nullptr;Node* cur = _root;while (cur) // 采用循环查找要插入的结点{if (cur->_kv.first < kv.first) // 插入的元素大于cur就走右子树{parent = cur;cur = cur->_right;}else if (cur->_kv.first < kv.first) // 插入的元素小于cur就走左子树{parent = cur;cur = cur->_left;}elsereturn false;}cur = new Node(kv);// 创建一个结点// 链接if (parent->_kv.first < kv.first)parent->_right = cur;elseparent->_left = cur;cur->_parent = parent;// 循环判断插入结点的平衡因子和AVL树是否正确while (parent){// 判断插入的节点在父亲的右边还是左边if (cur == parent->_left) // 在左边就父亲平衡因子减一parent->_bf--;else                     // 在右边就父亲平衡因子加一parent->_bf++;if (parent->_bf == 0) // 如果父亲的平衡因子为 0 该树就是健康的不用改变break;else if (parent->_bf == 1 || parent->_bf == -1) // 这时需要向上调整每个节点的平衡因子{cur = cur->_parent;parent = parent->_parent;}else if (parent->_bf == 2 || parent->_bf == -2) // 需要旋转处理{// 旋转处理if (parent->_bf == 2 && cur->_bf == 1) // 左单旋{RotateL(parent);}else if (parent->_bf == -2 && cur->_bf == -1) // 右单旋{RotateR(parent);}else if (parent->_bf == -2 && cur->_bf == 1) // 左右双旋{RotateLR(parent);}else  // 右左双旋 {RotateRL(parent);}break;}else{// 插入之前AVL树就有问题assert(false);}}}// 左单旋void RotateL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;parent->_right = subRL;if (subRL)subRL->_parent = parent;subR->_left = parent;Node* ppnode = parent->_parent;parent->_parent = subR;if (parent == _root){_root = subR;subR->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subR;}else{ppnode->_right = subR;}subR->_parent = ppnode;}parent->_bf = 0;subR->_bf = 0;}// 右单旋void RotateR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;parent->_left = subLR;if (subLR)subLR->_parent = parent;subL->_right = parent;Node* ppnode = parent->_parent;parent->_parent = subL;if (parent == _root){_root = subL;subL->_parent = nullptr;}else{if (ppnode->_left == parent){ppnode->_left = subL;}else{ppnode->_right = subL;}subL->_parent = ppnode;}subL->_bf = 0;parent->_bf = 0;}// 左右双旋void RotateLR(Node* parent){Node* subL = parent->_left;Node* subLR = subL->_right;int bf = subLR->_bf;RotateL(parent->_left);RotateR(parent);if (bf == -1){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 1;}else if (bf == 1){subLR->_bf = 0;subL->_bf = -1;parent->_bf = 0;}else if (bf == 0){subLR->_bf = 0;subL->_bf = 0;parent->_bf = 0;}else{assert(false);}}// 右左双旋void RotateRL(Node* parent){Node* subR = parent->_right;Node* subRL = subR->_left;int bf = subRL->_bf;RotateR(subR);RotateL(parent);subRL->_bf = 0;if (bf == 1){subR->_bf = 0;parent->_bf = -1;}else if (bf == -1){parent->_bf = 0;subR->_bf = 1;}else{parent->_bf = 0;subR->_bf = 0;}}// 中序遍历void _InOrder(Node* root){if (root == nullptr)return;_InOrder(root->_left); // 走左cout << root->_kv.first << "[" << root->_bf << "]" << endl; // 遍历根_InOrder(root->_right); // 走右}void InOrder(){_InOrder(_root);}// 计算树的高度int _Height(Node* root){if (root == nullptr)return 0;int leftHeight = _Height(root->_left);int rightHeight = _Height(root->_right);return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;}int Height(){return _Height(_root);}// 判断是否平衡bool _IsBalance(Node* root, int& height){if (root == nullptr){height = 0;return true;}int leftHeight = 0, rightHeight = 0;if (!_IsBalance(root->_left, leftHeight)|| !_IsBalance(root->_right, rightHeight)){return false;}if (abs(rightHeight - leftHeight) >= 2){cout << root->_kv.first << "不平衡" << endl;return false;}if (rightHeight - leftHeight != root->_bf){cout << root->_kv.first << "平衡因子异常" << endl;return false;}height = leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;return true;}bool IsBalance(){int height = 0;return _IsBalance(_root, height);}// 计算树的结点个数size_t _Size(Node* root){if (root == NULL)return 0;return _Size(root->_left)+ _Size(root->_right) + 1;}size_t Size(){return _Size(_root);}// 查找元素Node* Find(const K& key){Node* cur = _root;while (cur){if (cur->_kv.first < key){cur = cur->_right;}else if (cur->_kv.first > key){cur = cur->_left;}else{return cur;}}return NULL;}// 删除函数bool Erase(const K& key){//用于遍历二叉树Node* parent = nullptr;Node* cur = _root;//用于标记实际的删除结点及其父结点Node* delParentPos = nullptr;Node* delPos = nullptr;while (cur){if (key < cur->_kv.first) //所给key值小于当前结点的key值{//往该结点的左子树走parent = cur;cur = cur->_left;}else if (key > cur->_kv.first) //所给key值大于当前结点的key值{//往该结点的右子树走parent = cur;cur = cur->_right;}else //找到了待删除结点{if (cur->_left == nullptr) //待删除结点的左子树为空{if (cur == _root) //待删除结点是根结点{_root = _root->_right; //让根结点的右子树作为新的根结点if (_root)_root->_parent = nullptr;delete cur; //删除原根结点return true; //根结点无祖先结点，无需进行平衡因子的更新操作}else{delParentPos = parent; //标记实际删除结点的父结点delPos = cur; //标记实际删除的结点}break; //删除结点有祖先结点，需更新平衡因子}else if (cur->_right == nullptr) //待删除结点的右子树为空{if (cur == _root) //待删除结点是根结点{_root = _root->_left; //让根结点的左子树作为新的根结点if (_root)_root->_parent = nullptr;delete cur; //删除原根结点return true; //根结点无祖先结点，无需进行平衡因子的更新操作}else{delParentPos = parent; //标记实际删除结点的父结点delPos = cur; //标记实际删除的结点}break; //删除结点有祖先结点，需更新平衡因子}else //待删除结点的左右子树均不为空{//替换法删除//寻找待删除结点右子树当中key值最小的结点作为实际删除结点Node* minParent = cur;Node* minRight = cur->_right;while (minRight->_left){minParent = minRight;minRight = minRight->_left;}cur->_kv.first = minRight->_kv.first; //将待删除结点的key改为minRight的keycur->_kv.second = minRight->_kv.second; //将待删除结点的value改为minRight的valuedelParentPos = minParent; //标记实际删除结点的父结点delPos = minRight; //标记实际删除的结点break; //删除结点有祖先结点，需更新平衡因子}}}if (delParentPos == nullptr) //delParentPos没有被修改过，说明没有找到待删除结点{return false;}//记录待删除结点及其父结点（用于后续实际删除）Node* del = delPos;Node* delP = delParentPos;//更新平衡因子while (delPos != _root) //最坏一路更新到根结点{if (delPos == delParentPos->_left) //delParentPos的左子树高度降低{delParentPos->_bf++; //delParentPos的平衡因子++}else if (delPos == delParentPos->_right) //delParentPos的右子树高度降低{delParentPos->_bf--; //delParentPos的平衡因子--}//判断是否更新结束或需要进行旋转if (delParentPos->_bf == 0)//需要继续往上更新平衡因子{//delParentPos树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子delPos = delParentPos;delParentPos = delParentPos->_parent;}else if (delParentPos->_bf == -1 || delParentPos->_bf == 1) //更新结束{break; //delParent树的高度没有发生变化，不会影响其父结点及以上结点的平衡因子}else if (delParentPos->_bf == -2 || delParentPos->_bf == 2) //需要进行旋转（此时delParentPos树已经不平衡了）{if (delParentPos->_bf == -2){if (delParentPos->_left->_bf == -1){Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点RotateR(delParentPos); //右单旋delParentPos = tmp; //更新根结点}else if (delParentPos->_left->_bf == 1){Node* tmp = delParentPos->_left->_right; //记录delParentPos左右旋转后新的根结点RotateLR(delParentPos); //左右双旋delParentPos = tmp; //更新根结点}else //delParentPos->_left->_bf == 0{Node* tmp = delParentPos->_left; //记录delParentPos右旋转后新的根结点RotateR(delParentPos); //右单旋delParentPos = tmp; //更新根结点//平衡因子调整delParentPos->_bf = 1;delParentPos->_right->_bf = -1;break; //更正}}else //delParentPos->_bf == 2{if (delParentPos->_right->_bf == -1){Node* tmp = delParentPos->_right->_left; //记录delParentPos右左旋转后新的根结点RotateRL(delParentPos); //右左双旋delParentPos = tmp; //更新根结点}else if (delParentPos->_right->_bf == 1){Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点RotateL(delParentPos); //左单旋delParentPos = tmp; //更新根结点}else //delParentPos->_right->_bf == 0{Node* tmp = delParentPos->_right; //记录delParentPos左旋转后新的根结点RotateL(delParentPos); //左单旋delParentPos = tmp; //更新根结点//平衡因子调整delParentPos->_bf = -1;delParentPos->_left->_bf = 1;break; //更正}}//delParentPos树的高度变化，会影响其父结点的平衡因子，需要继续往上更新平衡因子delPos = delParentPos;delParentPos = delParentPos->_parent;//break; //error}else{assert(false); //在删除前树的平衡因子就有问题}}//进行实际删除if (del->_left == nullptr) //实际删除结点的左子树为空{if (del == delP->_left) //实际删除结点是其父结点的左孩子{delP->_left = del->_right;if (del->_right)del->_right->_parent = parent;}else //实际删除结点是其父结点的右孩子{delP->_right = del->_right;if (del->_right)del->_right->_parent = parent;}}else //实际删除结点的右子树为空{if (del == delP->_left) //实际删除结点是其父结点的左孩子{delP->_left = del->_left;if (del->_left)del->_left->_parent = parent;}else //实际删除结点是其父结点的右孩子{delP->_right = del->_left;if (del->_left)del->_left->_parent = parent;}}delete del; //实际删除结点return true;}private:Node* _root = nullptr;
};void TestAVLTree1()
{//int a[] = { 16, 3, 7, 11, 9, 26, 18, 14, 15 };int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14 };AVLTree<int, int> t;for (auto e : a){if (e == 14){int x = 0;}t.Insert(make_pair(e, e));cout << e << "->" << t.IsBalance() << endl;}t.InOrder();cout << t.IsBalance() << endl;
}void TestAVLTree2()
{const int N = 1000000;vector<int> v;v.reserve(N);srand(time(0));for (size_t i = 0; i < N; i++){v.push_back(rand() + i);//cout << v.back() << endl;}size_t begin2 = clock();AVLTree<int, int> t;for (auto e : v){t.Insert(make_pair(e, e));//cout << "Insert:" << e << "->" << t.IsBalance() << endl;}size_t end2 = clock();cout << "Insert:" << end2 - begin2 << endl;cout << t.IsBalance() << endl;cout << "Height:" << t.Height() << endl;cout << "Size:" << t.Size() << endl;size_t begin1 = clock();// 确定在的值for (auto e : v){t.Find(e);}// 随机值for (size_t i = 0; i < N; i++){t.Find((rand() + i));}size_t end1 = clock();cout << "Find:" << end1 - begin1 << endl;
}

🌟结束语

       今天内容就到这里啦，时间过得很快，大家沉下心来好好学习，会有一定的收获的，大家多多坚持，嘻嘻，成功路上注定孤独，因为坚持的人不多。那请大家举起自己的小手给博主一键三连，有你们的支持是我最大的动力💞💞💞，回见。

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

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

相关文章

Qt Creator 安装 Beautifier

Qt Creator 安装 Beautifier

启动 Beautifier 插件。 在 qtCreator 界面上&#xff0c;Help - About Plugins - C - Beautifier 勾选此项。重启 qtcreator 下载 Artisitic Style 下载地址 解压后进入目录&#xff0c;进入 build/gcc/ 执行&#xff1a;make && make install 配置 Artisitic Style…
阅读更多...
【Flask开发实战】防火墙配置文件解析（三）之python加工处理

【Flask开发实战】防火墙配置文件解析（三）之python加工处理

一、前言 上一篇文章中&#xff0c;介绍了通过shell脚本读取配置文件获取到IP地址组、服务端口组、规则清单这三个模块类别基础数据。基础数据中还需要进一步进行展开处理&#xff0c;生成三类扩展表。如IP地址组中&#xff0c;同一个地址组下存在多个IP地址&#xff0c;每组I…
阅读更多...
Python读取Excel工作表数据写入CSV、XML、文本

Python读取Excel工作表数据写入CSV、XML、文本

Excel工作簿是常用的表格格式&#xff0c;许多数据呈现、数据分析和数据汇报都是以Excel工作表的形式进行。然而&#xff0c;在实际的数据管理、分析或自动化流程构建过程中&#xff0c;我们常常需要将这些Excel中的数据迁移至更其他数据系统&#xff0c;或者以文本形式存储以便…
阅读更多...
B树B+树，字典树详解，哈夫曼树博弈树

B树B+树，字典树详解，哈夫曼树博弈树

目录 B树&#xff1a;B-Tree B树 字典树&#xff1a;Trie Tree 哈夫曼树 博弈树 B树&#xff1a;B-Tree 多路平衡搜索树 1.M阶B树&#xff0c;就是M叉&#xff08;M个指针&#xff09;。 2.每个节点内记录个数<M-1。 3.根节点记录个数>1。 4.其余节点内记录个数&…
阅读更多...
洗涤杂质气体的仪器-PFA洗涤瓶

洗涤杂质气体的仪器-PFA洗涤瓶

PFA洗气瓶是一种洗去气体中杂质的仪器&#xff0c;是将不纯气体通过选定的适宜液体介质鼓泡吸收&#xff08;溶解或由于发生化学反应&#xff09;&#xff0c;从而洗去杂质气体&#xff0c;以达净化气体的目的。在有可燃性气源的实验装置中&#xff0c;洗气瓶也可起到安全瓶的作…
阅读更多...
qt使用Windows经典风格，以使QTreeView或QTreeWidge有节点线或加号

qt使用Windows经典风格，以使QTreeView或QTreeWidge有节点线或加号

没有使用Windows经典风格的QTreeView或QTreeWidget显示如下&#xff1a; 使用Windows经典风格的QTreeView或QTreeWidget显示如下&#xff1a; 树展开时&#xff1a; 树未展开时&#xff1a; 可以看到&#xff1a; 未使用Windows经典风格时&#xff0c;QTreeView或QTreeWidget…
阅读更多...
【Flask开发实战】防火墙配置文件解析（二）之shell读取内容

【Flask开发实战】防火墙配置文件解析（二）之shell读取内容

一、前言 上一篇文章中&#xff0c;介绍了防火墙配置文件包含的基本元素和格式样式&#xff0c;并模拟了几组有代表性的规则内容&#xff0c;作为基础测试数据。在拿到基础测试数据后&#xff0c;关于我们最终想解析成的数据是什么样式的&#xff0c;其实不难看出&#xff0c;…
阅读更多...
聚合音乐网-播放器网站源码

聚合音乐网-播放器网站源码

源码简介 MKOnlineMusicPlayer 是一款全屏的音乐播放器 UI 框架&#xff08;为避免侵权&#xff0c;已移除所有后端功能&#xff09;。 前端界面参照 QQ 音乐网页版进行布局&#xff0c;同时采用了流行的响应式设计&#xff0c;无论是在PC端还是在手机端&#xff0c;均能给您…
阅读更多...
【Linux】日常使用命令（三）

【Linux】日常使用命令（三）

文章目录 **cal 命令****date 命令****bc 命令****Linux下玩小游戏**&#xff1a; cal 命令 功能描述: cal 命令用于显示日历。 常用选项: -3&#xff1a;显示前一个月、当前月和下一个月的日历。-y&#xff1a;显示整年的日历。 常用示例: # 示例 1: 显示当前月的日历 cal# …
阅读更多...
Ubuntu Desktop 设置 gedit

Ubuntu Desktop 设置 gedit

Ubuntu Desktop 设置 gedit 1. View2. Editor3. Font & Colors4. keyboard shortcut5. Find and ReplaceReferences gedit (/ˈdʒɛdɪt/ or /ˈɡɛdɪt/) is the default text editor of the GNOME desktop environment and part of the GNOME Core Applications. Desig…
阅读更多...
相比于 HTTP 协议，WebSocket协议的必要性体现在哪里？

相比于 HTTP 协议，WebSocket协议的必要性体现在哪里？

HTTP 协议的一个缺点 从 HTTP 协议的角度来看&#xff0c;就是点一下网页上的某个按钮&#xff0c;前端发一次 HTTP请 求&#xff0c;网站返回一次 HTTP 响应。这种由客户端主动请求&#xff0c;服务器响应的方式也满足大部分网页的功能场景。但是有没有发现&#xff0c;在HTTP…
阅读更多...
InfluxDB、Grafana、node_exporter、Prometheus搭建压测平台

InfluxDB、Grafana、node_exporter、Prometheus搭建压测平台

InfluxDB、Grafana、node_exporter、Prometheus搭建压测平台 我们的压测平台的架构图如下&#xff1a; 配置docker环境 1&#xff09;yum 包更新到最新 sudo yum update如果有提示&#xff0c;直接输入y&#xff0c;回车。 2&#xff09;安装需要的软件包&#xff0c; yum-…
阅读更多...
八大排序算法

八大排序算法

排序算法 排序的概述排序的分类分为5大类&#xff1a;优点及缺点如何选择排序算法 八种排序之间的关系:一、插入排序直接插入排序动图详解代码实现 希尔排序动图详解代码实现 二、交换排序冒泡排序:动图详解代码实现 快速排序:动图详解代码实现 三、选择排序直接选择排序动图详…
阅读更多...
杉德支付配合调查 - 数字藏品服务

杉德支付配合调查 - 数字藏品服务

最近&#xff0c;数字收藏品平台淘派发布了一则公告&#xff0c;宣布支付通道杉德已暂停接口服务&#xff0c;以配合调查。 近期发现多个异常账户&#xff0c;涉嫌盗取他人信息和银行卡&#xff0c;利用平台从事非法交易。淘派已第一时间报警&#xff0c;协助警方追回资金(回执…
阅读更多...
java数据结构与算法刷题-----LeetCode1005. K 次取反后最大化的数组和（这就不是简单题）

java数据结构与算法刷题-----LeetCode1005. K 次取反后最大化的数组和（这就不是简单题）

java数据结构与算法刷题目录&#xff08;剑指Offer、LeetCode、ACM&#xff09;-----主目录-----持续更新(进不去说明我没写完)&#xff1a;https://blog.csdn.net/grd_java/article/details/123063846 卷来卷去&#xff0c;把简单题都卷成中等题了 文章目录 1. 排序后从小到大…
阅读更多...
算法刷题Day14 | 二叉树理论、递归遍历、迭代遍历、统一迭代

算法刷题Day14 | 二叉树理论、递归遍历、迭代遍历、统一迭代

目录 0 引言1 递归遍历1.1 前序遍历1.2 后序遍历1.3 中序遍历 2 迭代遍历2.1 前序和后序2.2 中序 &#x1f64b;‍♂️ 作者&#xff1a;海码007&#x1f4dc; 专栏&#xff1a;算法专栏&#x1f4a5; 标题&#xff1a;算法刷题Day14 | 二叉树理论、递归遍历、迭代遍历、统一迭…
阅读更多...
【教程】APP加固的那些小事情

【教程】APP加固的那些小事情

摘要 APP加固是保护APP代码逻辑的重要手段&#xff0c;通过隐藏、混淆、加密等操作提高软件的逆向成本&#xff0c;降低被破解的几率&#xff0c;保障开发者和用户利益。本文将介绍APP加固常见失败原因及解决方法&#xff0c;以及处理安装出现问题的情况和资源文件加固策略选择…
阅读更多...
html--蝴蝶

html--蝴蝶

<!DOCTYPE html> <html lang"en" > <head> <meta charset"UTF-8"> <title>蝴蝶飞舞</title> <link rel"stylesheet" href"https://cdnjs.cloudflare.com/ajax/libs/meyer-reset/2.0/reset.min.cs…
阅读更多...
关于Transfomer的思考

关于Transfomer的思考

为何诞生 在说transformer是什么&#xff0c;有什么优势之类的之前&#xff0c;先谈一谈它因何而诞生。transformer诞生最重要的原因是早先的语言模型&#xff0c;比如RNN&#xff0c;由于其本身的训练机制导致其并行度不高&#xff0c;特别是遇到一些长句子的情况下。其次&…
阅读更多...
鸿蒙Harmony应用开发—ArkTS声明式开发（容器组件：ListItem）

鸿蒙Harmony应用开发—ArkTS声明式开发（容器组件：ListItem）

用来展示列表具体item&#xff0c;必须配合List来使用。 说明&#xff1a; 该组件从API Version 7开始支持。后续版本如有新增内容&#xff0c;则采用上角标单独标记该内容的起始版本。该组件的父组件只能是List或者ListItemGroup。 子组件 可以包含单个子组件。 接口 从API…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023