国家网站备案查询,wordpress 谷歌seo,王也道长冷酷头像,平面设计欣赏网站推荐目录
一、红黑树的概念
二、红黑树的性质
2.1 红黑树与AVL树的比较
三、红黑树的实现
3.1 红黑树节点的定义
3.2 数据的插入
3.2.1 红黑树的调整思路
3.2.1.1 cur为红#xff0c;f为红#xff0c;g为黑#xff0c;u存在且为红
3.2.1.2 cur为红#xff0c;f为红f为红g为黑u存在且为红
3.2.1.2 cur为红f为红g为黑u不存在/u存在且为黑
3.2.1.2.1 g、f、cur构成一条直线
3.2.1.2.2 g、f、cur构成一条折线
3.2.2 调整部分的代码实现
3.3 红黑树的验证
3.4 测试代码
四、红黑树实现完整代码 一、红黑树的概念
红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路 径会比其他路径长出俩倍因而是接近平衡的。 二、红黑树的性质
● 每个结点不是红色就是黑色
● 根节点是黑色的
● 如果一个节点是红色的则它的两个孩子结点是黑色的不允许出现连续的红色节点
● 对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点从根节点到每个叶子节点的空孩子路径上有相同数目的黑色节点
● 每个叶子结点的空孩子节点都是黑色的 根据上述的五条性质我们可以发现一个红黑树中如果有N个黑色节点则根节点到任意一个叶子节点的距离最短为㏒⑵N最长为2㏒⑵N
2.1 红黑树与AVL树的比较
我们来看到下面的红黑树 对于这棵红黑树如果将其看成一个AVL树是需要进行旋转的但是在红黑树结构中却不需要
所以红黑树是近似平衡的在搜索效率上会略逊AVL树一些但是红黑树在结构上不要求绝对的平衡这就造成插入相同的数据红黑树翻转的次数少于AVL树
实际使用中在经常进行增删的场景下红黑树性能比AVL树更优并且红黑树实现比较简单所以实际运用中红黑树更多 三、红黑树的实现
3.1 红黑树节点的定义
enum Colour
{RED,BLACK
};templateclass Key, class Val
struct RBTreeNode
{RBTreeNodeKey, Val* _left;RBTreeNodeKey, Val* _right;RBTreeNodeKey, Val* _parent;//多一个指针指向其父节点,方便我们的后续操作pairKey, Val _kv;Colour _col;//颜色标识RBTreeNode(const pairKey, Val kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)//构造时,优先将节点的颜色置为红色{}
};在这里提一下为什么要默认将节点的颜色置为红色
在我们向红黑树中插入一个新节点时如果将该节点置为黑色就肯定会影响红黑树性质中的第四条对于每个结点从该结点到其所有后代叶结点的简单路径上均包含相同数目的黑色结点
例如
我们现在在上面这棵树中不管在哪个叶子节点的下方插入一个黑色的新增节点从根节点到插入的节点的空孩子的路径上的黑色节点数目会变为4而从根节点到其他叶子节点的空孩子的路径上的黑色节点数目会都为3
所以我们将新增节点的颜色置为红色就一定不会违反第四条红黑树性质但是第三条呢如果插入节点的父节点是红色的怎么办
怎么办我们后面再说反正总归比置为黑色一定会违反第四条性质好吧 3.2 数据的插入
由于红黑树也是平衡二叉搜索树的一种我们在插入数据时也要找到合适的位置进行插入
templateclass Key, class Val
class RBTree
{typedef RBTreeNodeKey, Val Node;
public:bool Insert(const pairKey,Val kv){Node* cur _root, * parent nullptr;while (cur)//找到合适的位置{if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else{cout 插入的值重复 endl;return false;}}cur new Node(kv);cur-_parent parent;//将插入的节点连接上二叉树if (parent nullptr){_root cur;}else if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right cur;}return true;}private:Node* _root nullptr;
};插入到合适的位置之后我们还要检查是否破坏了红黑树的结构由于我们插入的是红色节点所以只会出现两个红色节点连续的情况如果出现了该情况我们就要对其进行分类讨论并解决
3.2.1 红黑树的调整思路
下面我们将出现异常情况的两个节点的那个子节点叫做curcur的父节点叫做father简称ffather的父节点叫做grandfather简称gfather的兄弟节点叫做uncle简称u
例如
接下来我们分类讨论
3.2.1.1 cur为红f为红g为黑u存在且为红
下面画出的情况表示的是抽象出的情况A、B、C、D、E都是满足构成红黑树的子树 对于这种情况我们先将f和u节点变黑再将g节点变红即可 调整完后要记得再向上检查g节点的父节点是否为红色哦~如果g节点为整棵红黑树的根最后要将其颜色置为黑 3.2.1.2 cur为红f为红g为黑u不存在/u存在且为黑
3.2.1.2.1 g、f、cur构成一条直线
对于这种情况若f为g的左孩子cur为f的左孩子则进行右单旋 再将f变黑g变红 相反 f为g的右孩子cur为f的右孩子则进行左单旋转 再将f变黑g变红 3.2.1.2.2 g、f、cur构成一条折线
f为g的左孩子cur为f的右孩子则做左右双旋旋转完后将cur节点颜色置黑、g节点颜色置红 相反 f为g的右孩子cur为f的左孩子则做右左双旋旋转完后将cur节点颜色置黑、g节点颜色置红 对于旋转操作还不熟悉的同学可以看到这里【数据结构高阶】AVL树 3.2.2 调整部分的代码实现
templateclass Key, class Val
class RBTree
{typedef RBTreeNodeKey, Val Node;
public:bool Insert(const pairKey, Val kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* cur _root, * parent nullptr;while (cur)//找到合适的位置{if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else{cout 插入的值重复 endl;return false;}}cur new Node(kv);//将插入的节点连接上二叉树if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right 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)//cur为红p为红g为黑u存在且为红{parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上更新cur grandfather;parent cur-_parent;}elsecur为红p为红g为黑u不存在/u存在且为黑{if (cur parent-_left)//cur在p的左边,p也在g的左边构成一条直线{//右单旋RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else//cur在p的右边,p在g的左边构成一条折线{//左右双旋RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//调整完跳出}}else{Node* uncle grandfather-_left;if (uncle uncle-_col RED)//cur为红p为红g为黑u存在且为红{parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上更新cur grandfather;parent cur-_parent;}elsecur为红p为红g为黑u不存在/u存在且为黑{if (cur parent-_right)//cur在p的右边,p也在g的右边构成一条直线{//左单旋RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else//cur在p的左边,p在g的右边构成一条折线{//右左双旋RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//调整完跳出}}}_root-_col BLACK;//确保即便进行过调整后根节点颜色为黑return true;
}private:void RotateL(Node* parent)//左单旋{Node* subR parent-_right;Node* subRL subR-_left;Node* pparent parent-_parent;parent-_right subRL;//更新parent的右节点if (subRL)//防止该节点为空{subRL-_parent parent;//更新subRL的父节点}parent-_parent subR;//更新parent的父节点subR-_left parent;//subR的左子树置为parentsubR-_parent pparent;//更新subR的父节点if (pparent nullptr)//旋转的是整棵树{_root subR;//更新根节点}else//将旋转后的子树链接上整个二叉树{if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}}}void RotateR(Node* parent)//右单旋{Node* subL parent-_left;Node* subLR subL-_right;Node* pparent parent-_parent;parent-_left subLR;//更新parent的左节点if (subLR)//防止该节点为空{subLR-_parent parent;//更新subLR的父节点}parent-_parent subL;//更新parent的父节点subL-_right parent;//subL的右子树置为parentsubL-_parent pparent;//更新subL的父节点if (pparent nullptr)//旋转的是整棵树{_root subL;//更新根节点}else//将旋转后的子树链接上整个二叉树{if (pparent-_left parent){pparent-_left subL;}else{pparent-_right subL;}}}private:Node* _root nullptr;
};3.3 红黑树的验证
下面我们来写段代码来验证一课树是不是红黑树
templateclass Key, class Val
class RBTree
{typedef RBTreeNodeKey, Val Node;
public:bool IsBalance(){if (_root _root-_col RED){cout 根节点颜色是红色 endl;return false;}int benchmark 0;Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}// 连续红色节点return _Check(_root, 0, benchmark);}private:bool _Check(Node* root, int blackNum, int benchmark)//计算每条路径上黑色节点的个数{if (root nullptr){if (benchmark ! blackNum){cout 某条路径黑色节点的数量不相等 endl;return false;}return true;}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return _Check(root-_left, blackNum, benchmark) _Check(root-_right, blackNum, benchmark);}private:Node* _root nullptr;
};3.4 测试代码
void Test_RBTree()
{const size_t N 50000;RBTreeint, int t;for (size_t i 0; i N; i){size_t x rand() i;t.Insert(make_pair(x, x));}t.InOrder();cout t.IsBalance();
}int main()
{Test_RBTree();return 0;
}
测试效果 四、红黑树实现完整代码
#includeiostreamusing namespace std;enum Colour
{RED,BLACK
};templateclass Key, class Val
struct RBTreeNode
{RBTreeNodeKey, Val* _left;RBTreeNodeKey, Val* _right;RBTreeNodeKey, Val* _parent;//多一个指针指向其父节点,方便我们的后续操作pairKey, Val _kv;Colour _col;//颜色标识RBTreeNode(const pairKey, Val kv):_left(nullptr),_right(nullptr),_parent(nullptr),_kv(kv),_col(RED)//默认构造时,优先将节点的颜色置为红色{}
};templateclass Key, class Val
class RBTree
{typedef RBTreeNodeKey, Val Node;
public:bool Insert(const pairKey, Val kv){if (_root nullptr){_root new Node(kv);_root-_col BLACK;return true;}Node* cur _root, * parent nullptr;while (cur)//找到合适的位置{if (kv.first cur-_kv.first){parent cur;cur cur-_left;}else if (kv.first cur-_kv.first){parent cur;cur cur-_right;}else{cout 插入的值重复 endl;return false;}}cur new Node(kv);//将插入的节点连接上二叉树if (kv.first parent-_kv.first){parent-_left cur;}else{parent-_right 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)//cur为红p为红g为黑u存在且为红{parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上更新cur grandfather;parent cur-_parent;}elsecur为红p为红g为黑u不存在/u存在且为黑{if (cur parent-_left)//cur在p的左边,p也在g的左边构成一条直线{//右单旋RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else//cur在p的右边,p在g的左边构成一条折线{//左右双旋RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//调整完跳出}}else{Node* uncle grandfather-_left;if (uncle uncle-_col RED)//cur为红p为红g为黑u存在且为红{parent-_col BLACK;uncle-_col BLACK;grandfather-_col RED;//继续向上更新cur grandfather;parent cur-_parent;}elsecur为红p为红g为黑u不存在/u存在且为黑{if (cur parent-_right)//cur在p的右边,p也在g的右边构成一条直线{//左单旋RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else//cur在p的左边,p在g的右边构成一条折线{//右左双旋RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;//调整完跳出}}}_root-_col BLACK;//确保即便进行过调整后根节点颜色为黑return true;
}void InOrder()//中序遍历{_InOrder(_root);cout endl;}bool IsBalance(){if (_root _root-_col RED){cout 根节点颜色是红色 endl;return false;}int benchmark 0;Node* cur _root;while (cur){if (cur-_col BLACK)benchmark;cur cur-_left;}// 连续红色节点return _Check(_root, 0, benchmark);}private:void RotateL(Node* parent)//左单旋{Node* subR parent-_right;Node* subRL subR-_left;Node* pparent parent-_parent;parent-_right subRL;//更新parent的右节点if (subRL)//防止该节点为空{subRL-_parent parent;//更新subRL的父节点}parent-_parent subR;//更新parent的父节点subR-_left parent;//subR的左子树置为parentsubR-_parent pparent;//更新subR的父节点if (pparent nullptr)//旋转的是整棵树{_root subR;//更新根节点}else//将旋转后的子树链接上整个二叉树{if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}}}void RotateR(Node* parent)//右单旋{Node* subL parent-_left;Node* subLR subL-_right;Node* pparent parent-_parent;parent-_left subLR;//更新parent的左节点if (subLR)//防止该节点为空{subLR-_parent parent;//更新subLR的父节点}parent-_parent subL;//更新parent的父节点subL-_right parent;//subL的右子树置为parentsubL-_parent pparent;//更新subL的父节点if (pparent nullptr)//旋转的是整棵树{_root subL;//更新根节点}else//将旋转后的子树链接上整个二叉树{if (pparent-_left parent){pparent-_left subL;}else{pparent-_right subL;}}}void _InOrder(Node* root){if (root NULL)//如果是空树就直接结束{return;}_InOrder(root-_left);//先递归遍历其左子树cout root-_kv.first ;//再遍历其根节点_InOrder(root-_right);//最后递归遍历其右子树}bool _Check(Node* root, int blackNum, int benchmark){if (root nullptr){if (benchmark ! blackNum){cout 某条路径黑色节点的数量不相等 endl;return false;}return true;}if (root-_col BLACK){blackNum;}if (root-_col RED root-_parent root-_parent-_col RED){cout 存在连续的红色节点 endl;return false;}return _Check(root-_left, blackNum, benchmark) _Check(root-_right, blackNum, benchmark);}private:Node* _root nullptr;
};
