红黑树

树树: 数据结构中是以二叉堆的模式呈现的如果从链表的观点登程,相当于是放宽了有序的的要求容许两个不同地位的元素有相等的序对于序为n的节点来说,能够指向多个序为n+1的节点: 相应的后者称为前者的孩子前者称为后者的父节点最大的序即为树的高度 0节点的左右两个节点别离为0节点的左子节点和右子节点0节点也是这两个子节点的父节点在一个树中,只有0节点没有父节点.这个节点叫做根节点二叉搜寻树二叉搜寻树: 父节点大于或者等于左子节点及所有子节点父节点小于或者等于右子节点及所有子节点初始化要在二叉搜寻树中查问任意一个值: 最坏的状况就是查问到最上面的节点进行比拟的次数为树的高度 因为这是二叉树,若树的元素个数为n,则现实状况下树的高度不大于log~2~n二叉搜寻树中,每个父节点最多子节点有两个子节点树中任意节点有三个指针: 别离指向父节点,左子节点和右子节点.其中根节点没有父节点 typedef struct TREENODE{ struct TREENODE *father; struct TREENODE *left; struct TREENODE *right; int value;}tNode;在一个二叉搜寻树中,插入新节点: 比拟新节点与以后节点的值如果大于以后节点,则比拟新节点与以后节点右子节点的值如果小于以后节点,则比拟新节点与以后左子节点的值如果下一个将要比拟的节点不存在,就将新节点插入进来 void insertNode(tNode* root, int val) {tNode* new = (tNode*)malloc(sizeof(tNode));new -> value = val;new -> left = NULL;new -> right = NULL;while (true) { if (root -> value < val) if (root -> right != NULL) root = root -> right; else { // 右子节点不存在,则新节点成为右子节点 new -> father = root; root -> right = new; return; // 实现赋值之后函数完结 } else if (root -> !=NULL) root = root -> left else { new -> father = root; root -> left = new; return; }}}生成二叉搜寻树之后,能够将二叉搜寻树打印进去,查看生成的二叉搜寻树是否正确 ...

花了好几天的业余时间，看文章，总算是用C实现了一遍红黑树，次要还是本人C语言程度不够高，调试断点节约了不少工夫，闲话少说 1. 红黑树结构体//这里偷懒就应0代表彩色，1代表红色了typedef struct RBTreeNode { int data; //数据域 int color; //0彩色 1红色 struct RBTreeNode *parent;//父亲结点 struct RBTreeNode *left; //左子结点 struct RBTreeNode *right; //右子结点} RBTreeNode;2. 前序遍历//这里打印了节点的色彩和父节点void preOrderTraverse(RBTreeNode *root){ if (root != NULL) { if (root->parent != NULL) { printf("%d color: %d parent:%d\n", root->data, root->color, root->parent->data); }else{ printf("%d color: %d\n", root->data, root->color); } preOrderTraverse(root->left); preOrderTraverse(root->right); }}3.1 左旋跟AVL树差不多，多了parent相干的操作 /** * 左旋 * parent parent * 8 12 * 4 12 8 50 * 9 50 => 4 9 70 * 70 */RBTreeNode *left_rotation(RBTreeNode *root){ struct RBTreeNode *new_root; new_root = root->right; root->right = new_root->left; //将9的父亲设置为老的root 即8 if (new_root->left != NULL) { new_root->left->parent = root; } //新root的parent即老parent new_root->parent = root->parent; //而后解决老root的parent if (root->parent == NULL) { //老root是根节点 new_root->parent = NULL; }else{ //判断父亲左右 if (new_root->parent->left == root) { new_root->parent->left = new_root; }else{ new_root->parent->right = new_root; } } root->parent = new_root; new_root->left = root; return new_root;}3.2 右旋/** * 右旋 * 8 4 * 4 12 2 8 * 2 6 => 1 6 12 * 1 */RBTreeNode *right_rotation(RBTreeNode *root){ struct RBTreeNode *new_root; new_root = root->left; root->left = new_root->right; //将6的父亲设置为老的root 即8 if (new_root->right != NULL) { new_root->right->parent = root; } //新root的parent即老parent new_root->parent = root->parent; //而后解决老root的parent if (root->parent == NULL) { //老root是根节点 new_root->parent = NULL; }else{ //判断父亲左右 if (new_root->parent->left == root) { new_root->parent->left = new_root; }else{ new_root->parent->right = new_root; } } new_root->right = root; root->parent = new_root; // printf("***本人right_rotation***: \n"); // printfNode(new_root); // printf("***左***: \n"); // printfNode(new_root->left); // printf("***右***: \n"); // printfNode(new_root->right); return new_root;}3.3 代码图解/** * 1.插入的只有一个根节点 * * 8(R) => 8(B) * * 2.1父节点是彩色，啥也不必干 * 8(B) * / => 不变 * 4(R) * * 2.2 父节点是红色,祖父肯定是彩色啦，看叔叔是啥色彩 * * 2.2.1 父节点是祖父节点的左节点 * * 2.2.1.1如果叔叔也是红色 * 将父节点,叔节点设为彩色,将祖父节点设为红色,将祖父节点设为“以后节点”(红色节点)；即，之后递归持续对“以后节点”进行操作 * * 8(B) 8(R) 8(B) * / \ / \ / \ * 4(R) 12(R) => 4(B) 12(B) => 4(B) 12(B) * / / / * 2(R) 2(R) 2(R) * * 2.2.1.2如果叔叔不存在或是彩色 * 2.2.1.2.1新节点在左子树 * 父节点设为彩色,将祖父节点设为红色，对祖父节点右旋 * * 8(B) 8(R) 8(B) * / \ 着色 / \ 对4右旋 / \ * 4(B) 12(B) => 4(R) 12(B) => 2(B) 12(B) * / / / \ * 2(R) 2(B) 1(R) 4(R) * / / * 1(R) 1(R) * * 2.2.1.2.2新节点在右子树 * root与父节点替换 并把父节点设为新root的左节点,即转化为2.2.1.2.1，解决如上 * * 8(B) 8(B) 8(B) 8(B) * / \ 替换 / \ 着色 / \ 对4右旋 / \ * 4(B) 12(B) => 4(B) 12(B) => 4(R) 12(B) => 3(B) 12(B) * / / / / \ * 2(R) 3(R) 3(B) 2(R) 4(R) * \ / / * 3(R) 2(R) 2(R) * * * * 2.2.2 父节点是祖父节点的右节点 * 2.2.2.1如果叔叔也是红色 * 将父节点,叔节点设为彩色,将祖父节点设为红色,将祖父节点设为“以后节点”(红色节点)；即，之后递归持续对“以后节点”进行操作 * * 8(B) 8(R) 8(B) * / \ / \ / \ * 4(R) 12(R) => 4(B) 12(B) => 4(B) 12(B) * \ \ \ * 20(R) 20(R) 20(R) * * 2.2.2.2如果叔叔不存在或是彩色(这里的绘图简化些，其实都一样的) * 2.2.2.2.1新节点在左子树 * root与父节点替换 并把父节点设为新root的右节点,即转化为2.2.2.2.2 * 8(B) 8(B) 8(R) 10(B) * \ 替换 \ 着色 \ 对8右旋 / \ * 12(R) => 10(R) => 10(B) => 8(R) 12(R) * / \ \ * 10(R) 12(R) 12(R) * * 2.2.2.2.2新节点在右子树 * 将父节点设为彩色 将祖父节点设为红色 左旋 * * 8(B) 8(R) 12(B) * \ 着色 \ 对8左旋 / \ * 12(B) => 12(B) => 8(R) 20(R) * \ \ * 20(R) 20(R) * * */4. 自均衡RBTreeNode *rebalance3(RBTreeNode *root, RBTreeNode *rootNode)//返回新的根节点{ //1 插入根节点,只需置黑即可 if (root->parent == NULL) { root->color = 0; } //2 有父节点 if (root->parent != NULL) { //2.1 父节点是彩色，啥也不必干 if (root->parent->color == 0) { //do nothing }else{ //2.2 父节点是红色,祖父肯定是彩色啦，看叔叔是啥色彩 RBTreeNode *parent, *gparent, *uncle; parent = root->parent; gparent = root->parent->parent; int return_flag = 0; if (gparent == rootNode) { return_flag = 1; } //先判断父节点是祖父节点的左节点还是右节点，即叔叔节点是啥 //2.2.1 父节点是祖父节点的左节点 if (parent == gparent->left) { uncle = gparent->right; //2.2.1.1如果叔叔也是红色 if (uncle != NULL && uncle->color == 1) { //1.将父节点设为彩色 parent->color = 0; //2.将叔节点设为彩色 uncle->color = 0; //3.将祖父节点设为红色 gparent->color = 1; //4.将祖父节点设为“以后节点”(红色节点)；即，之后持续对“以后节点”进行操作 return rebalance3(gparent, rootNode); }else{ //2.2.1.2如果叔叔彩色 或不存在 //2.2.1.2.1 root是左节点 if (root == parent->left) { //1.将父节点设为彩色 parent->color = 0; //2.将祖父节点设为红色 gparent->color = 1; gparent = right_rotation(gparent); }else{ //2.2.1.2.2 root是右节点 //1.root与父节点替换 并把父节点设为新root的左节点,即转化为2.2.1.2.1 gparent->left = root; root->parent = gparent; root->left = parent; parent->parent = root; parent->right = NULL; return rebalance3(parent, rootNode); } } }else{ //2.2.2 父节点是祖父节点的右节点 uncle = gparent->left; //2.2.2.1如果叔叔也是红色 if (uncle != NULL && uncle->color == 1) { //1.将父节点设为彩色 parent->color = 0; //2.将叔节点设为彩色 uncle->color = 0; //3.将祖父节点设为红色 gparent->color = 1; //4.将祖父节点设为“以后节点”(红色节点)；即，之后持续对“以后节点”进行操作 return rebalance3(gparent, rootNode); }else{ //2.2.2.2如果叔叔彩色 或不存在 //2.2.2.2.1 root是左节点 if (root == parent->left) { //1.root与父节点替换 并把父节点设为新root的左节点,即转化为2.2.2.2.2 gparent->right = root; root->parent = gparent; root->right = parent; parent->parent = root; parent->left = NULL; return rebalance3(parent, rootNode); }else{ //2.2.2.2.2 root是右节点 //1.将父节点设为彩色 parent->color = 0; //2.将祖父节点设为红色 gparent->color = 1; gparent = left_rotation(gparent); } } } if (return_flag == 1) { return gparent; } } } return rootNode;}5.1 插入（未均衡）RBTreeNode *insert(RBTreeNode *root, int data, RBTreeNode *parent){ if (NULL == root) { return getNode(data, parent); } if (data >= root->data) { root->right = insert(root->right, data, root); }else{ root->left = insert(root->left, data, root); } return root;}5.2 插入(均衡)RBTreeNode *inserRB(RBTreeNode *root, int data, RBTreeNode *parent){ root = insert(root,data,parent); return rebalance3(RBTreeEndNode,root);}6 测试红黑树构建int main(){ struct RBTreeNode *node; //2.2.1.1 测试用例 node = NULL; node = inserRB(node, 8, NULL); node = inserRB(node, 4, NULL); node = inserRB(node, 12, NULL); node = inserRB(node, 2, NULL); printf("***2.2.1.1 测试用例 前序***: \n"); preOrderTraverse(node); //2.2.1.2.1 测试用例 node = NULL; node = inserRB(node, 8, NULL); node = inserRB(node, 4, NULL); node = inserRB(node, 12, NULL); node = inserRB(node, 2, NULL); node = inserRB(node, 1, NULL); printf("***2.2.1.2.1 测试用例 前序***: \n"); preOrderTraverse(node); //2.2.1.2.2 测试用例 node = NULL; node = inserRB(node, 8, NULL); node = inserRB(node, 4, NULL); node = inserRB(node, 12, NULL); node = inserRB(node, 2, NULL); node = inserRB(node, 3, NULL); printf("***2.2.1.2.2 测试用例 前序***: \n"); preOrderTraverse(node); //2.2.2.1 测试用例 node = NULL; node = inserRB(node, 8, NULL); node = inserRB(node, 4, NULL); node = inserRB(node, 12, NULL); node = inserRB(node, 20, NULL); printf("***2.2.2.1 测试用例 前序***: \n"); preOrderTraverse(node); //2.2.2.2.1 测试用例 node = NULL; node = inserRB(node, 8, NULL); node = inserRB(node, 12, NULL); node = inserRB(node, 10, NULL); printf("***2.2.2.2.1 测试用例 前序***: \n"); preOrderTraverse(node); //2.2.2.2.2 测试用例 node = NULL; node = inserRB(node, 8, NULL); node = inserRB(node, 12, NULL); node = inserRB(node, 20, NULL); printf("***2.2.2.2.2 测试用例 前序***: \n"); preOrderTraverse(node);}测试后果: ...

二叉搜寻树的缺点二叉搜寻树作为数据存储的构造有重要的劣势：能够疾速的查找给定关键字的数据项，并且能够疾速的插入和删除数据项，然而，二叉搜寻树有一个很麻烦的问题：如果插入的数据是有序的数据，比方上面的状况有一棵初始化为9 8 12的二叉树插入上面的数据：7 6 5 4 3 非均衡树：比拟好的二叉搜寻树数据应该是左右均匀分布的然而插入间断数据后，散布的不平均，咱们称这种树为非均衡树对于一颗均衡二叉树来说，插入/查找等操作的效率是O(logN)对于一颗非均衡树，相当于编写了一个链表 树的平衡性为了能以较快的工夫O(logN)来操作一棵树，咱们须要保障树总是均衡的：至多大部分是均衡的，那么工夫复杂度也是靠近O(logN)的也就是说树中每个节点的右边的子孙节点的个数，应该尽可能的等于左边的子孙节点的个数常见的均衡树有哪些？ AVL树：AVL树是较早的一种均衡树，它有些方法保留树的均衡（每个节点多存储了一个额定的数据）因为AVL树是均衡的，所以工夫复杂度也是O(logN)然而，每次插入/删除操作绝对于红黑树效率不高，所以整体效率不如红黑树 红黑树：红黑树也是通过一些个性来放弃树的均衡因为红黑树，所以工夫复杂度也是在O(logN)另外插入/删除等操作，红黑树的性能要优于AVL树，所以当初均衡树的利用根本都是红黑树 红黑树红黑树规定：红黑树，除了合乎二叉搜寻树的根本规定外，还增加了以下个性：【性质1】.节点是红色或彩色【性质2】.根节点是彩色【性质3】.每个叶子节点都是彩色的空节点（NIL节点）【性质4】.每个红色节点的子节点都是彩色（从每个叶子到根的门路上不能有两个间断的红色节点）【性质5】.从任意节点到其每个节点的所有门路都蕴含雷同数目的彩色节点规定很重要，上面练习会用到，下图就是一个红黑树，下面的五点都合乎 红黑树的绝对均衡后面的束缚，确保了红黑树的要害个性：从根到叶子的最长可能门路，不会超过最短可能门路的两倍长后果就是这个树根本是均衡的尽管没有做到相对的均衡，然而能够保障在最坏的状况下，仍然是高效的 为什么能够做到最长门路不超过最短门路的两倍呢？【性质4】决定了门路不能有两个相连的红色节点【性质5】所有门路都有雷同数目的彩色节点这就表明了没有门路能多余任何其余门路的两倍长 插入新节点遇到状况的解决办法插入一个新节点时，有可能树不再均衡，能够通过三种形式的变换，让树保持平衡换色/左旋转/右旋转 变色为了从新合乎红黑树的规定，尝试把红色节点变成彩色，或者把彩色节点变成红色首先须要晓得插入的新节点通常默认为红色节点因为在插入节点为红色的时候，有可能插入一次是不违反红黑树任何规定的（插入9） 而插入彩色节点，必然会导致有一条门路上多了彩色节点，这是很难调整的红色节点有可能导致呈现红红相连的状况，然而这种状况能够通过色彩变换和旋转来调整 左旋转逆时针旋转红黑树的两个节点，使得父节点被本人的有孩子取代，而本人成为本人的左孩子图中，身为右孩子的x取代了a的地位，而a变成了x的左孩子。此为左旋转 右旋转顺时针旋转红黑树的两个节点，使得父节点被本人的左孩子取代，而本人成为本人的右孩子图中，身为左孩子的x取代了a的地位，而a变成x的右孩子 插入操作接下来，讨论一下插入的状况设要插入的节点为N,其父节点为P其祖父节点为G，其父亲的兄弟节点为U(即P和U是同一节点的子节点) 状况一：新节点N位于树的根，没有父节点这种状况下，咱们间接将红色变换成彩色即可，这样满足性质2 状况二新节点的父节点P是彩色性质4没有生效（新节点是红色的），性质5也没有任何问题只管新节点N有两个彩色的叶子节点nil，然而新节点N是红色的，所以通过它的门路中彩色节点的个数仍然雷同，满足性质5（下图省略了nil） 状况三P为红色，U也是红色 操作计划：将P和U变换为彩色，并且将G变换为红色可能呈现的问题然而N的祖父节点G的父节点也可能是红色，这就违反了性质3，能够递归调整色彩然而如果递归调整色彩到了根节点，就须要进行旋转了，这个上面遇到了再解说 状况四N的叔叔U是黑节点，且N是左孩子。简写：父红叔黑祖黑 N是左儿子变换：父黑--祖红--右旋转 状况五N的叔叔U是彩色节点，且N是右孩子。简写：父红叔黑祖黑，N是右孩子变换：以P为根，左旋转将P作为新插入的红色节点思考即可本人（N）变成彩色祖变成红色以祖为根，进行右旋转 实操上面咱们将10，9，8，7，6，5，4，3，2，1顺次插入树中造成红黑树。多图预警。。。。 红黑树的常识就到这里，至于代码实现看下面的图也晓得是十分难的，临时就先不钻研代码，先捋分明逻辑。

map与unordered_map都是c++ stl中的关联容器，两者的应用也都大致相同。不过在底层的实现上，map应用的是红黑树，unordered_map应用的则是hash表。 红黑树红黑树是一种绝对均衡的二叉搜寻树，并且其附加定义如下： 节点有且只有两种色彩，红色和彩色根节点和叶子节点必须是彩色，其中，叶子节点是虚构存在的空节点NULL红色节点的两个子节点必须是彩色任意节点到叶子节点的门路上，必须蕴含雷同数目的彩色节点能够参考一下以下blog：Red-Black Trees 绝对于AVL均衡树，红黑树对于平衡性的要求没有那么高，因为其对于色彩的定义，任意节点左右子树的高度差在一倍之内（最长门路为节点红黑相间，最短门路为节点全黑），因而频繁插入和删除节点时，触发均衡调整的次数更少，均衡调整的过程也更易收敛。 而c++ stl中的map应用红黑树作为底层实现，对于map中的键值，它只有可能比拟大小：如数值、字符串或其它可能反对大小比拟的类就能够。 hash表hash表，其实就是通过肯定的算法：hash函数将原始数据转为一段固定长度的数值（表这个词其实没有具体意义，hash的存储形式有很多，如再链表法，如凋谢地址法的数据结构，表只是对于它们的一种抽象称说）。 具体可见：什么是hash 这里次要答复一下我本人长期的一个误区： 即之前我始终认为hash只实用于key-value这样的数据，并且认为hash表中只存储value，那么依据key的hash值寻找数据时，存在hash抵触的话，就没法晓得以后hash值对应的value数据到底哪个是对应于key的。 其实，hash也能够对于不是key-value这样的数据进行存储，比方就是一系列大量的数值或字符串，咱们能够应用hash算法，而不是简略的数组顺序存储，为的是放慢查找速度；并且对于key-value这样的数据，其实hash表中所存储的不是只有value，而是key-value这个键值对都存储了，这样在有hash抵触的状况下就能依据key值找到真正对应的value。