AVL树&&红黑树
目录
1..AVL
1.1简介
AVL树主要是用来解决普通的二叉搜索树的一个缺陷。
二叉搜索树如果插入顺序是有序或解决有序,那么整个树会呈现接近单支树的状态(就是一条线),这时候搜索的效率会退化到O(N)。
AVL树的条件:
每个子树及其子树满足条件:左右子树高度差不超过1;
之所以高度差不超过1而不是相等,是因为相等太苛刻,有时候无法满足,比如2个节点或4个节点。
这个高度差,可以称为平衡因子,左子树高度-右子树高度,或右子树高度-左子树高度,都行。因为最后是看平衡因子的绝对值。
注意,我们自己写AVL树可以采取每个节点多一个平衡因子,方便控制,但不是必须。
如果一个二叉搜索树是高度平衡的,那么就是AVL树,有n个节点,那高度可以保持在log2 n,搜索时间复杂度可以保持在log2 n
1.2avl的平衡因子
平衡因子,非必须。可以尝试不加,这里是右-左(就是右子树高度减去左子树高度)
利用平衡因子可以快速判断树的情况。
过程:
先按搜索树规则插入
更新平衡因子(检查是否是AVL树)
怎么更新?
新增节点会影响哪些节点的平衡因子呢?
1.影响新增节点的祖先节点(父亲、爷爷等)
注意,一定会影响父节点,但是爷爷,则要看父节点的高度有没有变化,从而影响爷爷,以此类推。
下面是情况分析。
1.1更新后,新增节点的父节点平衡因子变成0,意味着父节点所在子树高度不变,不影响爷爷
因为0,说明父节点的左右子树高度相同的,也就是说新增节点加在了父节点原先子树中矮的一边
满足AVL树规则,不需要继续向上更新,更新结束
1.2更新后,新增节点的父节点平衡因子变成-1/1,意味着父节点所在子树高度变了,会影响爷爷
因为1/-1,说明原先父节点平衡因子为0,新增节点在某一子树插入,导致更新后父节点的平衡因子改变
但是还是满足AVL树规则,需要继续向上更新
1.3更新后,父节点平衡因子为2/-2,说明违反了AVL规则,需要处理->旋转,选择之后因为高度没有变,因此结束更新
1.4一值更新到AVL树的根节点,也结束更新
1.5简而言之就是,当前节点的平衡因子是否改变,取决于子树的高度有没有变
2.更新原则,要根据平衡因子的定义,这里用右-左
那么如果新增节点是父节点左边,则父节点平衡因子--,否则++
1.3旋转(核心)
情况分析:
1.3.1左单旋
在当前树的较高右子树右侧插入新节点。
h是高度
这个旋转方式,主要为了让3的左子树高度升上来,这样整体就平衡了
void RotateL(Node* parent) { //parent是平衡因子更新后为2/-2的节点 Node* subR = parent->right; Node* subRL = subR->left; parent->right = subRL; if(subRL)subRL->parent = parent;//注意,可能为空节点 //注意处理parent关系 subR->left = parent; Node* ppnode = parent->parent; parent->parent = subR; if (root == parent)//如果parent本身就是avl树的根,就直接让subR成为新的根节点即可 { 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; }
1.3.2右单旋
这个情况跟上面类似
void RotateR(Node* parent) { //parent是平衡因子更新后为2/-2的节点 Node* subL = parent->left; Node* subLR = subL->right; parent->left = subLR; if (subLR)subLR->parent = parent;//注意,可能为空节点 //注意处理parent关系 subL->right = parent; Node* ppnode = parent->parent; parent->parent = subL; if (root == parent)//如果parent本身就是avl树的根,就直接让subR成为新的根节点即可 { root = subL; subL->parent = nullptr; } else { if (ppnode->left == parent) { ppnode->left = subL; } else { ppnode->right = subL; } subL->parent = ppnode; } //注意改变平衡因子 parent->bf = 0; subL->bf = 0; }
1.3.3先左单旋再右单旋
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); } }
1.3.4先右旋再左旋
void RotateRL(Node* parent) { Node* subR = parent->right; Node* subRL = subR->left; int bf = subRL->bf; RotateR(subR); RotateL(parent); if (bf == 1) { subR->bf = 0; subRL->bf = 0; parent->bf = -1; } else if (bf == -1) { subR->bf = 0; subRL->bf = 1; parent->bf = 0; } else if (bf == 0) { subR->bf = 0; subRL->bf = 0; parent->bf = 0; } }
1.3.5特殊情况
这两个都是上面两种情况可能会出现的,即一个三角形的形状。这时候平衡因子应该都是0
1.4完整代码
#pragma once #include<assert.h> #include<vector> template<class K,class V> struct AVLTreeNode { pair<K, V> _kv; AVLTreeNode<K, V>* left;//左子树 AVLTreeNode<K, V>* right;//右子树 AVLTreeNode<K, V>* parent;//父树或根数 int bf;//平衡因子,非必须。可以尝试不加,这里是右-左 AVLTreeNode(const pair<K,V>&kv) :left(nullptr) ,right(nullptr) ,parent(nullptr) ,bf(0) ,_kv(kv) {} }; 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); root->bf = 0; return true; } Node* parent = nullptr; Node* cur = root; while (cur) { if (cur->_kv.first > kv.first) { parent = cur; cur = cur->left; } else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->right; } else { return false; } } cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->right = cur; } else { parent->left = cur; } cur->parent = parent; while (parent) { if (cur == parent->left)parent->bf--; else parent->bf++; if (parent->bf == 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) { //说明此时是cur的右子树高了一层,导致parent的右子树高度+1,所以要用左单旋的方法,让cur的左子树高度提升 RotateL(parent); } else if (parent->bf == -2 && cur->bf == -1) { //说明此时是cur的左子树高了一层,导致parent的左子树高度+1,所以要用右单旋,让cur的右子树高度提升 RotateR(parent); } else if (parent->bf == -2 && cur->bf == 1) { RotateLR(parent); } else if(parent->bf==2&&cur->bf==-1) { //parent->bf == 2 && cur->bf == -1 RotateRL(parent); } break; } else { //插入前,该树就有问题,不符合AVL树 assert(false); } } return true; } 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; } bool IsBalance() { int h = 0; return _IsBalance(root,h); } private: //左单旋,在较高右子树右侧插入新节点,触发旋转时(某个祖先节点的平衡因子变为2/-2) void RotateL(Node* parent) { //parent是平衡因子更新后为2/-2的节点 Node* subR = parent->right; Node* subRL = subR->left; parent->right = subRL; if (subRL)subRL->parent = parent;//注意,可能为空节点 //注意处理parent关系 subR->left = parent; Node* ppnode = parent->parent; parent->parent = subR; if (root == parent)//如果parent本身就是avl树的根,就直接让subR成为新的根节点即可 { 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) { //parent是平衡因子更新后为2/-2的节点 Node* subL = parent->left; Node* subLR = subL->right; parent->left = subLR; if (subLR)subLR->parent = parent;//注意,可能为空节点 //注意处理parent关系 subL->right = parent; Node* ppnode = parent->parent; parent->parent = subL; if (root == parent)//如果parent本身就是avl树的根,就直接让subR成为新的根节点即可 { root = subL; subL->parent = nullptr; } else { if (ppnode->left == parent) { ppnode->left = subL; } else { ppnode->right = subL; } subL->parent = ppnode; } //注意改变平衡因子 parent->bf = 0; subL->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); if (bf == 1) { subR->bf = 0; subRL->bf = 0; parent->bf = -1; } else if (bf == -1) { subR->bf = 1; subRL->bf = 0; parent->bf = 0; } else if (bf == 0) { subR->bf = 0; subRL->bf = 0; parent->bf = 0; } } void _InOrder(Node* _root) { if (_root == nullptr) { return; } _InOrder(_root->left); cout << _root->_kv.first << " "; _InOrder(_root->right); } bool _IsBalance(Node* _root, int& height) { if (_root == nullptr) { height = 0; return true; } int leftHeight = 0; int rightHeight = 0; if (!_IsBalance(_root->left, leftHeight) || !_IsBalance(_root->right, rightHeight)) { return false; } if (rightHeight - leftHeight >= 2 || 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; } Node* root = nullptr;//根节点 }; //自测 void VLtest() { const int N =10000000; vector<int>v; v.reserve(N); //srand(time(NULL)); for (size_t i = 0; i < N; i++) { v.push_back(rand() + i); } size_t begin2 = clock(); AVLTree<int, int>t; for (auto x : v) { t.Insert(make_pair(x, x)); //cout <<x<<"[ "<<t.IsBalance() <<"]" << endl; } size_t end2 = clock(); cout << "Insert:" << end2 - begin2 << endl; cout << t.IsBalance() << endl; }
2.红黑树
2.1简介
红黑树是在每个节点增加了一个存储颜色的变量。可以是red也可以是black,通过着色方式的限制,使红黑树里没有一条路径比其他路径长2倍,因此是接近平衡的。
性质:
1.每个节点不是红色就是黑色。
2.根节点是黑色
3.如果一个节点是红色,则其孩子必是黑色
4.对于每个节点,从该节点到其所有后代节点叶节点的简单路径上,均含相同数目的黑色节点
5.每个叶子节点都是黑色的(此叶子结点指的是黑色)
为什么上面的性质可以保证红黑树,最长路径的节点数不会超过最短路径的2倍?
因为性质4,保证了最短路径和最长路径的黑色节点数目相同。在极端情况下,最短路径全是黑,最长路径除了相同的黑外,因为性质3,最长路径的其他节点只能是跟黑相同数量的红节点。
2.2插入
插入的时候,默认是红色,因为黑色会影响所有其他路径,所以我们默认红色。
红色的话,只有插在红色节点的孩子,才需要考虑对附近路径进行换色处理来符合规则。
在基于插入红色节点的情况下,继续分析。其中用的旋转跟上面的avl树旋转是一样的
情况1:cur节点为红,parent为黑。符合规则,无需处理。
情况2:cur节点为红,parent为红,grandfather为黑,uncle存在且为红。则g变红,p和u都变黑。
这样就保证了黑的数量不变,也没有连续的红色节点。注意,如果g是根,则无需变红,保持黑即可(这样每个路径都是同时多一个黑,符合规则),并且p和u是g的左孩子还是右孩子不影响。p、u有没有子树也不影响这里的处理方式。c是p的左孩子还是右孩子也不影响处理方式。
注意,这一步做完还没有结束,要继续把g当成c来看,重新进行情况的判断(比如情况1则就结束处理,情况2或3则继续处理)
情况3:cur节点为红,parent为红,grandfather为黑,uncle不存在。
说明cur就是新增节点,且p的另一个孩子必为空。
情况4:cur节点为红,parent为红,grandfather为黑,uncle存在且为黑。
说明cur不可能是新增(因为这样的话,u的路径黑色节点比c所在路径多),只可能是c是情况2的g变成的。
注意,不管是情况3还是情况4。都不能通过单纯的变色来解决。因为本质都是高度的极度不平衡,不管是u存在且为黑还是不存在,都说明了新增节点是在最长路径上插入的红,违反了规则。所以这里必须通过旋转+变色来解决。
具体旋转方式也要分情况:
1:c是p的左孩子,p是g的左孩子,则进行右单旋。然后让p变黑,g变红即可。
2:c是p的右孩子,p是g的右孩子,则进行左单旋。然后让p变黑,g变红即可。
3:c是p的右孩子,p是g的左孩子,则进行左右单旋。然后让c变黑,g变红
4:c是p的左孩子,p是g的右孩子,则进行右左单旋。然后让c变黑,g变红
实现代码
#include<vector> #include<assert.h> enum Color { RED, BLACK }; template<class K, class V> struct RBTreeNode { pair<K, V> _kv; RBTreeNode<K, V>* _left;//左子树 RBTreeNode<K, V>* _right;//右子树 RBTreeNode<K, V>* _parent;//父树或根数 Color _col; RBTreeNode(const pair<K, V>& kv) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _kv(kv) ,_col(RED) {} }; template<class K, class V> class RBTree { typedef RBTreeNode<K, V> Node; public: bool Insert(const pair<K, V>& kv)//插入 { if (_root == nullptr) { _root = new Node(kv); _root->_col = BLACK; return true; } Node* parent = nullptr; Node* cur = _root; while (cur) { if (cur->_kv.first > kv.first) { parent = cur; cur = cur->_left; } else if (cur->_kv.first < kv.first) { parent = cur; cur = cur->_right; } else { return false; } } cur = new Node(kv); if (parent->_kv.first < kv.first) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent;//上面部分就是搜索树插入就不注释了。 while (parent&&parent->_col == RED)//只有parent的颜色还是红色,我们就需要继续向上处理 { Node* grandfather = parent->_parent; //爷爷一定存在,因为如果parent是根节点,那p一定是黑,不会进入循坏,而如果p不是根,那爷爷一定存在。 if (parent == grandfather->_left) { Node* uncle = grandfather->_right; //情况1:u存在且为红 if (uncle && uncle->_col == RED) { //变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续往上 cur = grandfather; parent = cur->_parent; } //情况2:u不存在或则u存在且为黑 else if(uncle==nullptr||uncle->_col==BLACK) { if (cur == parent->_left) { //对g右单旋再变色 RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else if (cur == parent->_right) { //对p左单旋再对g右单旋,再变色 RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else if(parent==grandfather->_right) { Node* uncle = grandfather->_left; //情况1:u存在且为红 if (uncle && uncle->_col == RED) { //变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续往上 cur = grandfather; parent = cur->_parent; } //情况2:u不存在或则u存在且为黑 else if (uncle == nullptr || uncle->_col == BLACK) { if (cur == parent->_right) { //左单旋再变色 RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else if (cur == parent->_left) { //对p右单旋再对g左单旋,再变色 RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return true; } //右单旋 void RotateR(Node* parent) { //parent是平衡因子更新后为2/-2的节点 Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR)subLR->_parent = parent;//注意,可能为空节点 //注意处理parent关系 subL->_right = parent; Node* ppnode = parent->_parent; parent->_parent = subL; if (_root == parent)//如果parent本身就是avl树的根,就直接让subR成为新的根节点即可 { _root = subL; subL->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subL; } else { ppnode->_right = subL; } subL->_parent = ppnode; } } //左单旋 void RotateL(Node* parent) { //parent是平衡因子更新后为2/-2的节点 Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL)subRL->_parent = parent;//注意,可能为空节点 //注意处理parent关系 subR->_left = parent; Node* ppnode = parent->_parent; parent->_parent = subR; if (_root == parent)//如果parent本身就是avl树的根,就直接让subR成为新的根节点即可 { _root = subR; subR->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subR; } else { ppnode->_right = subR; } subR->_parent = ppnode; } } void InOrder() { _InOrder(_root); } void _InOrder(Node* root) { if (root == nullptr) { return; } _InOrder(root->_left); cout << root->_kv.first << " "; _InOrder(root->_right); } bool check(Node* cur,int blackNum,int refBlackNum) { if (cur == nullptr) { if (blackNum != refBlackNum) { cout << "黑色节点数量不相等" << endl; return false; } return true; } if (cur->_col == RED && cur->_parent->_col == RED) { cout << cur->_kv.first << "存在连续的红色" << endl; return false; } if (cur->_col == BLACK)blackNum++; return check(cur->_left, blackNum,refBlackNum) && check(cur->_right, blackNum, refBlackNum); } bool IsBalance() { if (_root && _root->_col == RED)return false; int refBlackNum = 0; Node* cur = _root; while (cur) { if (cur->_col == BLACK)refBlackNum++; cur = cur->_left; } return check(_root,0,refBlackNum); } private: Node* _root=nullptr; };
3.set&&map的模拟
3. 1.框架
根据库函数的写法,我们可以发现,库里的红黑树是一个泛用性的写法,使得map和set,虽然我们自己用的时候set只用给一个类型,map要给两个,但事实上,在红黑树的模板参数上,都是两个类型,只是红黑树的模板上,set是<key,value>,value==key。而map是<key,pair<key,value>>,而对于红黑树的节点,set是value,而map是pair<key,value>。
注意,为什么红黑树的模板一定要放个key呢,毕竟节点的参数已经决定了红黑树是kv,还是k模型了。因为红黑树还要进行find等操作,这样我们就需要提出key的类型,毕竟我们无法知道究竟传的kv还是k,这样就算pair的第一个参数key,我们也没法用.first的方式解决全部,毕竟k模型是直接value就是key了。
所以我们必须在红黑树的参数上放个额外的key,方便调用。
3.2迭代器
注意,这里迭代器的思路跟list的很像,只是在实现自增的时候,不像list只需去next,这里需要找中序的下一个。
假设it是当前节点的迭代器。
那么
如果 it的右子树不为空,则it的下一个则是右子树的最左节点。
如果it的右子树为空,则it的下一个节点则是,以it为当前节点,向其父节点走(当前节点一直变)。直到当前节点是其父节点的左孩子,那么it的下一个就是该父节点。
3.3实现
这是为了配合实现set和map修改过的一份红黑树
#pragma once #include<vector> #include<assert.h> enum Color { RED, BLACK }; template< class T> struct RBTreeNode { RBTreeNode<T>* _left;//左子树 RBTreeNode<T>* _right;//右子树 RBTreeNode<T>* _parent;//父树或根数 Color _col; T _data; RBTreeNode(const T& data) :_left(nullptr) , _right(nullptr) , _parent(nullptr) , _data(data) , _col(RED) {} }; template<class T,class Ptr,class Ref> struct RBTreeIterator { typedef RBTreeNode<T> Node; typedef RBTreeIterator<T,Ptr,Ref> Self; Node* _node; RBTreeIterator(Node*node) :_node(node) {} Ref operator*() { return _node->_data; } Ptr operator->() { return &_node->_data; } Self& operator++() { //说明右子树不为空 if (_node->_right)//右子树不为空,则找右子树最左节点 { Node* SubLeft = _node->_right; while (SubLeft->_left) { SubLeft = SubLeft->_left; } _node = SubLeft; } else//右子树为空 { Node* cur = _node; Node* parent = cur->_parent; while (parent&&cur == parent->_right)//直到cur是父节点的左孩子,或者cur是根节点,父节点为空 { cur = parent; parent = cur->_parent; } _node = parent; } return *this; } Self& operator--() { //说明左子树不为空 //注意,如果要--end,需要特殊判断。 if (_node->_left) { Node* SubLeft = _node->_left; while (SubLeft->_right) { SubLeft = SubLeft->_right; } _node = SubLeft; } else//左子树为空 { Node* cur = _node; Node* parent = cur->_parent; while (parent && cur == parent->_left) { cur = parent; parent = cur->_parent; } _node = parent; } return *this; } bool operator!=(const Self& s) { return _node != s._node; } }; //keyOfT是用来从T中取出key template<class K, class T,class KeyOfT> class RBTree { typedef RBTreeNode<T> Node; public: typedef RBTreeIterator<T,T*,T&> iterator; typedef RBTreeIterator<T,const T*,const T&> const_iterator; const_iterator rbegin() const { Node* SubLeft = _root; while (SubLeft && SubLeft->_left) { SubLeft = SubLeft->_left; } return const_iterator(SubLeft); } iterator begin() { Node* SubLeft = _root; while (SubLeft && SubLeft->_left) { SubLeft = SubLeft->_left; } return iterator(SubLeft); } iterator end() { return iterator(nullptr); } const_iterator rend() const{ return const_iterator(nullptr); } iterator Find(const K&key) { Node* cur = _root; KeyOfT kot; while (cur) { if (kot(cur->_data) > key) { cur = cur->_left; } else if (kot(cur->_data) < key) { cur = cur->_right; } else { return iterator(cur); } } return end(); } pair<iterator, bool> Insert(const T& data)//插入 { if (_root == nullptr) { _root = new Node(data); _root->_col = BLACK; return make_pair(iterator(_root), true); // } Node* parent = nullptr; Node* cur = _root; KeyOfT kot; while (cur) { if (kot(cur->_data) > kot(data)) { parent = cur; cur = cur->_left; } else if (kot(cur->_data) < kot(data)) { parent = cur; cur = cur->_right; } else { return make_pair(iterator(cur), false); // } } cur = new Node(data); Node* newnode = cur; if (kot(parent->_data) < kot(data)) { parent->_right = cur; } else { parent->_left = cur; } cur->_parent = parent;//上面部分就是搜索树插入就不注释了。 while (parent && parent->_col == RED)//只有parent的颜色还是红色,我们就需要继续向上处理 { Node* grandfather = parent->_parent; //爷爷一定存在,因为如果parent是根节点,那p一定是黑,不会进入循坏,而如果p不是根,那爷爷一定存在。 if (parent == grandfather->_left) { Node* uncle = grandfather->_right; //情况1:u存在且为红 if (uncle && uncle->_col == RED) { //变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续往上 cur = grandfather; parent = cur->_parent; } //情况2:u不存在或则u存在且为黑 else if (uncle == nullptr || uncle->_col == BLACK) { if (cur == parent->_left) { //对g右单旋再变色 RotateR(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else if (cur == parent->_right) { //对p左单旋再对g右单旋,再变色 RotateL(parent); RotateR(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } else if (parent == grandfather->_right) { Node* uncle = grandfather->_left; //情况1:u存在且为红 if (uncle && uncle->_col == RED) { //变色 parent->_col = uncle->_col = BLACK; grandfather->_col = RED; //继续往上 cur = grandfather; parent = cur->_parent; } //情况2:u不存在或则u存在且为黑 else if (uncle == nullptr || uncle->_col == BLACK) { if (cur == parent->_right) { //左单旋再变色 RotateL(grandfather); parent->_col = BLACK; grandfather->_col = RED; } else if (cur == parent->_left) { //对p右单旋再对g左单旋,再变色 RotateR(parent); RotateL(grandfather); cur->_col = BLACK; grandfather->_col = RED; } break; } } } _root->_col = BLACK; return make_pair(iterator(newnode), true); } //右单旋 void RotateR(Node* parent) { //parent是平衡因子更新后为2/-2的节点 Node* subL = parent->_left; Node* subLR = subL->_right; parent->_left = subLR; if (subLR)subLR->_parent = parent;//注意,可能为空节点 //注意处理parent关系 subL->_right = parent; Node* ppnode = parent->_parent; parent->_parent = subL; if (_root == parent)//如果parent本身就是avl树的根,就直接让subR成为新的根节点即可 { _root = subL; subL->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subL; } else { ppnode->_right = subL; } subL->_parent = ppnode; } } //左单旋 void RotateL(Node* parent) { //parent是平衡因子更新后为2/-2的节点 Node* subR = parent->_right; Node* subRL = subR->_left; parent->_right = subRL; if (subRL)subRL->_parent = parent;//注意,可能为空节点 //注意处理parent关系 subR->_left = parent; Node* ppnode = parent->_parent; parent->_parent = subR; if (_root == parent)//如果parent本身就是avl树的根,就直接让subR成为新的根节点即可 { _root = subR; subR->_parent = nullptr; } else { if (ppnode->_left == parent) { ppnode->_left = subR; } else { ppnode->_right = subR; } subR->_parent = ppnode; } } private: Node* _root = nullptr; };
#pragma once #include"RBTreeNew.h" namespace practice { template<class K> class set { //提出key struct SetKeyOfT { const K& operator()(const K& key) { return key; } }; public: //注意,第二个参数可以写成const K来防止set的key值被修改,导致红黑树的结构被破坏了。 typedef typename RBTree< K,const K, SetKeyOfT>::iterator iterator; typedef typename RBTree< K,const K, SetKeyOfT>::const_iterator const_iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } const_iterator rbegin() { return _t.rbegin(); } const_iterator rend() { return _t.rend(); } pair<iterator, bool> insert(const K& key) { return _t.Insert(key); } iterator Find(const K&key) { return _t.Find(key); } private: RBTree<K,const K,SetKeyOfT>_t; }; void test_set() { int a[] = { 4,2,6,1,3,5,15,7,16,14 }; set<int>m; for (auto x : a) { m.insert(x); } set<int>::const_iterator it = m.rbegin(); int c = 0; while (it != m.rend()) { cout << *it << " "; ++it; if (it!=m.end() && (*it) == 3 && c == 0)--it, c = 1; } //t.InOrder(); //cout << t.IsBalance() << endl; } }
这是set容器
#pragma once #include"RBTreeNew.h" namespace practice { template<class K,class V> class map { //提出key struct MapKeyOfT { const K& operator()(const pair<K,V>& kv) { return kv.first; } }; public: typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::iterator iterator; typedef typename RBTree<K, pair<const K, V>, MapKeyOfT>::const_iterator const_iterator; iterator begin() { return _t.begin(); } iterator end() { return _t.end(); } const_iterator rbegin() { return _t.rbegin(); } const_iterator rend() { return _t.rend(); } pair<iterator, bool> insert(const pair<const K, V>& kv) { return _t.Insert(kv); } iterator Find(const K& key) { return _t.Find(key); } V& operator[](const K& key) { pair<iterator, bool>ret = insert(make_pair(key, V())); return ret.first->second; } private: RBTree<K, pair<const K,V>,MapKeyOfT>_t; }; void test_map(){ int a[] = { 4,2,6,1,3,5,15,7,16,14 }; map<int, int>m; for (auto x : a) { m[x]++; } map<int,int>::iterator it = m.begin(); while (it != m.end()) { cout << it->first << " " << it->second << endl; ++it; } //t.InOrder(); //cout << t.IsBalance() << endl; } }
这是map容器。
原文地址:https://blog.csdn.net/MXZSL/article/details/141830626
免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!