韩国网站域名分类,平度网站制作,揭阳seo快速排名,上海市重点企业名单W...Y的个人主页#x1f495;
gitee代码仓库分享#x1f60a; 前言#xff1a;上篇博客中#xff0c;我们为了使二叉搜索树不会出现”一边倒“的情况#xff0c;使用了AVL树对搜索树进行了处理#xff0c;从而解决了数据在有序或者接近有序时出现的情况。但是AVL树还会…
W...Y的个人主页
gitee代码仓库分享 前言上篇博客中我们为了使二叉搜索树不会出现”一边倒“的情况使用了AVL树对搜索树进行了处理从而解决了数据在有序或者接近有序时出现的情况。但是AVL树还会有一大缺陷就是其性能的原因当我们在使其满足AVL树的规则时其付出的旋转代价是非常大的所以经常修改的结构就不适合AVL树。但是红黑树就可以补足AVL树的缺陷。
目录
1. 红黑树
1.1 红黑树的概念
1.2 红黑树的性质 1.3红黑树节点的定义 1.4红黑树的插入
1.5 红黑树与AVL树的比较
2. 红黑树模拟实现STL中的map与set
2.1 红黑树的迭代器
2.2 红黑树的改写与迭代器完整代码
2.3 map的封装
2.4 set的封装 1. 红黑树
1.1 红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或 Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路 径会比其他路径长出俩倍因而是接近平衡的。
假设最短路径为h则最长路径为2h。
1.2 红黑树的性质
1. 每个结点不是红色就是黑色2. 根节点是黑色的 3. 如果一个节点是红色的则它的两个孩子结点必须是黑色的 4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点)
为什么满足上述性质红黑树就可以保证其最长路径的节点树不会超过最短路径的两倍呢 前两个性质非常通俗易懂我们从第三个性质开始解读 3.没有连续的两个红色节点。 4.每条路径的黑色节点数是相同的。 所以我们就可以假设一颗红黑树中每条路径有两个黑色节点(满足性质4)那最短路径只可能是全黑节点最长路径一定是一黑一红节点(假设最短路径与最长路径都存在),那么红色节点只能在黑色节点中间插入这样才能满足性质3所以红黑树就可以保证其最长路径的节点树不会超过最短路径的两倍。
对比AVL树与红黑树的结构其AVL树的高度近似logN而红黑树的高度近似2logN所以相对于AVL树红黑树的搜索效率差一些但是几乎可以忽略不计因为logN足够小所以他们之间的搜索差距微乎其微。 1.3红黑树节点的定义
enum Colour
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Colour _col;RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv),_col(RED){}
};
在节点定义时我们默认将节点设置成红色节点这样如果出现连续的红色节点时我们可以进行变色操作通过维护一个子树来使红黑树合法但是如果插入一个黑色节点时我们就无法下手因为每条路的黑色节点数必须相同这样我们无法很好的进行操作使其合法化。 1.4红黑树的插入 红黑树是在二叉搜索树的基础上加上其平衡限制条件因此红黑树的插入可分为两步
1. 按照二叉搜索的树规则插入新节点
class RBTree
{typedef RBTreeNodeK, V Node;
public:bool Insert(const pairK, 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-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}else{return false;}}cur new Node(kv); // 红色的if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;
}
private:Node* _root nullptr;
};2. 检测新节点插入后红黑树的性质是否造到破坏: 因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何 性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连 在一起的红色节点此时需要对红黑树分情况来讨论 约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点 情况一: cur为红p为红g为黑u存在且为红 解决方式将p,u改为黑g改为红然后把g当成cur继续向上调整。
情况二: cur为红p为红g为黑u不存在/u存在且为黑 如果u存在且为黑 则cur一定不是新增节点因为这样就不满足性质4每条路径黑色节点个数相同。所以我们将上面图补充完整就是下图所示先是由情况一进行调整然后向上调整后才得到上图。所以情况一向上调整后的情况不一定又是情况一 这时我们就无法用情况一的做法进行调整 如果继续用情况一法则已经违反规则了。左右极度不均衡只能进行选择这时我们就可以类比使用AVL树中的旋转法则。(旋转变色)
p为g的左孩子cur为p的左孩子则进行右单旋转相反 p为g的右孩子cur为p的右孩子则进行左单旋转 p、g变色--p变黑g变红
在变色时我们不区分其p与u节点的左右但是在旋转时我们就要进行区分。
情况三: cur为红p为红g为黑u不存在/u存在且为黑 这种情况并不是一边高而是两边都高左边高右边也高。所以我们得使用左右/右左双旋转。 p为g的左孩子cur为p的右孩子左右双旋变色 p为g的右孩子cur为p的左孩子右左双旋变色 针对每种情况进行相应的处理即可。
bool Insert(const pairK, 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-_right;}else if (cur-_kv.first kv.first){parent cur;cur cur-_left;}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){Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;// 情况一叔叔存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}else{// 情况二叔叔不存在或者存在且为黑// 旋转变色if (cur parent-_left){// g// p u// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;} }else{Node* uncle grandfather-_left;// 情况一叔叔存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}else{// 情况二叔叔不存在或者存在且为黑// 旋转变色// g// u p// cif (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}void RotateL(Node* parent){rotateSize;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;}}void RotateR(Node* parent){rotateSize;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;}
1.5 红黑树与AVL树的比较 红黑树和AVL树都是高效的平衡二叉树增删改查的时间复杂度都是O($log_2 N$)红黑树不追 求绝对平衡其只需保证最长路径不超过最短路径的2倍相对而言降低了插入和旋转的次数 所以在经常进行增删的结构中性能比AVL树更优而且红黑树实现比较简单所以实际运用中红 黑树更多。
2. 红黑树模拟实现STL中的map与set
我们模拟实现了红黑树接下来就是对map与set的封装。
我们通过观察其stl源码切入进行仿写 我们发现无论是map还是set都复用的一个红黑树模板参数都是kv模型。通过源码我们可以发现setk - rb_treek,k mapk,v -rb_treek,pairconst k,v。所以节点中存什么内容是由v决定的不是k决定的。将红黑树写成泛型所以我们必须将上面写的红黑树的模板进行修改 进行封装后就可以解决复用红黑树的模板。 但是使用红黑树的模板时set和map所比较的对象不一样因为set比较的就是key而map比较的是value所以我们就得使用仿函数进行操作我们创建keyoft仿函数取出T对象中的key即可。
//set
struct SetKeyOfT{const K operator()(const K key){return key;}};//map
struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};
2.1 红黑树的迭代器
首先我们得封装一个红黑树的迭代器用来实现、--、*、-、!。这里的迭代器与list的迭代器非常类似可以用一个指针来实现其内容。但是与--必须确定下一个与上一个节点的关系这里我们可以使用中序遍历解决但是得用一个栈来辅助这里我们不想使用这样的方法我们可以找规律来实现 逻辑 1.it指向节点右不为空下一个就是右子树的最左节点 2.it指向节点右为空意味着这个节点的子树中序访问完了下一个节点找祖先里面的孩子父亲左的那个祖先。 --逻辑与相反 这样迭代器就很好解决了
templateclass T
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT Self;Node* _node;RBTreeIterator(Node* node):_node(node){}T operator*(){return _node-_data;}T* 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 parent;parent cur-_parent;}_node parent;}return *this;}Self operator--(){// return *this;}bool operator!(const Self s){return _node ! s._node;}bool operato (const Self s){return _node s._node;}
};
迭代器的好处是可以方便遍历是数据结构的底层实现与用户透明。如果想要给红黑树增加迭代 器需要考虑以前问题
begin()与end() STL明确规定begin()与end()代表的是一段前闭后开的区间而对红黑树进行中序遍历后 可以得到一个有序的序列因此begin()可以放在红黑树中最小节点(即最左侧节点)的位 置end()放在最大节点(最右侧节点)的下一个位置关键是最大节点的下一个位置在哪块 能否给成nullptr呢答案是行不通的因为对end()位置的迭代器进行--操作必须要能找最 后一个元素此处就不行因此最好的方式是将end()放在头结点的位置
typedef RBTreeIteratorT iterator;iterator begin()
{Node* subLeft _root;while (subLeft subLeft-_left){subLeft subLeft-_left;}return iterator(subLeft);
}iterator end()
{return iterator(nullptr);
}
//map
typedef typename RBTreeK, pairconst K, V, MapKeyOfT::iterator iterator;
iterator begin()
{return _t.begin();
}iterator end()
{return _t.end();
}bool insert(const pairK, V kv)
{return _t.Insert(kv);
}
//settypedef typename RBTreeK, const K, SetKeyOfT::iterator iterator;iterator begin()
{return _t.begin();
}iterator end()
{return _t.end();
}bool insert(const K key)
{return _t.Insert(key);
}2.2 红黑树的改写与迭代器完整代码
#pragma once
#includevectorenum Colour
{RED,BLACK
};templateclass T
struct RBTreeNode
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;Colour _col;T _data;RBTreeNode(const T data):_left(nullptr), _right(nullptr), _parent(nullptr), _data(data), _col(RED){}
};templateclass T
struct RBTreeIterator
{typedef RBTreeNodeT Node;typedef RBTreeIteratorT Self;Node* _node;RBTreeIterator(Node* node):_node(node){}T operator*(){return _node-_data;}T* 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 parent;parent cur-_parent;}_node parent;}return *this;}Self operator--(){// return *this;}bool operator!(const Self s){return _node ! s._node;}bool operato (const Self s){return _node s._node;}
};// set-RBTreeK, K, SetKeyOfT
// map-RBTreeK, pairK, V, MapKeyOfT// KeyOfT仿函数 取出T对象中的key
templateclass K, class T, class KeyOfT
class RBTree
{typedef RBTreeNodeT Node;
public:typedef RBTreeIteratorT iterator;iterator begin(){Node* subLeft _root;while (subLeft subLeft-_left){subLeft subLeft-_left;}return iterator(subLeft);}iterator end(){return iterator(nullptr);}bool Insert(const T data){if (_root nullptr){_root new Node(data);_root-_col BLACK;return true;}KeyOfT kot;Node* parent nullptr;Node* cur _root;while (cur){if (kot(cur-_data) kot(data)){parent cur;cur cur-_right;}else if (kot(cur-_data) kot(data)){parent cur;cur cur-_left;}else{return false;}}cur new Node(data); // 红色的if (kot(parent-_data) kot(data)){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;while (parent parent-_col RED){Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;// 情况一叔叔存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}else{// 情况二叔叔不存在或者存在且为黑// 旋转变色if (cur parent-_left){// g// p u// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p u// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else{Node* uncle grandfather-_left;// 情况一叔叔存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}else{// 情况二叔叔不存在或者存在且为黑// 旋转变色// g// u p// cif (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}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;}}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;}}private:Node* _root nullptr;
};
2.3 map的封装
namespace why
{templateclass K, class Vclass map{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename RBTreeK, pairconst K, V, MapKeyOfT::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const pairK, V kv){return _t.Insert(kv);}private:RBTreeK, pairconst K, V, MapKeyOfT _t;};
}
2.4 set的封装
#includeRBTree.h
namespace why
{templateclass Kclass set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename RBTreeK, const K, SetKeyOfT::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}bool insert(const K key){return _t.Insert(key);}private:RBTreeK, const K, SetKeyOfT _t;};
}
