在网站怎么做代销,discuz模板下载,网站html动态效果代码,网站建设运用软件目录
1.红黑树的概念
2.红黑树的性质
3.红黑树节点的定义 4.红黑树的插入操作 5.数据测试 1.红黑树的概念 红黑树#xff0c;是一种二叉搜索树#xff0c;但在每个结点上增加一个存储位表示结点的颜色#xff0c;可以是Red或Black。 通过对任何一条从根到叶子的路径上各个…目录
1.红黑树的概念
2.红黑树的性质
3.红黑树节点的定义 4.红黑树的插入操作 5.数据测试 1.红黑树的概念 红黑树是一种二叉搜索树但在每个结点上增加一个存储位表示结点的颜色可以是Red或Black。 通过对任何一条从根到叶子的路径上各个结点着色方式的限制红黑树确保没有一条路径会比其他路径长出俩倍因而是接近平衡的 2.红黑树的性质 1. 每个结点不是红色就是黑色 2. 根节点是黑色的 3. 如果一个节点是红色的则它的两个孩子结点是黑色的 4. 对于每个结点从该结点到其所有后代叶结点的简单路径上均 包含相同数目的黑色结点 5. 每个叶子结点都是黑色的(此处的叶子结点指的是空结点) 思考为什么满足上面的性质红黑树就能保证其最长路径中节点个数不会超过最短路径节点个数的两倍 最短路径由于性质4规定从任意节点到叶子节点的所有路径都包含相同数量的黑色节点因此由纯黑色节点组成的路径将是最短路径。这是因为黑色节点是每条路径上必须包含的而且没有其他颜色的节点可以“缩短”这条路径。最长路径最长路径将是由红色和黑色节点交替组成的路径。由于性质3禁止了连续红色节点的出现因此最长路径将是黑色节点与红色节点交替出现的情况。由于每条路径上的黑色节点数量相同性质4红色节点的插入不会增加路径上黑色节点的数量而是增加了路径的总长度。路径长度比较在最长路径中每两个黑色节点之间可能插入一个红色节点这使得最长路径的长度大致为最短路径纯黑色节点的两倍。这是因为在保持黑色节点数量相同的情况下红色节点的插入只是在黑色节点之间增加了额外的节点而这些额外的红色节点最多只能使路径长度加倍。 3.红黑树节点的定义 enum Colour
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Colour _col;RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;private:Node* _root nullptr;
}; 成员变量 _left、_right 和 _parent 分别指向节点的左子节点、右子节点和父节点。_kv 是一个 pairK, V存储节点的键和值。_col 表示节点的颜色可以是 RED 或 BLACK。构造函数 接收一个 pairK, V 作为参数初始化节点的键值对并将节点的颜色初始化为 RED。其他指针成员初始化为 nullptr。 4.红黑树的插入操作 我们在进行插入操作时新节点默认是红色。红色节点的插入可能导致红黑树的性质被破坏但通过将新节点设为红色我们可以更容易地通过颜色变换和旋转来恢复平衡。具体来说红色节点的插入只会影响局部区域的平衡而黑色节点的插入则可能影响整棵树的平衡。 因为新节点的默认颜色是红色因此如果其双亲节点的颜色是黑色没有违反红黑树任何 性质则不需要调整但当新插入节点的双亲节点颜色为红色时就违反了性质三不能有连 在一起的红色节点此时需要对红黑树分情况来讨论约定:cur为当前节点p为父节点g为祖父节点u为叔叔节点情况一: cur为红p为红g为黑u存在且为红 情况二: cur为红p为红g为黑u不存在/u存在且为黑 p为g的左孩子cur为p的左孩子则进行右单旋转相反 p为g的右孩子cur为p的右孩子则进行左单旋转 p、g变色--p变黑g变红 情况三: cur为红p为红g为黑u不存在/u存在且为黑双旋 p为g的左孩子cur为p的右孩子则针对p做左单旋转相反 p为g的右孩子cur为p的左孩子则针对p做右单旋转则转换成了情况2 针对每种情况进行相应的处理即可。 据以上情况写代码 }cur new Node(kv);cur-_col RED; // 新增节点给红色if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;// parent的颜色是黑色也结束while (parent parent-_col RED){// 关键看叔叔Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;// 叔叔存在且为红-》变色即可if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}else // 叔叔不存在或者存在且为黑{if (cur parent-_left){// g // p u// c RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g // p u// c RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else{Node* uncle grandfather-_left;// 叔叔存在且为红-》变色即可if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}else // 叔叔不存在或者存在且为黑{// 情况二叔叔不存在或者存在且为黑// 旋转变色// g// u p// cif (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;} 代码解释 初始化新节点: 创建一个新的节点cur并为其分配键值对kv。将新节点的颜色设置为红色RED因为在红黑树的规则中新插入的节点默认为红色。根据键值对的大小将新节点插入到其父节点的左子树或右子树。设置新节点的父节点。调整红黑树以保持其性质: 如果父节点是黑色的那么不需要进行任何调整因为插入红色节点不会违反红黑树的性质。如果父节点是红色的那么需要进行调整以恢复红黑树的性质。这是通过一个循环来完成的该循环会持续进行直到父节点不再是红色或者已经进行了必要的调整。调整过程: 首先根据父节点是其祖父节点的左子节点还是右子节点分为两种情况处理。在每种情况下都会考虑叔叔节点的颜色和存在性。如果叔叔节点是红色的那么可以通过重新着色父节点、叔叔节点和祖父节点来恢复红黑树的性质然后将当前节点移动到祖父节点并更新父节点为祖父节点的父节点继续向上调整。如果叔叔节点是黑色的或者不存在那么需要进行旋转操作来恢复红黑树的性质。根据当前节点是父节点的左子节点还是右子节点进行相应的旋转操作并重新着色节点。结束调整: 一旦退出调整循环将根节点着色为黑色以确保红黑树的根节点总是黑色的性质。 以下是旋转逻辑的代码示例 void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* ppNode parent-_parent;parent-_parent subL;if (parent _root){_root subL;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* ppNode parent-_parent;parent-_parent subR;if (parent _root){_root subR;_root-_parent nullptr;}else{if (ppNode-_right parent){ppNode-_right subR;}else{ppNode-_left subR;}subR-_parent ppNode;}} 5.数据测试 为了更好的测试数据我们需要写一个检查一棵红黑树是否满足红黑树的性质以确保红黑树的正确性 bool Check(Node* root, int blackNum, const int refNum){if (root nullptr){//cout blackNum endl;if (refNum ! blackNum){cout 存在黑色节点的数量不相等的路径 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout root-_kv.first 存在连续的红色节点 endl;return false;}if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, refNum) Check(root-_right, blackNum, refNum);} 代码解释 空节点检查 如果root是空指针即已经到达了一个叶节点函数会检查当前路径上的黑色节点数量blackNum是否与参考数量refNum相等。如果不相等会输出错误信息并返回false表示检查失败。如果相等则返回true表示这条路径满足红黑树的性质。 连续红色节点检查 如果当前节点的颜色是红色并且其父节点的颜色也是红色那么会输出错误信息并返回false。因为红黑树的一个关键性质是不允许有两个连续的红色节点。 黑色节点计数 如果当前节点的颜色是黑色blackNum会递增以记录从根节点到当前节点的路径上黑色节点的数量。 递归检查 函数会递归地对左子树和右子树进行相同的检查。如果左右子树都满足红黑树的性质即递归调用都返回true则整个子树满足性质函数返回true。如果有任何一个子树不满足性质函数返回false。 下面是红黑树的完整代码 enum Colour
{RED,BLACK
};templateclass K, class V
struct RBTreeNode
{RBTreeNodeK, V* _left;RBTreeNodeK, V* _right;RBTreeNodeK, V* _parent;pairK, V _kv;Colour _col;RBTreeNode(const pairK, V kv):_left(nullptr), _right(nullptr), _parent(nullptr), _kv(kv), _col(RED){}
};templateclass K, class V
class RBTree
{typedef RBTreeNodeK, V Node;
public: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; // 新增节点给红色if (parent-_kv.first kv.first){parent-_right cur;}else{parent-_left cur;}cur-_parent parent;// parent的颜色是黑色也结束while (parent parent-_col RED){// 关键看叔叔Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;// 叔叔存在且为红-》变色即可if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}else // 叔叔不存在或者存在且为黑{if (cur parent-_left){// g // p u// c RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g // p u// c RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else{Node* uncle grandfather-_left;// 叔叔存在且为红-》变色即可if (uncle uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;// 继续往上处理cur grandfather;parent cur-_parent;}else // 叔叔不存在或者存在且为黑{// 情况二叔叔不存在或者存在且为黑// 旋转变色// g// u p// cif (cur parent-_right){RotateL(grandfather);parent-_col BLACK;grandfather-_col RED;}else{// g// u p// cRotateR(parent);RotateL(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}}_root-_col BLACK;return true;}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;parent-_left subLR;if (subLR)subLR-_parent parent;subL-_right parent;Node* ppNode parent-_parent;parent-_parent subL;if (parent _root){_root subL;_root-_parent nullptr;}else{if (ppNode-_left parent){ppNode-_left subL;}else{ppNode-_right subL;}subL-_parent ppNode;}}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;parent-_right subRL;if (subRL)subRL-_parent parent;subR-_left parent;Node* ppNode parent-_parent;parent-_parent subR;if (parent _root){_root subR;_root-_parent nullptr;}else{if (ppNode-_right parent){ppNode-_right subR;}else{ppNode-_left subR;}subR-_parent ppNode;}}void InOrder(){_InOrder(_root);cout endl;}bool IsBalance(){if (_root-_col RED){return false;}int refNum 0;Node* cur _root;while (cur){if (cur-_col BLACK){refNum;}cur cur-_left;}return Check(_root, 0, refNum);}private:bool Check(Node* root, int blackNum, const int refNum){if (root nullptr){//cout blackNum endl;if (refNum ! blackNum){cout 存在黑色节点的数量不相等的路径 endl;return false;}return true;}if (root-_col RED root-_parent-_col RED){cout root-_kv.first 存在连续的红色节点 endl;return false;}if (root-_col BLACK){blackNum;}return Check(root-_left, blackNum, refNum) Check(root-_right, blackNum, refNum);}void _InOrder(Node* root){if (root nullptr){return;}_InOrder(root-_left);cout root-_kv.first : root-_kv.second endl;_InOrder(root-_right);}private:Node* _root nullptr;
};数据测试 void TestRBTree1()
{int a[] { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14,8, 3, 1, 10, 6, 4, 7, 14, 13 };RBTreeint, int t1;for (auto e : a){if (e 10){int i 0;}t1.Insert({ e,e });cout Insert: e - t1.IsBalance() endl;}t1.InOrder();cout t1.IsBalance() endl;
} 符合预期代码正确。
