目录
介绍
引入
概念
特点
模拟实现
思路
插入
旋转
左旋
无子树
有子树
右旋
无子树
有子树
左右旋
引入(也就是有子树版本的抽象图解)
解决方法(也就是左右旋)
总结
无子树(也就是curright的位置就是newnode)
有子树
模型高度解释
旋转
更新三个节点的bf
右左旋
无子树
有子树
旋转
更新三个结点的bf
注意点
代码
介绍
引入
map和set的底层都是按照二叉搜索树来实现的
- 但是二叉搜索树有其自身的缺陷,假如往树中插入的元素有序或者接近有序,二叉搜索树就会退化成单支树,时间复杂度会退化成O(N)
- 因此map、set等关联式容器的底层结构是对二叉树进行了平衡处理,即采用平衡树来实现
概念
- AVL树是一种自平衡二叉搜索树,其名称源自其发明者Adelson-Velsky和Landis
- AVL树通过确保各个节点之间的高度差不超过1,来保证在最坏情况下,树的高度仍为O(log n) (其中n是树中节点的数量),这样可以保持最好的效率
特点
自平衡:在插入或删除节点时,AVL树会自动执行旋转操作来保持平衡。这些旋转操作包括左旋、右旋、左右旋和右左旋等,通过这些旋转可以调整节点的平衡因子,使其满足平衡条件(不超过1)
二叉搜索树性质:AVL树仍然是二叉搜索树,即左子树的所有节点的值都小于根节点的值,右子树的所有节点的值都大于根节点的值
模拟实现
思路
插入
- avl树中保持平衡的关键就在于平衡因子(bf)
- 这里bf=右子树高度-左子树高度
- 主要就是每次插入时,需要更新平衡因子 (但只需要沿着newnode的位置往上就行,因为它改变的只是newnode所在那一分支)
- 只要当前结点bf=0,就可以不再更新了(它此时变为0,说明原来是1/-1)
- 那么让1/-1变为0,这一分支的高度是不变的,那么以这个为子树的树,高度也不会变,平衡因子也就不变
- 然后,如果结点bf=2/-2,就要开始旋转了
- 而旋转分为4种,需要判断cur和cur父亲的bf,来区分使用哪种旋转方式
- 而旋转后的子树,其根结点bf是0,那么他也是从在插入新结点前的1/-1变成了0,所以也就不需要往上更新了
- 这样,插入步骤就结束了
旋转
左旋
无子树
左旋实际上就是 -- 让p成为cur的左子树,cur的右边不受影响
有子树
- 虽然都有子树,但我们无法知道到底是多少个,到底是什么形态
- (这些其实我们都不关心,我们只要知道一个相对大小就行,毕竟重点还是在p和cur上)
- 有子树和无子树都是差不多的,只不过是多了子树,但是p和cur的bf仍然是2和1,只有这样才会触发左旋
- 然后设cur左子树高度为h,那么可以推出curright高度就是h+1,p左树是h
- 旋转后 -- cur的原左子树成为了p的右子树(因为本身curleft就处于p的右树范围),p左树不变,cur右树也不变
- 只要记住 -- 左旋是p成为cur的左树,那么原左树就成为了p的右树
- 旋转后的bf:(都为0)
右旋
和左旋非常像,只不过是换了个方向
无子树
旋转后,p成为cur的右子树
有子树
和左旋一个思路,最终得到了这么一副抽象图:
然后就是旋转了 -- cur原右子树成为p的左子树(本身就是p左树范围内),p右子树不变
计算bf后,两个结点的bf变成了0,其他的都不变
两种旋转真的非常像,只要记住左旋是p成为cur的左子树,右旋是p成为cur的右子树,就行了
左右旋
引入(也就是有子树版本的抽象图解)
上面有这样一种情况,它是需要被右旋的:
但是如果这个新结点是在curright下呢???
这种情况不能使用单独的右旋(因为单右旋没有用):
会发现右旋后,这支子树的根结点的bf还是2(只是把原子树的左右颠倒了)
解决方法(也就是左右旋)
然后,我们经过对比可以发现,实际上他和右旋之间就差一个拐拐 :
所以可以考虑将那个拐角处掰正,也就是对应的将cur那支子树进行左旋:
这样,就可以和原来的p拼接起来,达到右旋的条件
最终经过右旋后,就可以完成我们的需求(这里只是抽象演示,并没有细画cur的情况,有子树中会有详细版)
总结
相当于对cur左旋是进行右旋的预热,最终其实还是经过对p右旋完成的
无子树(也就是curright的位置就是newnode)
先对cur进行左旋,然后对p右旋:
最终newnode(也就是curright成为了这一支子树的根结点)
有子树
首先,在无子树情况中,我们会发现,最终cur的右结点成为了根,那么我们就需要额外画出这个结点
其次,新结点放在curright的左/右子树都可以,只不过最后处理这三个重要结点的bf时,需要单另处理
先抽象好模型(设curright右子树高度为h,从而可以推出其他高度)
模型高度解释
你可能会好奇,为什么curright的左右子树高度被写成是相等的? (至少我好奇了,然后我画了画,发现是有人家的理由的)
- 这里还是设右子树高度为h
- 如果原先左子树高度是h+1(高度差不能超过1嗷)
- 那新加一个结点就会变成h+2,会让curright的bf变成-2,那么这里不会触发p的左右旋,而是curright的旋转(左旋或者左右旋,具体看新结点的位置)
- 如果原先左子树高度是h-1(高度差不能超过1嗷)
- 那新加一个结点就会变成h,会让curright的bf变成0,那bf的更新到curright就停止了,不会让p更新到2/-2,所以依然不可以
那么就可以得到,curright的两个子树(如果有),那一定高度相等,才能触发p的左右旋
旋转
继续接下来的步骤,抽象好模型后,对cur进行左旋
不要忘记前面介绍的左旋了嗷(这里的cur成为curright的左子树,原左树成为cur的右子树)
然后和p连接在一起(也就是修改p的指向和两个结点的_parent指向)
接下来就是旋转的最后一步辣,对p进行右旋
这里是将p作为curright的右子树,原右子树成为p的左树(都是之前的步骤)
之后就是最重要的一步,对三个结点的bf重新赋值(虽然进行了旋转,但更新到的bf实际并不准确,因为右旋和左右旋用到的模型本身就不同)
更新三个节点的bf
这里的更新也得分情况
像这里用到的图解,是新结点插入在curright的左树部分
(下面是全部的旋转变换过程)
- 那么由于要对cur左旋的缘故,curright中带有新结点的这一支给了cur的右树,那么cur右边和左边平衡了,cur的bf=0
- 但p不一样,p的左树是被分配的curright的右树,其高度只有h(注意看图嗷看图),所以p的bf=1
如果新结点插入在curright的右树部分
- 道理和上面的一样
- 因为curright的右树给了p的左边:
- 所以p的bf=0(平衡了)
- 而cur的右边是原curright的左边,高度是0,所以cur的bf=-1
只要过程熟悉,知道是怎么变的,bf的更新也素手到擒来噜
右左旋
和左右旋非常像,只不过是换了个方向
无子树
同样是有拐,也是一样要把那个拐掰正,也就是对cur进行右旋(让cur成为curleft的右子树)
最后就可以美美对p进行左旋噜
然后curleft成为了这一支的根结点
有子树
由于在左右旋中,我们已经分析了模型高度,所以我们直接画出右左旋的抽象模型(本质一样的)
旋转
接下来就是相似的操作,对curleft进行右旋
然后和p连接
就变成了标准的左旋状态,对p进行左旋:
最后就是:curleft的右结点通过右旋给了cur的左边,左结点经过左旋给了p的右边
更新三个结点的bf
这里用到的图解,是新结点插入在curleft的左树部分
像一直在重复说的那样(臣妾已经说倦了)
- 因为右旋,cueleft的右子树给了cur的左树,所以cur的左边是h,而右边是自己的h+1,所以cur的bf=1
- 因为左旋,curleft的左子树给了p的右子树,而右子树正是新结点插入位置,所以p的左边是h+1,右边是原先自己的h+1,相等了,所以p的bf=0
当新结点插入在curleft的右树部分
经过旋转后:
会发现:
- 新结点所在的右子树,在右旋中给了cur的左子树,所以cur的左右相等了,cur的bf=0
- 而给p的curleft右树高度仍是h,而p的左子树是自己的h+1,所以p的bf=-1
注意点
一定要写对插入的逻辑,还有 各种结点指向 / bf数值 的更新,超级重要!!!
- 亲身经历,本来以为对了,测试也是对的,过了几天加了点测试代码(因为实在是不好看这个代码到底写的对不对,又多又杂),结果就挂了
- 找了半天的错,发现旋转代码没问题,是我插入里面的"往上更新bf"逻辑错了
- 我是先一直更新到根结点,然后才找bf=2/-2的结点
- 就导致,旋转完后子树的bf是对的,它父结点的bf错了,本来就不应该更新它的!(我哭死)
然后就是旋转里面,"原子树根结点的父结点"的指向要注意不要漏掉,要更新啊!!!
其他的好像就没啥了,只要多多写备注,就应该没啥问题
代码
#include <iostream>
#include <vector>
#include <string>
#include <queue>
#include <cassert>
#include <cstdlib>namespace my_AvlTree
{template <class T>struct AvlTreeNode{AvlTreeNode(const T &data = T()): _left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _bf(0){}AvlTreeNode<T> *_left;AvlTreeNode<T> *_right;AvlTreeNode<T> *_parent;T _data;int _bf; // 节点的平衡因子};// AVL: 二叉搜索树 + 平衡因子的限制template <class T>class AvlTree{typedef AvlTreeNode<T> Node;public:AvlTree(): _root(nullptr){}// 在AVL树中插入值为data的节点bool Insert(const T &data);// AVL树的验证bool IsAvlTree(){return _IsAvlTree(_root);}void levelOrder();size_t Height(){return _Height(_root);}private:// 根据AVL树的概念验证pRoot是否为有效的AVL树bool _IsAvlTree(Node *root);size_t _Height(Node *root);// 右单旋void RotateR(Node *parent);// 左单旋void RotateL(Node *parent);// 右左双旋void RotateRL(Node *parent);// 左右双旋void RotateLR(Node *parent);private:Node *_root;};template <class T>void AvlTree<T>::levelOrder(){Node *root = _root;std::vector<std::vector<T>> arr;std::queue<Node *> q;if (root != nullptr){q.push(root);}while (!q.empty()){std::vector<T> tmp; // 存储一层的结点int size = q.size(); // 此时队列内的元素就是上一层的结点个数for (int i = 0; i < size; ++i){tmp.push_back(q.front()->_data);if (q.front()->_left){ // 有子树就放进队列中q.push(q.front()->_left);}if (q.front()->_right){q.push(q.front()->_right);}q.pop(); // 出掉这个父结点}arr.push_back(tmp);}for (auto &i : arr){for (auto &j : i){std::cout << j << " ";}std::cout << std::endl;}}template <class T>bool AvlTree<T>::Insert(const T &data){if (_root == nullptr){_root = new Node(data);}else{Node *cur = _root, *parent = cur, *newnode = nullptr;// 找到插入位置while (cur){if (data > cur->_data){parent = cur;cur = cur->_right;}else if (data < cur->_data){parent = cur;cur = cur->_left;}else{return false;}}// 插入+改父亲bfnewnode = new Node(data);if (data < parent->_data){parent->_left = newnode;--parent->_bf;newnode->_parent = parent;}else{parent->_right = newnode;++parent->_bf;newnode->_parent = parent;}// std::cout << "parent:" << parent->_data << " "// << "newnode:" << newnode->_data << std::endl;// 维护bfcur = parent; //注意,这里不能直接定义cur的父结点,因为不能保证cur不为空(如果此时只有俩结点,就为空了!!!)while (cur != _root){Node *pnode = cur->_parent;// 更新bfif (pnode->_left == cur){--pnode->_bf;}else{++pnode->_bf;}// 判断是否继续往上更新if (cur->_bf == 0){break;}else{if (pnode->_bf == 2 || pnode->_bf == -2){// pnode就是不合法的结点,然后判断它该怎么调整if (pnode->_bf == -2 && cur->_bf == -1){// 右单旋RotateR(pnode);}if (pnode->_bf == 2 && cur->_bf == 1){// 左单旋RotateL(pnode);}if (pnode->_bf == -2 && cur->_bf == 1){// 左右双旋RotateLR(pnode);}if (pnode->_bf == 2 && cur->_bf == -1){// 右左双旋RotateRL(pnode);}break;}else{cur = pnode;pnode = pnode->_parent;}}}}return true;}template <class T>bool AvlTree<T>::_IsAvlTree(Node *root){if (root == nullptr){return true;}int left_height = _Height(root->_left);int right_height = _Height(root->_right);if (right_height - left_height != root->_bf) //不要太相信自己写的bf计算方法{std::cout << right_height << std::endl;std::cout << left_height << std::endl;std::cout << root->_bf << std::endl;std::cout << "平衡因子异常" << std::endl;return false;}return abs(right_height - left_height) < 2 && _IsAvlTree(root->_left) && _IsAvlTree(root->_right);}template <class T>size_t AvlTree<T>::_Height(Node *root){if (root == nullptr){return 0;}int leftsize = _Height(root->_left) + 1;int rightsize = _Height(root->_right) + 1;return leftsize > rightsize ? leftsize : rightsize;}template <class T>void AvlTree<T>::RotateL(Node *parent){Node *cur = parent->_right, *curleft = cur->_left, *ppnode = parent->_parent;// 连接cur上需要修改的子树(比如左旋就是让parent当cur的左子树,那么cur左树就得和parent右边相连)if (curleft) // 防止左树为空{curleft->_parent = parent;}parent->_right = curleft;// 连接cur和parentcur->_left = parent;// 修改parent父结点的指向if (ppnode == nullptr) // 如果此时parent是根结点,那么它没有父结点,且需要更新根结点{_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}}// 改父结点指向(千万别忘辣!!!)cur->_parent = ppnode;parent->_parent = cur;// 维护bfcur->_bf = parent->_bf = 0;}template <class T>void AvlTree<T>::RotateR(Node *parent){Node *cur = parent->_left, *curright = cur->_right, *ppnode = parent->_parent;// 连接cur上需要修改的子树(右旋就是让parent当cur的右子树,那么cur右树就得和parent左边相连)if (curright) // 防止右树为空{curright->_parent = parent;}parent->_left = curright;// 连接cur和parentcur->_right = parent;// 修改parent父结点的指向if (ppnode == nullptr) // 如果此时parent是根结点,那么它没有父结点,且需要更新根结点{_root = cur;}else{if (ppnode->_left == parent){ppnode->_left = cur;}else{ppnode->_right = cur;}}// 改父结点指向cur->_parent = ppnode;parent->_parent = cur;// 维护bfcur->_bf = parent->_bf = 0;}template <class T>void AvlTree<T>::RotateLR(Node *parent){Node *cur = parent->_left, *curright = cur->_right;int bf_comp = curright->_bf; // 用于判断插入结点的左右位置RotateL(parent->_left); // 让cur成为curright的左子树RotateR(parent); // 让parent成为curright的右子树// curright是旋转后子树的根结点// 最终让curright的左子树给了cur的右子树,curright的右子树给了parent的左子树// if (_Height(curright) == 1)// {// curright->_bf = 0;// cur->_bf = 0;// parent->_bf = 0;// }if (bf_comp == 0){curright->_bf = 0;cur->_bf = 0;parent->_bf = 0;}else{if (bf_comp == -1) // 在curright的左边{// 说明cur的右子树多了1,使其与原先的左子树高度相等// 而parent的左子树是h-1,右子树是原先的hcurright->_bf = 0;cur->_bf = 0;parent->_bf = 1;}else if (bf_comp == 1) // 在curright的右边{// 说明parent的左子树多了1,使其与原先的右子树高度相等// 而cur的右子树是h-1,左子树是原先的hcurright->_bf = 0;cur->_bf = -1;parent->_bf = 0;}else{assert(false);}}}template <class T>void AvlTree<T>::RotateRL(Node *parent) // 插入结点在curleft的左右子树上其中一个位置{Node *cur = parent->_right, *curleft = cur->_left;int bf_comp = curleft->_bf; // 用于判断插入结点的左右位置RotateR(parent->_right); // 让cur成为curleft的右子树RotateL(parent); // 让parent成为curleft的左子树// curleft是旋转后子树的根结点// 最终让原curleft的右子树给了cur的左子树,curleft的左子树给了parent的右子树// if (_Height(curleft) == 1)// {// curleft->_bf = 0;// cur->_bf = 0;// parent->_bf = 0;// }if (bf_comp == 0){curleft->_bf = 0;cur->_bf = 0;parent->_bf = 0;}else{if (bf_comp == -1) // 在curleft的左边{// 说明parent右子树多了1,使其与原先的左子树高度相等// 而cur的左子树是h-1,右子树是原先的hcurleft->_bf = 0;cur->_bf = 1;parent->_bf = 0;}if (bf_comp == 1) // 在curleft的右边{// 说明cur的左子树多了1,使其与原先的右子树高度相等// 而parent的右子树是h-1,左子树是原先的hcurleft->_bf = 0;cur->_bf = 0;parent->_bf = -1;}}}
}