成都网站优化教程,企业网站建立答辩问题,商业店铺设计,jetpack报错 wordpress红黑树 一.红黑树简单实现1.性质二.更新颜色1.情况一2.情况二3.情况三 3.完整代码(代码有注释#xff0c;稍微画图很容易理解,旋转部分可以看我的AVL树博客) 二.map和set1.基本实现2.迭代器 本篇的前置条件是AVL树的旋转和搜索树#xff0c;如果不了解可以看看我的AVL树博客 … 红黑树 一.红黑树简单实现1.性质二.更新颜色1.情况一2.情况二3.情况三 3.完整代码(代码有注释稍微画图很容易理解,旋转部分可以看我的AVL树博客) 二.map和set1.基本实现2.迭代器 本篇的前置条件是AVL树的旋转和搜索树如果不了解可以看看我的AVL树博客 一.红黑树简单实现
1.性质 红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的。 每个结点不是红色就是黑色。根节点是黑色的。如果一个节点是红色的则它的两个孩子结点是黑色的。对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点。每个叶子结点都是黑色的(此处的叶子结点指的是空结点。
创建节点 二.更新颜色
1.情况一
插入一个节点它的父亲是红色的并且它有叔叔且叔叔也是红色的。 2.情况二
如果叔叔不存在 此时单纯的变色是无法解决问题的需要进行旋转在此情况是右旋。 3.情况三
叔叔存在且为黑注意此时插入的点是在最下面cur经过上面的转变后到达图示的位置。 3.完整代码(代码有注释稍微画图很容易理解,旋转部分可以看我的AVL树博客)
测试
#includeRBTree.h
#includevectorint main()
{RBTreeint, int t;srand(time(0));vectorinta;for (int i 0; i 100; i){int x rand();a.push_back(x);}for (auto x : a)t.Insert(make_pair(x, x));cout t.IsBalance() endl;return 0;
}树
#includeiostream
#includeassert.h
using namespace std;enum Color
{RED,BLACK
};templateclass K,class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;RBTreeNode(const pairK,V kv)//初始化节点:_kv(kv),_left(nullptr),_right(nullptr),_parent(nullptr),_col(RED){}Color _col;
};templateclass K,class V
class RBTree
{
public:typedef RBTreeNodeK, V Node;bool Insert(const pairK, V kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;//根为黑色return true;}Node* parent _root;Node* cur _root;//一般的搜索二叉树插入while (cur){if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else if (kv.first cur-_kv.first){parent cur;cur cur-_left;}elsereturn false;}cur new Node(kv);cur-_parent parent;if (parent-_kv kv) parent-_left cur;else parent-_right cur;//进行颜色更新while (parent parent-_col RED){Node* grandparent parent-_parent;Node* uncle;//找到叔叔if (grandparent-_left parent)uncle grandparent-_right;elseuncle grandparent-_left;//如果叔叔存在且为红色if (uncle uncle-_col RED){//变颜色parent-_col uncle-_col BLACK;grandparent-_col RED;//继续向上cur grandparent;parent cur-_parent;}//如果叔叔不存在或者是黑色else{//parent是左cur是左进行右单旋if (grandparent-_left parent parent-_left cur){RotateR(grandparent);grandparent-_col RED;parent-_col BLACK;}//parent是左cur是右进行左右旋else if (grandparent-_left parent parent-_right cur){RotateL(parent);RotateR(grandparent);cur-_col BLACK;grandparent-_col RED;}//parent是右,cur是右,进行左单旋else if (grandparent-_right parent parent-_right cur){RotateL(grandparent);grandparent-_col RED;parent-_col BLACK;}//parent是右cur是左,进行右左旋else{RotateR(parent);RotateL(grandparent);cur-_col BLACK;grandparent-_col RED;}}}_root-_col BLACK;}//旋转函数void RotateL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;Node* ppnode parent-_parent;//记录父节点的父节点//父节点的右孩子变成curleftparent-_right curleft;if (curleft)//细节注意curleft为空时不能操作curleft-_parent parent;//父节点变为cur的左孩子cur-_left 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;}}void RotateR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;Node* pphead parent-_parent;//父节点到cur右边cur-_right parent;parent-_parent cur;//父节点的左孩子变成currightparent-_left curright;if (curright)curright-_parent parent;//cur的父节点变为原来父节点的父节点if (pphead)//如果不是根节点{if (pphead-_left parent)pphead-_left cur;elsepphead-_right cur;cur-_parent pphead;}else{_root cur;cur-_parent nullptr;}}void RotateRL(Node* parent){Node* cur parent-_right;Node* curleft cur-_left;RotateR(parent-_right);RotateL(parent);}void RotateLR(Node* parent){Node* cur parent-_left;Node* curright cur-_right;RotateL(parent-_left);RotateR(parent);}//测试是否出问题bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){//根是否为黑色if (_root-_col ! BLACK){cout 根不是红色endl;return false;}int blackcheck 0;Node* cur _root;while (cur){if (cur-_col BLACK)blackcheck;cur cur-_left;}//判断是否有两个连续的红色和每条路径的黑色是否相同return CheckColor(_root,blackcheck,0);}bool CheckColor(Node*root,int blackcheck,int blacknum){if (root nullptr){//检查是否每条路径的黑色相同if (blackcheck ! blacknum){cout 路径上黑色个数不同 ;return false;}return true;}//判断是否有两个连续的红色Node* parent root-_parent;if (root-_col RED){if (parent parent-_col RED){cout 有连续的红色 ;return false;}}if (root-_col BLACK) blacknum;return CheckColor(root-_left, blackcheck, blacknum) CheckColor(root-_right, blackcheck, blacknum);}
private:Node* _root nullptr;
};
二.map和set
1.基本实现
map和set虽然功能不同但在库里都是使用红黑树实现的接下来对红黑树的代码进行改造。在库里set和map走的是泛型也就是map和set可以使用同一份红黑树代码。
对红黑树进行泛化处理方便之后传参 这里有一个问题对于data如果是set那么我们可以直接比较但如果是map呢map的T是一个pair我们是不能直接比较的为了解决这个问题我们可以使用仿函数如果不了解可以看看我的仿函数这篇博客。
map里返回pair的firist
set为了保持一致直接返回key
在树里创建一个对象用该对象的规则进行比较
分别对map和set加入插入操作 2.迭代器
首先需要明确迭代器的功能就是能够将整棵树进行中序遍历。 我们需要*–!等操作。对于操作我们需要进行中序遍历。 其他一些小功能就不细说下面是完整代码
RBTree.h
#pragma once
#includeiostream
using namespace std;enum Colour
{RED,BLACK
};templateclass T
struct RBTreeNode
{RBTreeNodeT* _left;RBTreeNodeT* _right;RBTreeNodeT* _parent;T _data;Colour _col;RBTreeNode(const T data):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}
};templateclass T
struct __TreeIterator
{typedef RBTreeNodeT Node;typedef __TreeIteratorT Self;Node* _node;__TreeIterator(Node* node):_node(node){}T operator*(){return _node-_data;}T* operator-(){return _node-_data;}bool operator!(const Self s){return _node ! s._node;}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){if (cur parent-_left){break;}else{cur cur-_parent;parent parent-_parent;}}_node parent;}return *this;}
};// set-RBTreeK, K, SetKeyOfT _t;
// map-RBTreeK, pairK, V, MapKeyOfT _t;templateclass K, class T, class KeyOfT
struct RBTree
{typedef RBTreeNodeT Node;
public:typedef __TreeIteratorT iterator;// const_iteratoriterator begin(){Node* leftMin _root;while (leftMin leftMin-_left){leftMin leftMin-_left;}return iterator(leftMin);}iterator end(){return iterator(nullptr);}Node* Find(const K key){Node* cur _root;KeyOfT kot;while (cur){if (kot(cur-_data) key){cur cur-_right;}else if (kot(cur-_data) key){cur cur-_left;}else{return cur;}}return nullptr;}bool Insert(const T data){if (_root nullptr){_root new Node(data);_root-_col BLACK;return true;}Node* parent nullptr;Node* cur _root;KeyOfT kot;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);cur-_col RED;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;// u存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else // u不存在 或 存在且为黑{if (cur parent-_left){// g// p// cRotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// p// cRotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else // parent grandfather-_right{Node* uncle grandfather-_left;// u存在且为红if (uncle uncle-_col RED){// 变色parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续向上处理cur grandfather;parent cur-_parent;}else{if (cur parent-_right){// g// p// cRotateL(grandfather);grandfather-_col RED;parent-_col BLACK;}else{// g// p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}void RotateL(Node* parent){_rotateCount;Node* cur parent-_right;Node* curleft cur-_left;parent-_right curleft;if (curleft){curleft-_parent parent;}cur-_left 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;}}void RotateR(Node* parent){_rotateCount;Node* cur parent-_left;Node* curright cur-_right;parent-_left curright;if (curright)curright-_parent parent;Node* ppnode parent-_parent;cur-_right parent;parent-_parent cur;if (ppnode nullptr){_root cur;cur-_parent nullptr;}else{if (ppnode-_left parent){ppnode-_left cur;}else{ppnode-_right cur;}cur-_parent ppnode;}}bool CheckColour(Node* root, int blacknum, int benchmark){if (root nullptr){if (blacknum ! benchmark)return false;return true;}if (root-_col BLACK){blacknum;}if (root-_col RED root-_parent root-_parent-_col RED){cout root-_kv.first 出现连续红色节点 endl;return false;}return CheckColour(root-_left, blacknum, benchmark) CheckColour(root-_right, blacknum, benchmark);}bool IsBalance(){return IsBalance(_root);}bool IsBalance(Node* root){if (root nullptr)return true;if (root-_col ! BLACK){return false;}// 基准值int benchmark 0;Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}return CheckColour(root, 0, benchmark);}int Height(){return Height(_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;}private:Node* _root nullptr;public:int _rotateCount 0;
};Map.h
#includeRBTree.hnamespace Mine
{templateclass K, class Vclass map{struct MapKeyOfT{const K operator()(const pairK, V kv){return kv.first;}};public:typedef typename RBTreeK, pairK, V, MapKeyOfT::iterator iterator;iterator begin(){return _t.begin();}iterator end(){return _t.end();}V operator[](const K key);bool insert(const pairK, V kv){return _t.Insert(kv);}private:RBTreeK, pairK, V, MapKeyOfT _t;};
}
Set.h
#includeRBTree.hnamespace Mine
{templateclass Kclass set{struct SetKeyOfT{const K operator()(const K key){return key;}};public:typedef typename RBTreeK, 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, K, SetKeyOfT _t;};
}
