广东网站建设多少钱,zencart 网站换域名,php做简单网站 多久,温州建网站哪家好个人主页 #xff1a; 个人主页 个人专栏 #xff1a; 《数据结构》 《C语言》《C》《Linux》 文章目录 一、红黑树二、红黑树的插入三、代码实现总结 一、红黑树
红黑树的概念#xff1a; 红黑树是一颗二叉搜索树#xff0c;但在每个节点上增加一个存储位表示节点的颜色 个人主页 个人专栏 《数据结构》 《C语言》《C》《Linux》 文章目录 一、红黑树二、红黑树的插入三、代码实现总结 一、红黑树
红黑树的概念 红黑树是一颗二叉搜索树但在每个节点上增加一个存储位表示节点的颜色该节点颜色不是红色就是黑色。通过对每一条从根节点到叶子结点路径上各个节点颜色的控制确保没有一条路径会比其它路径长出两倍因此红黑树是接近平衡。 那红黑树是通过哪些规则来对节点颜色进行控制 每个节点不是红色就是黑色 根节点是黑色 如果一个节点是红色则其两个子节点是黑色(不能有连续的红色节点) 对于每个节点从该节点到其所以叶子结点的路径上其黑色节点的数目相同 每个叶子结点都是黑色的(此处的叶子结点是空节点(NIL)方便我们计算路径的个数) 注意上述中的路径是从某一节点到NIL节点。如上图8节点到叶子结点就有5条路径每条路径都有一个黑色节点。
那为什么遵循这5条规则红黑树就能保证其最长路径中节点的个数不会超过最短路径节点个数的两倍 我们假设从根节点到叶子结点的黑色节点数为n那么最短路径不就是连续的黑色节点最短路径的节点数为n那么最长路径不就是红黑相间最长路径的节点数为2n。所以红黑树保证其最长路径中节点的个数不会超过最短路径节点个数的两倍。 下面是红黑树节点的定义。
enum
{RED,BLACK
};templateclass T
struct RBTreeNode
{RBTreeNode(T data T()):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;T _data;int _col;
};该定义中我们默认将新节点颜色定义为红色这样我们插入节点时需要维护规则的成本就少。如我们新插入一个红色节点那么有可能会违背规则3(当其父节点是红色时有连续红色节点)这时我们可能需要一些变色和旋转来维持规则但如果我们插入节点是黑色那么我们一定违背4(每条路径上黑色节点数相同)这时我们可能需要对整个数进行操作。
二、红黑树的插入
红黑树也是一个二叉搜索树插入新节点与二叉搜索树的操作一样如果新插入节点比该节点大新插入节点就去该节点的右子树反之去该节点的左子树。
if (_root nullptr){_root new Node(data);_root-_col BLACK;return true;}Node* parent nullptr;Node* cur _root;while (cur ! nullptr){parent cur;if (cur-_data data){cur cur-_left;}else if(cur-_data data){cur cur-_right;}else // cur-_data data{return false;}}cur new Node(data);cur-_parent parent;if (cur-_data parent-_data){parent-_right cur;}else{parent-_left cur;}这里我们主要分析新插入节点后红黑树的情况和处理。对于旋转这里并不会详细解析。对于旋转的详细解析在我的AVL树一文中。数据结构AVLTree的插入和删除的实现
在分析情况前我们先了解几个节点的含义方便后续的理解。 接下来的所有情况都与这四个节点有关。
因为我们新插入的节点是红色如果新插入节点的父节点是黑色那么红黑树的规则未被破坏。如果新插入节点的父节点是红色那么就有连续的红色节点。这是我们就要分情况讨论。 情况1. cur为红色parent为红色grandfather为黑色uncle为红色 也就是如下图所示 这种情况是最简单的情况我们只需要将parent 与 uncle的颜色变成黑色(解决连续红色节点)再将grandfather的颜色变成红色(防止经过grandfather路径的黑色节点数1) 但就如上图所示因为我们将grandfather的颜色变成红色如果grandfather的父节点的颜色也是红色这时我们依旧有连续的红色节点我们仍需对grandfather进行处理。 我们重复变色过程 这时grandfather没有父节点就可以停止了但此时grandfather作为根节点为红色我们需要特殊处理一下即可。这样对于该插入新节点的情况一就完成了。 下面是总结的模型 对于这种curparentuncle为红色grandfather为黑色的情况我们只需让parentuncle变成红色grandfather变成黑色接着需要检查grandfather的父节点是否是红色如果是红色重复上述操作。如果是黑色就可以结束了。 情况2cur为红色parent为红色grandfather为黑色uncle不存在或uncle存在且为黑色 这时情况1 的处理就行不通了因为uncle要么不存在要么本身就为黑色如果将grandfather变成红色那么经过grandfather的路径的黑色节点数就-1。所以我们要采取旋转变色。 因为cur在parent的右侧parent在grandfather的右侧成直线。所以我们对grandfather左单旋接着将parent的颜色变成黑色grandfather的颜色变成红色(防止经过grandfather的路径的黑色节点数1)又因为parent作为新的根节点为黑色所以我们不需要去检查parent的父节点的颜色。(虽然我们也可以只将cur变为黑色但这样我们就需要检查parent父节点的颜色) 那如果我们新增5节点要怎么处理 此时我们也需要旋转变色但我们要双旋。 如上图我们要先对parent左单旋使grandfathercurparent在同一侧接着使grandfather左单旋cur变为黑色grandfather变成红色。 如果parent在grandfather的左侧情况与上述情况类似只需要改变旋转方向即可。 下面是总结的模型 单旋 双旋 while (parent ! nullptr parent-_col ! BLACK){Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;if (uncle ! nullptr uncle-_col RED) // uncle存在且为红色{parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else if (uncle nullptr || uncle-_col BLACK) // uncle不存在 或 umcle存在且为黑{if (cur parent-_left) // 同方向{RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else // cur parent-_right 不同方向{RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else // parent grandfather-_right{Node* uncle grandfather-_left;if (uncle ! nullptr uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else if (uncle nullptr || uncle-_col BLACK){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; //特殊处理保证根节点是黑色则此红黑树的插入就完成了。
三、代码实现
RBTree.h 文件是红黑树插入的实现 test.cpp 文件是测试用例
// RBTree.h 文件
#pragma onceenum
{RED,BLACK
};templateclass T
struct RBTreeNode
{RBTreeNode(T data T()):_left(nullptr),_right(nullptr),_parent(nullptr),_data(data),_col(RED){}RBTreeNode* _left;RBTreeNode* _right;RBTreeNode* _parent;T _data;int _col;
};templateclass T
class RBTree
{typedef RBTreeNodeT Node;
public:RBTree():_root(nullptr){}bool insert(const T data){if (_root nullptr){_root new Node(data);_root-_col BLACK;return true;}Node* parent nullptr;Node* cur _root;while (cur ! nullptr){parent cur;if (cur-_data data){cur cur-_left;}else if(cur-_data data){cur cur-_right;}else // cur-_data data{return false;}}cur new Node(data);cur-_parent parent;if (cur-_data parent-_data){parent-_right cur;}else{parent-_left cur;}while (parent ! nullptr parent-_col ! BLACK){Node* grandfather parent-_parent;if (parent grandfather-_left){Node* uncle grandfather-_right;if (uncle ! nullptr uncle-_col RED) // uncle存在且为红色{parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else if (uncle nullptr || uncle-_col BLACK) // uncle不存在 或 umcle存在且为黑{if (cur parent-_left) // 同方向{RotateR(grandfather);parent-_col BLACK;grandfather-_col RED;}else // cur parent-_right 不同方向{RotateL(parent);RotateR(grandfather);cur-_col BLACK;grandfather-_col RED;}break;}}else // parent grandfather-_right{Node* uncle grandfather-_left;if (uncle ! nullptr uncle-_col RED){parent-_col uncle-_col BLACK;grandfather-_col RED;cur grandfather;parent cur-_parent;}else if (uncle nullptr || uncle-_col BLACK){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;}// 读取红黑树最左侧节点Node* leftMost(){if (_root nullptr){return nullptr;}Node* cur _root;while (cur-_left ! nullptr){cur cur-_left;}return cur;}// 读取红黑树最右侧节点Node* rightMost(){if (_root nullptr){return nullptr;}Node* cur _root;while (cur-_right ! nullptr){cur cur-_right;}return cur;}bool isValidRBTree(){if (_root-_col RED){return false;}// 找最左边的黑色节点数作为标准比较int pathBlack 0;Node* cur _root;while (cur ! nullptr){if (cur-_col BLACK){pathBlack;}cur cur-_left;}return _isValidRBTree(_root, 0, pathBlack);}bool _isValidRBTree(Node* root, int blackCount, int pathBlack){if (root nullptr){if (blackCount pathBlack)return true;elsereturn false;}if (root-_col RED root-_parent ! nullptr root-_parent-_col RED){cout 有连续的红色节点 endl;return false;}if (root-_col BLACK){blackCount;}return _isValidRBTree(root-_left, blackCount, pathBlack) _isValidRBTree(root-_right, blackCount, pathBlack);}void RotateR(Node* parent){Node* subL parent-_left;Node* subLR subL-_right;Node* pparent parent-_parent;parent-_left subLR;subL-_right parent;parent-_parent subL;if (subLR ! nullptr){subLR-_parent parent;}if (pparent nullptr){_root subL;subL-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subL;}else{pparent-_right subL;}subL-_parent pparent;}}void RotateL(Node* parent){Node* subR parent-_right;Node* subRL subR-_left;Node* pparent parent-_parent;parent-_right subRL;subR-_left parent;parent-_parent subR;if (subRL ! nullptr){subRL-_parent parent;}if (pparent nullptr){_root subR;subR-_parent nullptr;}else{if (pparent-_left parent){pparent-_left subR;}else{pparent-_right subR;}subR-_parent pparent;}}private:Node* _root;
}; //test.cpp 文件
#include iostream
#include vectorusing namespace std;
#include RBTree.h#define N 10000000void test1()
{vectorint nums(N);srand((unsigned int)time(0));for (int i 0; i N; i){nums[i] rand() i;//cout nums[i] endl;}RBTreeint tree;for (auto val : nums){if (val 11478){int i 0;i;}tree.insert(val);//cout val - tree.isValidRBTree() endl;}cout tree.isValidRBTree() endl;
}int main()
{test1();return 0;
}总结
以上就是我对于红黑树插入实现的总结。感谢支持
