网站微信公众号链接怎么做,电子商城网站设计论文,教育网站安全建设方案,沙坪坝网站建设各位大佬好#xff0c;我是落羽#xff01;一个坚持不断学习进步的大学生。 如果您觉得我的文章有所帮助#xff0c;欢迎多多互三分享交流#xff0c;一起学习进步#xff01; 也欢迎关注我的blog主页: 落羽的落羽 一、红黑树的概念与规则
红黑树是一种更加特殊的平衡二… 各位大佬好我是落羽一个坚持不断学习进步的大学生。 如果您觉得我的文章有所帮助欢迎多多互三分享交流一起学习进步 也欢迎关注我的blog主页: 落羽的落羽 一、红黑树的概念与规则
红黑树是一种更加特殊的平衡二叉搜索树它在每个节点上增加一个存储位来表示
节点的颜色红色或黑色
并通过几条规则确保树在插入和删除操作后仍然保持平衡。
红黑树有以下四条规则
每个结点不是红色就是黑色根结点是黑色的如果一个结点是红色的则它的两个孩子必须都是黑色的也就是说任意一条路径上不会出现连续的红色结点黑色结点的孩子颜色不做要求对于任意一个结点从结点到这棵树所有空结点的简单路径上均包含相同数量的黑色结点 依靠它的几条规则从同一结点出发红黑树没有一条路径会比其他路径长出2倍因而也是接近平衡的。这是因为由于从根到空结点的每条路径都有相同数量的黑色结点所以极限场景下理论最短路径就是全是黑色结点的路径设长度为bh理论最长路径是一黑一红间隔组成长度就是2bh了。也就是说红黑树中任意一条从根到空结点的路径x都有bh x 2bh确保了红黑树最长路径不超过最短路径的2倍了。
假设N是红黑树中结点数量h是最短路径长度那么2h -1 N 22h -1 推出h约等于logN红黑树增删查改最坏情况也就是走最长路径2*logN时间复杂度还是O(logN)。
这些规则保证了红黑树的平衡性使得树的高度保持在logN级别。相比于AVL树红黑树的平衡结构可以说更加“松散”AVL树严格要求了左右子树高度差不超过1但红黑树只要路径长不超过2倍就行但它们的效率还是相同的水平。 二、红黑树的实现
红黑树的结构 红黑树的基本结构不需要AVL树的平衡因子而需要一个颜色成员:
enum Color
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{pairK, V _kv;RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;Color _col;RBTreeNode(const pairK,V kv):_kv(kv), _left(nullptr), _right(nullptr), _parent(nullptr), _col(RED){ }
};templateclass K,class V
class RBTree
{typedef RBTreeNodeK, V Node;
public:private:Node* _root;
};红黑树的插入 红黑树的插入新结点的过程是这样的
首先按照二叉搜索树的规则找到应插入的位置插入后我们需要判断是否符合红黑树的规则。如果是空树插入新增结点必须是黑色的插入完成如果是非空树插入新增结点必须是红色的因为如果非空树插入了黑色结点就会破坏规则4这条规则是很难维护的。非空树插入红色结点后如果父亲是黑色的则不会破坏任何规则插入完成。非空树插入红色结点后如果父亲是红色的就破坏了规则“红色结点的孩子必须是黑色”此时需要下面进一步分析。 接下来我们具体分析最后一条情况又有几种场景。下面称新增结点为cc的父亲为pp的父亲为gp的兄弟为u。c是红色的p也是红色的那么g一定是黑色的这三者的颜色是确定的所以关键是看u的状态下图中只表示出cpgu结点省略其他子树
场景1
u存在且为红色。这种场景下c保持红色不变使p和u都变成黑色g变为红色。这样处理后就能使包含p或u的路径的黑色结点数量保持一致。 场景2
u存在且为黑色 或 u不存在。u不存在则c一定是新增结点u存在且为黑则c一定不是新增结点而是新增结点插入在了c的子树中通过场景1调整后使c变成了红色。
这两种情况下处理方式是一样的需要旋转变色处理但是旋转变色的方式和AVL树一样仍需分情况讨论
p是g的左c是p的左。以g为旋转点右单旋。然后把p变黑g变红。如图p是g的右c是p的右。以g为旋转点左单旋。然后把p变黑g变红。如图p是g的左c是p的右。**先以p为旋转点左单旋再以g为旋转点右单旋左右双旋。然后把c变黑g变红。**如图p是g的右c是p的左。**先以p为旋转点右单旋再以g为旋转点左单旋右左双旋。然后把c变黑g变红。**如图
红黑树的插入代码实现
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);cur-_col RED;cur-_parent parent;if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}while (parent parent-_col RED){Node* grandfather parent-_parent;//p是g的左的情况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;}//u不存在或存在为黑色else //旋转变色{if (cur parent-_left){RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}//p是g的右的情况else{Node* uncle grandfather-_left;//u存在且为红色//变色if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}//u不存在或存在为黑色else //旋转变色{if (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{RotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;
}红黑树的验证 验证我们的红黑树是否合格也就需要检查是否满足了那四条规则
规则1不用检查因为我们一开始就用了枚举类型赋值规则2检查根结点颜色即可规则3进行前序遍历遇到红色结点就检查它的父结点是不是红色的规则4首先用一个refNum记录最左路径的黑色结点数量进行前序遍历遍历过程中用一个变量blackNum记录到当前结点的黑色结点数量遇到黑色结点就blackNum走到空就计算出了一条路径的黑色结点数量。此时若blackNum与refNum不同则规则4不满足。
bool Check(Node* root, int blackNum, const int refNum)
{if (root nullptr){if (refNum ! blackNum){cout 存在黑色结点数量不相同的路径 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout 存在连续的红色结点 endl;return false;}if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, refNum) Check(root-_right, blackNum, refNum);
}bool IsBalance()
{if (_root nullptr){return true;}if (_root-_col RED){return false;}//参考值refNum记录最左路径的黑色结点数量int refNum 0;Node* cur _root;while (cur){if (cur-_col BLACK){refNum;}cur cur-_left;}return Check(_root, 0, refNum);
}本篇完感谢阅读~
