红黑树的应用：
1、利用key_value对，快速查找，o(logn)
- socket与客户端id之间，形成映射关系(socket, id)
- 内存分配管理
- 一整块内存，不断分配小块
- 每分配一次，就加入到红黑树
- 释放的时候，在红黑树找到相应的块，然后去释放
2、利用红黑树中序遍历是顺序的特性
- 进程的调度
- 进程处于等待状态，每个进程都有等待的时间，在未来某个时刻会运行，将这些进程利用红黑树组织起来
- 在某个时刻，找到对应时刻的节点，然后中序遍历，就可以把该节点之前的节点全部运行到。
3、nginx定时器
为什么使用红黑树不使用哈希表？
- 极少情况下，需要key是有序的，如定时器
二叉排序树（bstree）
- 左子树 < 根 < 右子树
- 中序遍历结果是顺序的
- 极端情况下，如果顺序插入，结果就成了链表
- 为了解决这个问题，引入了红黑树
红黑树性质
- 每个节点是红色的或黑色的
- 根节点是黑色的
- 叶子节点是黑色的
- 红色节点的两个子节点必须是黑色的
- 对每个节点，该节点到其子孙节点的所有路径上的包含相同数目的黑节点（黑高相同）
- 最短路径就是全黑
- 最长路径就是黑红相间
如何证明红黑树的正确性？
- 采用归纳法
左旋与右旋
- 改变三个方向，六根指针
红黑树的插入：
- 插入节点的时候，原先的树是满足红黑树性质的
- 插入节点的颜色是红色更容易满足红黑树的性质
- 插入的节点是红色，且其父节点也是红色的时候，需要调整
插入有三种情况：
- 叔父节点是红色
- 叔父节点是黑色，且祖父节点，父节点和插入节点不是一条直线
- 叔父节点是黑色，且祖父节点，父节点和插入节点是一条直线
平衡二叉树：
- 内部不是color，而是一个high记录高度，如果左右子树高度相差超过1，就需要调整。
红黑树的删除：
- 什么是删除节点? y-> y是z的后继节点
- 什么是轴心节点? x是y的右子树
- 如果x是红色，把x变成黑色
- 如果x是黑色，需要进行调整
删除y节点，是什么颜色的时候需要调整？
- 黑色需要调整，删除黑色破坏了黑高
#include <stdio.h> #include <stdlib.h> #include <string.h> #define red 1 #define black 2 typedef int key_type; typedef struct _rbtree_node { unsigned char color; struct _rbtree_node *right; struct _rbtree_node *left; struct _rbtree_node *parent; key_type key; void *value; } rbtree_node; typedef struct _rbtree { rbtree_node *root; rbtree_node *nil; } rbtree; rbtree_node *rbtree_mini(rbtree *t, rbtree_node *x) { while (x->left != t->nil) { x = x->left; } return x; } rbtree_node *rbtree_maxi(rbtree *t, rbtree_node *x) { while (x->right != t->nil) { x = x->right; } return x; } rbtree_node *rbtree_successor(rbtree *t, rbtree_node *x) { rbtree_node *y = x->parent; if (x->right != t->nil) { return rbtree_mini(t, x->right); } while ((y != t->nil) && (x == y->right)) { x = y; y = y->parent; } return y; } void rbtree_left_rotate(rbtree *t, rbtree_node *x) { rbtree_node *y = x->right; // x --> y , y --> x, right --> left, left --> right x->right = y->left; //1 1 if (y->left != t->nil) { //1 2 y->left->parent = x; } y->parent = x->parent; //1 3 if (x->parent == t->nil) { //1 4 t->root = y; } else if (x == x->parent->left) { x->parent->left = y; } else { x->parent->right = y; } y->left = x; //1 5 x->parent = y; //1 6 } void rbtree_right_rotate(rbtree *t, rbtree_node *y) { rbtree_node *x = y->left; y->left = x->right; if (x->right != t->nil) { x->right->parent = y; } x->parent = y->parent; if (y->parent == t->nil) { t->root = x; } else if (y == y->parent->right) { y->parent->right = x; } else { y->parent->left = x; } x->right = y; y->parent = x; } void rbtree_insert_fixup(rbtree *t, rbtree_node *z) { while (z->parent->color == red) { //z ---> red if (z->parent == z->parent->parent->left) { rbtree_node *y = z->parent->parent->right; if (y->color == red) { z->parent->color = black; y->color = black; z->parent->parent->color = red; z = z->parent->parent; //z --> red } else { if (z == z->parent->right) { z = z->parent; rbtree_left_rotate(t, z); } z->parent->color = black; z->parent->parent->color = red; rbtree_right_rotate(t, z->parent->parent); } }else { rbtree_node *y = z->parent->parent->left; if (y->color == red) { z->parent->color = black; y->color = black; z->parent->parent->color = red; z = z->parent->parent; //z --> red } else { if (z == z->parent->left) { z = z->parent; rbtree_right_rotate(t, z); } z->parent->color = black; z->parent->parent->color = red; rbtree_left_rotate(t, z->parent->parent); } } } t->root->color = black; } void rbtree_insert(rbtree *t, rbtree_node *z) { rbtree_node *y = t->nil; rbtree_node *x = t->root; while (x != t->nil) { y = x; if (z->key < x->key) { x = x->left; } else if (z->key > x->key) { x = x->right; } else { //exist return ; } } z->parent = y; if (y == t->nil) { t->root = z; } else if (z->key < y->key) { y->left = z; } else { y->right = z; } z->left = t->nil; z->right = t->nil; z->color = red; rbtree_insert_fixup(t, z); } void rbtree_delete_fixup(rbtree *t, rbtree_node *x) { while ((x != t->root) && (x->color == black)) { if (x == x->parent->left) { rbtree_node *w= x->parent->right; if (w->color == red) { w->color = black; x->parent->color = red; rbtree_left_rotate(t, x->parent); w = x->parent->right; } if ((w->left->color == black) && (w->right->color == black)) { w->color = red; x = x->parent; } else { if (w->right->color == black) { w->left->color = black; w->color = red; rbtree_right_rotate(t, w); w = x->parent->right; } w->color = x->parent->color; x->parent->color = black; w->right->color = black; rbtree_left_rotate(t, x->parent); x = t->root; } } else { rbtree_node *w = x->parent->left; if (w->color == red) { w->color = black; x->parent->color = red; rbtree_right_rotate(t, x->parent); w = x->parent->left; } if ((w->left->color == black) && (w->right->color == black)) { w->color = red; x = x->parent; } else { if (w->left->color == black) { w->right->color = black; w->color = red; rbtree_left_rotate(t, w); w = x->parent->left; } w->color = x->parent->color; x->parent->color = black; w->left->color = black; rbtree_right_rotate(t, x->parent); x = t->root; } } } x->color = black; } rbtree_node *rbtree_delete(rbtree *t, rbtree_node *z) { rbtree_node *y = t->nil; rbtree_node *x = t->nil; if ((z->left == t->nil) || (z->right == t->nil)) { y = z; } else { y = rbtree_successor(t, z); } if (y->left != t->nil) { x = y->left; } else if (y->right != t->nil) { x = y->right; } x->parent = y->parent; if (y->parent == t->nil) { t->root = x; } else if (y == y->parent->left) { y->parent->left = x; } else { y->parent->right = x; } if (y != z) { z->key = y->key; z->value = y->value; } if (y->color == black) { rbtree_delete_fixup(t, x); } return y; } rbtree_node *rbtree_search(rbtree *t, key_type key) { rbtree_node *node = t->root; while (node != t->nil) { if (key < node->key) { node = node->left; } else if (key > node->key) { node = node->right; } else { return node; } } return t->nil; } void rbtree_traversal(rbtree *t, rbtree_node *node) { if (node != t->nil) { rbtree_traversal(t, node->left); printf("key:%d, color:%dn", node->key, node->color); rbtree_traversal(t, node->right); } } int main() { int keyarray[20] = {24,25,13,35,23, 26,67,47,38,98, 20,19,17,49,12, 21,9,18,14,15}; rbtree *t = (rbtree *)malloc(sizeof(rbtree)); if (t == null) { printf("malloc failedn"); return -1; } t->nil = (rbtree_node*)malloc(sizeof(rbtree_node)); t->nil->color = black; t->root = t->nil; rbtree_node *node = t->nil; int i = 0; for (i = 0;i < 20;i ++) { node = (rbtree_node*)malloc(sizeof(rbtree_node)); node->key = keyarray[i]; node->value = null; rbtree_insert(t, node); } rbtree_traversal(t, t->root); printf("----------------------------------------n"); for (i = 0;i < 20;i ++) { rbtree_node *node = rbtree_search(t, keyarray[i]); rbtree_node *cur = rbtree_delete(t, node); free(cur); rbtree_traversal(t, t->root); printf("----------------------------------------n"); } }
总结
到此这篇关于c++实现红黑树的文章就介绍到这了,更多相关c++实现红黑树内容请搜索<计算机技术网(www.ctvol.com)!!>以前的文章或继续浏览下面的相关文章希望大家以后多多支持<计算机技术网(www.ctvol.com)!!>！
需要了解更多c/c++开发分享C++实现红黑树应用实例代码，都可以关注C/C++技术分享栏目—计算机技术网(www.ctvol.com)!
本文来自网络收集，不代表计算机技术网立场，如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址：https://www.ctvol.com/c-cdevelopment/913752.html