别人给公司做的网站字体侵权吗,百度有哪些app产品,网站开发后怎么上线,有没有专门做家纺的网站相关的数据结构#xff1a; 搜索二叉树-CSDN博客 AVL树的创建与检测-CSDN博客 个人主页#xff1a;敲上瘾-CSDN博客 个人专栏#xff1a;游戏、数据结构、c语言基础、c学习、算法 目录
一、红黑树规则#xff1a;
二、红黑树的插入
1.变色
2.单旋变色
3.双旋变色
三、… 相关的数据结构 搜索二叉树-CSDN博客 AVL树的创建与检测-CSDN博客 个人主页敲上瘾-CSDN博客 个人专栏游戏、数据结构、c语言基础、c学习、算法 目录
一、红黑树规则
二、红黑树的插入
1.变色
2.单旋变色
3.双旋变色
三、红黑树的验证
四、源码 一、红黑树规则
红黑树规则重点
每个结点不是红⾊就是⿊⾊。根结点是⿊⾊的。如果⼀个结点是红⾊的则它的两个孩⼦结点必须是⿊⾊的也就是说任意⼀条路径不会有连续的红⾊结点。对于任意⼀个结点从该结点到其所有NULL结点的简单路径上均包含相同数量的⿊⾊结点。 红黑树的性质都由以上4点规则决定的其中的一个性质红黑树最长路径的节点数量一定不会大于最短路径的两倍。这使得红黑树虽然不是完全平衡但高度差没有那么大查找效率依旧是longN级别的。 红黑树为什么能实现最长路径不会超过最短路径的两倍呢我们可以想一想如果其中任意一条路径有n个黑节点最短路径的颜色是如何分布最长路径颜色又是如何分布的呢其实很简单根据第4条规则我们可以最短的路径的节点不可能低于n个即最少的时候为n个黑节点。又由第3条规则可以知道最长的路径的节点数不可能超过2n个即最多的时候为n个黑节点n个红节点。 所以我们要实现一个红黑树只需要维护以上4条规则即可。
二、红黑树的插入 因为红黑树也是一棵二叉搜索树所以我们先按二叉搜索树的逻辑将节点进行插入需要注意插入的是红色节点因为黑色节点维护起来非常的困难。 1如果该新节点的父亲为黑节点不用再做调整直接返回。 2如果不是则需要分情况进行更新 在这里我们是因为父亲为红节点才进行更新的因为在插入之前已经保证这是一棵红黑树又因为父亲为红色所以爷爷一定为黑色。 而我们要做的就是把新节点的父亲更新成黑色如何更新如何分情况呢关键就在于叔叔是否存在以及叔叔的颜色。接下来就以父亲为爷爷的左孩子为例进行讲解父亲为爷爷的右孩子同理。 说明下图中假设我们把新增结点标识为c(cur)c的⽗亲标识为p(parent)p的⽗亲标识为 g(grandfather)p的兄弟标识为uuncle。 1.变色 叔叔u存在且为红 该情况比较简单因为要保持每条路径的黑节点的个数相同所以直接将g的黑色分配给p和u而g变为红色即可。如上图 但是有个问题g的父亲是完全有可能是红节点的照这样的话又出现了两个连续的红色节点所以再以g作为新的c节点g的父亲作为新的p节点然后更新g最后循环进行调整就可以解决。
如下x是通过变色更新上来的节点 2.单旋变色 叔叔u不存在或为黑 当叔叔u不存在或为黑我们发现无论如何变色都是无法调整得当的所以这就需要旋转变色操作了。
该情况又可以细分为两种情况
c和p在g的同一侧需要单旋变色c和p在g的不同侧需要双旋变色
首先来分析第一种情况
如下以g为旋转点进行右旋然后将p更新为黑色c和g为红色。 关于旋转请参考AVL树的创建与检测-CSDN博客
3.双旋变色 叔叔u不存在或为黑并且c和p在g的不同侧我们进行双旋变色如下 注意因为考虑要使根节点为黑色防止在调整过程将根节点改为黑色所以在每次调整过后直接将根节点更新为黑色。
三、红黑树的验证 红黑树的验证并不用去验证高度差也不用去验证最长路径的节点数是不是小于最短路径的两倍因为即使这一些条件都满足也不一定是红黑树想要验证红黑树只需要验证是否满足红黑树的规则即可只要满足了那些规则那么红黑树的性质自然就有了。
规则1就不用验证因为这是必然的规则2也是比较简单一个if语句就解决。规则3的验证遍历整棵树当遍历到红色节点时判断它的父亲是否为黑色不是则违反规则。规则4的验证任意选择一条路径如一直往左走并记录其中的黑节点数目记为count然后遍历整棵树的所有路径并记录黑节点数目然后在路径结束后与count比较如果不相等则违反规则。
四、源码
#pragma once
#includeiostream
using namespace std;
enum Color{red, black};
templateclass T
struct RBNode
{RBNode(T key):data(key),color(red),left(nullptr),right(nullptr),prev(nullptr){}T data;enum Color color;RBNodeT* left;RBNodeT* right;RBNodeT* prev;
};
templateclass T
class RBTree
{
public:typedef RBNodeT Node;RBTree():root(nullptr){}bool insert(T data){Node* newNode new Node(data);if (root nullptr){root newNode;root-color black;return true;}Node* cur root;Node* parent root;while (cur){parent cur;if (newNode-data.first cur-data.first)cur cur-left;else cur cur-right;}if (newNode-data.first parent-data.first)parent-left newNode;else parent-right newNode;newNode-prev parent;//需要调整cur newNode;Node* grandfather parent-prev;Node* uncle nullptr;while (parentparent-color red){grandfather parent-prev;if (parent grandfather-left){uncle grandfather-right;if (uncle uncle-color red){grandfather-color red;parent-color uncle-color black;cur grandfather;parent cur-prev;}else{if (cur parent-left){ReverseR(grandfather);parent-color black;grandfather-color red;}else{ReverseL(parent);ReverseR(grandfather);cur-color black;parent-color grandfather-color red;}}}else{uncle grandfather-left;if (uncle uncle-color red){grandfather-color red;parent-color uncle-color black;cur grandfather;parent cur-prev;}else{if (cur parent-right){ReverseL(grandfather);parent-color black;grandfather-color red;}else{ReverseR(parent);ReverseL(grandfather);cur-color black;parent-color grandfather-color red;}}}}root-color black;return true;}void ReverseR(Node* parent){Node* subL parent-left;Node* subLR subL-right;parent-leftsubLR;subL-right parent;//Node* pparent parent-prev;subL-prev pparent;if (pparent nullptr) root subL;else{if (pparent-left parent) pparent-left subL;else pparent-right subL;}if (subLR) subLR-prev parent;parent-prev subL;}void ReverseL(Node* parent){Node* subR parent-right;Node* subRL subR-left;parent-right subRL;subR-left parent;//Node* pparent parent-prev;subR-prev pparent;if (pparent nullptr) root subR;else{if (pparent-left parent) pparent-left subR;else pparent-right subR;}if (subRL) subRL-prev parent;parent-prev subR;}bool IsBalanceTree(){if (root nullptr) return true;if (root-color red) return false;int count 0;Node* cur root;while (cur){if (cur-color black) count;cur cur-left;}return Check(root, 0, count);}bool Check(Node* root,int path,const int refNum){if (root nullptr) return path refNum;if (root-color red root-prev-color red) return false;if (root-color black) path;return Check(root-left, path, refNum) Check(root-right, path, refNum);}
private:Node* root;
};
