做地方门户网站怎样,四川住房和城乡建设厅官网安全员,网站备案登记信息,网上国网推广方法目录 00.引入
01.红黑树的性质
02.红黑树的定义
03.红黑树的插入
1.按照二叉搜索树的规则插入新节点
2.检测新节点插入后#xff0c;是否满足红黑树的性质
1.uncle节点存在且为红色
2.uncle节点不存在
3.uncle节点存在且为黑色 04.验证红黑树 00.引入
和AVL树一样是否满足红黑树的性质
1.uncle节点存在且为红色
2.uncle节点不存在
3.uncle节点存在且为黑色 04.验证红黑树 00.引入
和AVL树一样红黑树也是一种自平衡的二叉搜索树。AVL树通过平衡因子调整子树的高度确保树的高度差在 -1 到 1 之间。而红黑树通过在每个节点上增加一个存储位表示节点的颜色可以是RED或BLACK。通过对任何一条从根到叶子的路径上各个节点着色方式的限制红黑树确保没有任何一条路径会是其他路径的两倍以上长因而接近平衡。 01.红黑树的性质
红黑树具有以下几种性质这些性质确保了树的平衡性和高效性
1.节点颜色每个节点要么是红色要么是黑色。
2.根节点颜色根节点始终是黑色。
3.红色节点限制没有两个红色节点可以相连。
4.黑色节点数量从任何节点到其每个叶子节点的所以路径包含相同数量的黑色节点。
5.叶子节点所有的叶子节点此处都表示为NULL节点都是黑色。
其实还有一条潜规则每一个新插入的节点初始都为红色。
为什么以上性质就可以保证最长路径的节点个数不会超过最短路径节点个数的两倍
通过性质1/2/5可知在判断性质4时计算路径上黑色节点的数量不需要考虑头节点以及叶子节点只需要考虑中间节点即可再根据性质3可以列举以下几种情况
1.中间没有黑色节点
路径 黑-黑黑-红-黑。
2.中间只有1个黑色节点
路径 黑-黑-黑黑-红-黑-黑黑-黑-红-黑黑-红-黑-红-黑
3.中间有2个黑色节点
路径 黑-黑-黑-黑黑-红-黑-黑-黑黑-黑-红-黑-黑黑-黑-黑-红-黑 。。。黑-红-黑-红-黑-红-黑
可以看出最短路径就是全黑的最长路径是黑、红相间的。因而我们可以找到规律
假设中间有n个黑色节点
最短路径n2中间节点加上首尾
最长路径n(n1)22n3中间有n个黑色节点最多可以有n1个红色节点
所以最长路径2n3永远比最短路径的2倍2n4小1。
02.红黑树的定义
红黑树的底层结构在代码实现中使用节点结构体和数来表示。节点结构体 保存每个节点的数据、指向左右子节点、父节点的指针、以及平衡因子树类管理插入、删除等操作。
// 节点的颜色
enum Color { RED, BLACK };// 红黑树节点的定义
templateclass T
struct RBTreeNode
{RBTreeNode(const T data T(), Color color RED): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _color(color){}RBTreeNodeT* _pLeft; // 节点的左孩子RBTreeNodeT* _pRight; // 节点的右孩子RBTreeNodeT* _pParent; // 节点的双亲T _data; // 节点的值域Color _color; // 节点的颜色
};在节点的定义中我们将节点默认颜色给成红色这是因为如果定义成黑色的话根据性质4每一次插入节点都需要重新调整树而定义成红色就只需要在父节点也为红色时进行调整一定程度上保证了插入的效率。
03.红黑树的插入
红黑树是在二叉搜索树的基础上加上平衡限制条件的因此红黑树的插入可以分为两步
1.按照二叉搜索树的规则插入新节点 // 在红黑树中插入值为data的节点插入成功返回true否则返回false// 注意为了简单起见本次实现红黑树不存储重复性元素bool Insert(const T data){if (!_pRoot) // 根节点为空直接插入{_pRoot new Node(data);_pRoot-_color BLACK; // 设置根节点为黑色return true;}Node* pParent nullptr;Node* pCur _pRoot;while (pCur){pParent pCur;if (data pCur-_data) // 元素重复不进行插入return false;else if (data pCur-_data) // 大于向右走pCur pCur-_pRight;else // 小于向左走pCur pCur-_pLeft;}pCur new Node(data);// 更新父节点的子节点指针if (data pParent-_data)pParent-_pLeft pCur;elsepParent-_pRight pCur;pCur-_pParent pParent;return true;}
二叉搜索树的插入过程不在赘述详细可跳转这篇博客【C】二叉搜索树。
2.检测新节点插入后是否满足红黑树的性质
因为新插入节点默认为红色因此如果双亲节点是黑色则满足性质不需要调整如果双亲节点为红色违反了性质3需要进行调整调整过程需要进行分类讨论
第一种情况
我们调整红黑树的底层逻辑是通过改变某些节点的颜色使整棵树符合性质看下面这棵树 cur表示新插入节点parent为父节点grandpa为父节点的父节点uncle为grandpa的另一个节点
下面用cpgu分别表示curparentgrandpauncle
此时c和p是连续的红色节点。破坏了性质3那么我直接把p的颜色改成黑色性质3被修复但同时又破坏了性质4于是我把u的颜色也改成黑色这样以g为根节点的这棵树确实被修复了。
但要注意如果g不是根节点呢
此时性质4还是被破坏了为此把g的颜色改成红色
这样就完成了修复。但如果是下面这种情况呢
g的双亲也为红色此时需要继续向上调整。。
所以我们得到了第一种情况
1.uncle节点存在且为红色
a.祖父节点为根 或 祖父的双亲为黑色
只需要修改u和p的颜色即可 b.祖父节点不为根 且 祖父的双亲为红色
此时需要进一步向上调整 将cur的位置换到grandpap、u、g一并转换此时u一定存在如果u不存在则违反了性质4
第二种情况
2.uncle节点不存在
1.单旋的情况 学习过AVL树可以知道对于这样的一棵树我们需要通过旋转的方法调整高度关于旋转的原理可以调整这篇博客【C】AVL树
旋转完成之后我们需要调整颜色此时p成为了这棵树的根节点为了满足条件4我们把p颜色改成黑g颜色改成红 这是左单旋的情况右单旋同理
2.双旋的情况 双旋分为 右左 与 左右 两种情况右左即p是g的右孩子c是p的左孩子。右左情况下我们需要对p进行右单旋在对g进行左单旋最后调整c和g的颜色过程如下 左右的情况同理
3.uncle节点存在且为黑色
a.单旋的情况 此时cur一定不是新插入节点这种情况就是1.b向上调整的后续了此时依旧要用到旋转操作和情况2同理 b.双旋的情况 由此看来情况2和情况3其实可以合并。
下面给出插入以及旋转的完整代码
templateclass T
class RBTree
{typedef RBTreeNodeT Node;
public:RBTree(){_pRoot nullptr;}// 在红黑树中插入值为data的节点插入成功返回true否则返回false// 注意为了简单起见本次实现红黑树不存储重复性元素bool Insert(const T data){if (!_pRoot) // 根节点为空直接插入{_pRoot new Node(data);_pRoot-_color BLACK; // 设置根节点为黑色return true;}Node* pParent nullptr;Node* pCur _pRoot;while (pCur){pParent pCur;if (data pCur-_data) // 元素重复不进行插入return false;else if (data pCur-_data) // 大于向右走pCur pCur-_pRight;else // 小于向左走pCur pCur-_pLeft;}pCur new Node(data);// 更新父节点的子节点指针if (data pParent-_data)pParent-_pLeft pCur;elsepParent-_pRight pCur;pCur-_pParent pParent;while (pParent pParent-_color RED){Node* pGrandpa pParent-_pParent;if (!pGrandpa)pParent-_color BLACK;else {if (pParent pGrandpa-_pRight) {Node* pUncle pGrandpa-_pLeft;// uncle存在且为红if (pUncle pUncle-_color RED){pUncle-_color pParent-_color BLACK;pGrandpa-_color RED;// 继续向上调整pCur pGrandpa;pParent pCur-_pParent;}// uncle不存在或者uncle为黑else{// 右右的情况if (pCur pParent-_pRight){RotateL(pGrandpa);pParent-_color BLACK;pGrandpa-_color RED;}// 右左的情况else{RotateR(pParent);RotateL(pGrandpa);pCur-_color BLACK;pGrandpa-_color RED;}break;}}else // pParent pGrandpa-_pLeft{Node* pUncle pGrandpa-_pRight;// uncle存在且为红if (pUncle pUncle-_color RED){pUncle-_color pParent-_color BLACK;pGrandpa-_color RED;// 继续向上调整pCur pGrandpa;pParent pCur-_pParent;}// uncle不存在或者uncle为黑else{// 左左的情况if (pCur pParent-_pLeft){RotateR(pGrandpa);pParent-_color BLACK;pGrandpa-_color RED;}// 左右的情况else{RotateL(pParent);RotateR(pGrandpa);pCur-_color BLACK;pGrandpa-_color RED;}break;}}}}_pRoot-_color BLACK;return true;}private:// 左单旋void RotateL(Node* pParent){Node* pCur pParent-_pRight;pParent-_pRight pCur-_pLeft; // cur的左孩子作为parent的右孩子if (pCur-_pLeft)pCur-_pLeft-_pParent pParent;if (pParent-_pParent) // parent不是根节点{pCur-_pParent pParent-_pParent;if (pParent-_pParent-_pLeft pParent)pParent-_pParent-_pLeft pCur;elsepParent-_pParent-_pRight pCur;}else // parent是根节点{_pRoot pCur;pCur-_pParent nullptr;}pParent-_pParent pCur;pCur-_pLeft pParent;}// 右单旋void RotateR(Node* pParent){Node* pCur pParent-_pLeft;pParent-_pLeft pCur-_pRight; // cur的右孩子作为parent的左孩子if (pCur-_pRight)pCur-_pRight-_pParent pParent;if (pParent-_pParent) // parent不是根节点{pCur-_pParent pParent-_pParent;if (pParent-_pParent-_pLeft pParent)pParent-_pParent-_pLeft pCur;elsepParent-_pParent-_pRight pCur;}else // parent是根节点{_pRoot pCur;pCur-_pParent nullptr;}pParent-_pParent pCur;pCur-_pRight pParent;}private:Node* _pRoot;
}; 04.验证红黑树
检验上述代码就得从红黑树的5条性质入手性质1、5不需要验证性质2也很容易验证实际上我们主要验证的是性质3没有连续的红色节点以及性质4每条路径上黑色节点数量一致
对于性质4我们可以先记录某一条路径这里选取最左叶节点这条路径的黑色节点数量再遍历每一条路径只要有一条路径上的黑色节点数量与前者不一样就返回false这里选择用递归的方式遍历红黑树。
对于性质3我们需要再遍历的过程中碰到红色节点就验证一下双亲的颜色如果也为红则违反性质返回false
完整代码如下 // 检测红黑树是否为有效的红黑树注意其内部主要依靠_IsValidRBTRee函数检测bool IsValidRBTRee(){if (!_pRoot)return true;if (RED _pRoot-_color)return false;Node* pCur _pRoot;size_t blackcount 0;while (pCur){if (BLACK pCur-_color)blackcount;pCur pCur-_pLeft;}return _IsValidRBTRee(_pRoot, blackcount, 0);}bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack) {if (!pRoot) {// 如果到达叶子节点检查黑色节点数量return pathBlack blackCount;}// 检查当前节点的颜色if (pRoot-_color RED) {// 如果是红色检查父节点是否也是红色if (pRoot-_pParent pRoot-_pParent-_color RED) {return false; // 违反红黑树性质}}// 更新路径上的黑色节点数量if (pRoot-_color BLACK) {pathBlack;}// 递归检查左子树和右子树return _IsValidRBTRee(pRoot-_pLeft, blackCount, pathBlack) _IsValidRBTRee(pRoot-_pRight, blackCount, pathBlack);}
最后我们用一万组包含10个1~100随机数的数组验证红黑树
#includeiostream
using namespace std;
#includeMy_RBTree.h
#includevectorbool test1()
{srand(time(0)); // 初始化随机种子// 生成10000组随机向量for (int i 0; i 10000; i) {RBTreeint BT;vectorint nums;// 每组随机生成10个整数范围为 1 到 100for (int j 0; j 10; j) {nums.push_back(rand() % 100 1);}// 将每个整数插入 B 树中for (const int num : nums) {BT.Insert(num);}// 检查 B 树if (!BT.IsValidRBTRee()) {cout 树不平衡测试失败\n;for (auto it : nums){cout it , ;}cout endl;return 1;}}cout 所有10000组随机树均平衡测试通过\n;
}int main()
{test1();return 0;
}
运行结果 验证通过
附上完整代码
//My_RBTree.h
#pragma once
// 节点的颜色
enum Color { RED, BLACK };// 红黑树节点的定义
templateclass T
struct RBTreeNode
{RBTreeNode(const T data T(), Color color RED): _pLeft(nullptr), _pRight(nullptr), _pParent(nullptr), _data(data), _color(color){}RBTreeNodeT* _pLeft; // 节点的左孩子RBTreeNodeT* _pRight; // 节点的右孩子RBTreeNodeT* _pParent; // 节点的双亲T _data; // 节点的值域Color _color; // 节点的颜色
};templateclass T
class RBTree
{typedef RBTreeNodeT Node;
public:RBTree(){_pRoot nullptr;}// 在红黑树中插入值为data的节点插入成功返回true否则返回false// 注意为了简单起见本次实现红黑树不存储重复性元素bool Insert(const T data){if (!_pRoot) // 根节点为空直接插入{_pRoot new Node(data);_pRoot-_color BLACK; // 设置根节点为黑色return true;}Node* pParent nullptr;Node* pCur _pRoot;while (pCur){pParent pCur;if (data pCur-_data) // 元素重复不进行插入return false;else if (data pCur-_data) // 大于向右走pCur pCur-_pRight;else // 小于向左走pCur pCur-_pLeft;}pCur new Node(data);// 更新父节点的子节点指针if (data pParent-_data)pParent-_pLeft pCur;elsepParent-_pRight pCur;pCur-_pParent pParent;while (pParent pParent-_color RED){Node* pGrandpa pParent-_pParent;if (!pGrandpa)pParent-_color BLACK;else {if (pParent pGrandpa-_pRight) {Node* pUncle pGrandpa-_pLeft;// uncle存在且为红if (pUncle pUncle-_color RED){pUncle-_color pParent-_color BLACK;pGrandpa-_color RED;// 继续向上调整pCur pGrandpa;pParent pCur-_pParent;}// uncle不存在或者uncle为黑else{// 右右的情况if (pCur pParent-_pRight){RotateL(pGrandpa);pParent-_color BLACK;pGrandpa-_color RED;}// 右左的情况else{RotateR(pParent);RotateL(pGrandpa);pCur-_color BLACK;pGrandpa-_color RED;}break;}}else // pParent pGrandpa-_pLeft{Node* pUncle pGrandpa-_pRight;// uncle存在且为红if (pUncle pUncle-_color RED){pUncle-_color pParent-_color BLACK;pGrandpa-_color RED;// 继续向上调整pCur pGrandpa;pParent pCur-_pParent;}// uncle不存在或者uncle为黑else{// 左左的情况if (pCur pParent-_pLeft){RotateR(pGrandpa);pParent-_color BLACK;pGrandpa-_color RED;}// 左右的情况else{RotateL(pParent);RotateR(pGrandpa);pCur-_color BLACK;pGrandpa-_color RED;}break;}}}}_pRoot-_color BLACK;return true;}// 检测红黑树中是否存在值为data的节点存在返回该节点的地址否则返回nullptrNode* Find(const T data){Node* pCur _pRoot;while (pCur){if (data pCur-_data)return pCur;if (data pCur-_data)pCur pCur-_pRight;elsepCur pCur-_pLeft;}return nullptr;}// 检测红黑树是否为有效的红黑树注意其内部主要依靠_IsValidRBTRee函数检测bool IsValidRBTRee(){if (!_pRoot)return true;if (RED _pRoot-_color)return false;Node* pCur _pRoot;size_t blackcount 0;while (pCur){if (BLACK pCur-_color)blackcount;pCur pCur-_pLeft;}return _IsValidRBTRee(_pRoot, blackcount, 0);}private:bool _IsValidRBTRee(Node* pRoot, size_t blackCount, size_t pathBlack) {if (!pRoot) {// 如果到达叶子节点检查黑色节点数量return pathBlack blackCount;}// 检查当前节点的颜色if (pRoot-_color RED) {// 如果是红色检查父节点是否也是红色if (pRoot-_pParent pRoot-_pParent-_color RED) {return false; // 违反红黑树性质}}// 更新路径上的黑色节点数量if (pRoot-_color BLACK) {pathBlack;}// 递归检查左子树和右子树return _IsValidRBTRee(pRoot-_pLeft, blackCount, pathBlack) _IsValidRBTRee(pRoot-_pRight, blackCount, pathBlack);}// 左单旋void RotateL(Node* pParent){Node* pCur pParent-_pRight;pParent-_pRight pCur-_pLeft; // cur的左孩子作为parent的右孩子if (pCur-_pLeft)pCur-_pLeft-_pParent pParent;if (pParent-_pParent) // parent不是根节点{pCur-_pParent pParent-_pParent;if (pParent-_pParent-_pLeft pParent)pParent-_pParent-_pLeft pCur;elsepParent-_pParent-_pRight pCur;}else // parent是根节点{_pRoot pCur;pCur-_pParent nullptr;}pParent-_pParent pCur;pCur-_pLeft pParent;}// 右单旋void RotateR(Node* pParent){Node* pCur pParent-_pLeft;pParent-_pLeft pCur-_pRight; // cur的右孩子作为parent的左孩子if (pCur-_pRight)pCur-_pRight-_pParent pParent;if (pParent-_pParent) // parent不是根节点{pCur-_pParent pParent-_pParent;if (pParent-_pParent-_pLeft pParent)pParent-_pParent-_pLeft pCur;elsepParent-_pParent-_pRight pCur;}else // parent是根节点{_pRoot pCur;pCur-_pParent nullptr;}pParent-_pParent pCur;pCur-_pRight pParent;}private:Node* _pRoot;
}; //test.cpp
#define _CRT_SECURE_NO_WARNINGS 1#includeiostreamusing namespace std;#includeMy_RBTree.h#includevectorbool test1(){srand(time(0)); // 初始化随机种子// 生成10000组随机向量for (int i 0; i 10000; i) {RBTreeint BT;vectorint nums;// 每组随机生成10个整数范围为 1 到 100for (int j 0; j 10; j) {nums.push_back(rand() % 100 1);}// 将每个整数插入 B 树中for (const int num : nums) {BT.Insert(num);}// 检查 B 树if (!BT.IsValidRBTRee()) {cout 树不平衡测试失败\n;for (auto it : nums){cout it , ;}cout endl;return 1;}}cout 所有10000组随机树均平衡测试通过\n;}void test2(){RBTreeint BT1;vectorint v1 { 70,25,97,18,51,85 };for (auto it : v1){BT1.Insert(it);}cout BT1.IsValidRBTRee() endl;}int main(){test1();return 0;}
以上就是红黑树的详解与模拟实现过程欢迎在评论区留言码文不易觉得这篇博客对你有帮助的可以点赞收藏关注支持一波~
