【数据结构与算法】第29篇：红黑树原理与C语言模拟

一、红黑树的定义1.1 五大性质红黑树是一种自平衡二叉查找树每个节点增加一个颜色属性红或黑必须满足性质说明性质1每个节点是红色或黑色性质2根节点是黑色性质3所有叶子节点NIL是黑色性质4红色节点的两个子节点都是黑色不能有连续红性质5从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点黑高相同关键推论红黑树的最长路径不超过最短路径的2倍因此大致平衡。1.2 节点结构c#define RED 0 #define BLACK 1 typedef struct RBNode { int data; int color; // RED 或 BLACK struct RBNode *left; struct RBNode *right; struct RBNode *parent; // 需要父指针 } RBNode, *RBTree;二、红黑树与AVL树的对比对比项AVL树红黑树平衡性严格高度差≤1大致黑高相同树高约 1.44 log n约 2 log n插入旋转最多2次最多3次删除旋转最多O(log n)次最多3次查找效率更快略慢插入/删除效率较慢更快实现复杂度中等较难工程应用较少广泛结论查找多选AVL插入删除多选红黑树。三、插入操作的核心规则3.1 插入规则新插入的节点默认为红色不破坏黑高。需要调整的情况新节点N父节点P祖父G叔父U情况条件处理情况1空树插入根节点改为黑色情况2P为黑色无需调整情况3P为红色U为红色变色P和U变黑G变红递归处理G情况4P为红色U为黑色N、P、G呈直线旋转变色情况5P为红色U为黑色N、P、G呈折线双旋转变色3.2 变色规则图示text情况3P红U红 G(黑) G(红) / \ 变色→ / \ P(红) U(红) P(黑) U(黑) / / N(红) N(红)text情况4P红U黑LL型 G(黑) P(黑) / \ 右旋→ / \ P(红) U(黑) N(红) G(红) / \ N(红) U(黑)text情况4RR型对称处理左旋 情况5LR型 G(黑) G(黑) N(黑) / \ 左旋→ / \ 右旋→ / \ P(红) U(黑) N(红) U(黑) P(红) G(红) \ / \ N(红) P(红) U(黑)情况5RL型对称处理先右旋后左旋3.3 插入代码框架c// 左旋与AVL类似需维护parent void leftRotate(RBTree *root, RBNode *x) { RBNode *y x-right; x-right y-left; if (y-left ! NULL) y-left-parent x; y-parent x-parent; if (x-parent NULL) *root y; else if (x x-parent-left) x-parent-left y; else x-parent-right y; y-left x; x-parent y; } // 右旋对称 void rightRotate(RBTree *root, RBNode *y) { // 对称实现... } // 插入后调整 void insertFixup(RBTree *root, RBNode *z) { while (z ! *root z-parent-color RED) { if (z-parent z-parent-parent-left) { RBNode *y z-parent-parent-right; // 叔父 if (y ! NULL y-color RED) { // 情况3变色 z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-right) { // 情况5LR型 z z-parent; leftRotate(root, z); } // 情况4LL型 z-parent-color BLACK; z-parent-parent-color RED; rightRotate(root, z-parent-parent); } } else { // 对称情况P是右孩子 // ... } } (*root)-color BLACK; }四、C语言模拟简化版由于完整红黑树代码量很大约300-500行这里实现一个简化模拟重点演示插入和调整逻辑。c#include stdio.h #include stdlib.h #define RED 0 #define BLACK 1 typedef struct RBNode { int data; int color; struct RBNode *left; struct RBNode *right; struct RBNode *parent; } RBNode, *RBTree; // 创建节点 RBNode* createNode(int data) { RBNode *node (RBNode*)malloc(sizeof(RBNode)); node-data data; node-color RED; // 新节点默认为红色 node-left NULL; node-right NULL; node-parent NULL; return node; } // 左旋 void leftRotate(RBTree *root, RBNode *x) { RBNode *y x-right; x-right y-left; if (y-left ! NULL) y-left-parent x; y-parent x-parent; if (x-parent NULL) *root y; else if (x x-parent-left) x-parent-left y; else x-parent-right y; y-left x; x-parent y; } // 右旋 void rightRotate(RBTree *root, RBNode *y) { RBNode *x y-left; y-left x-right; if (x-right ! NULL) x-right-parent y; x-parent y-parent; if (y-parent NULL) *root x; else if (y y-parent-left) y-parent-left x; else y-parent-right x; x-right y; y-parent x; } // 插入调整 void insertFixup(RBTree *root, RBNode *z) { while (z ! *root z-parent-color RED) { if (z-parent z-parent-parent-left) { RBNode *y z-parent-parent-right; if (y ! NULL y-color RED) { // 情况3叔父红色变色 z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-right) { // 情况5LR型 z z-parent; leftRotate(root, z); } // 情况4LL型 z-parent-color BLACK; z-parent-parent-color RED; rightRotate(root, z-parent-parent); } } else { // 对称情况P是右孩子 RBNode *y z-parent-parent-left; if (y ! NULL y-color RED) { z-parent-color BLACK; y-color BLACK; z-parent-parent-color RED; z z-parent-parent; } else { if (z z-parent-left) { z z-parent; rightRotate(root, z); } z-parent-color BLACK; z-parent-parent-color RED; leftRotate(root, z-parent-parent); } } } (*root)-color BLACK; } // 插入 void insert(RBTree *root, int data) { RBNode *z createNode(data); RBNode *y NULL; RBNode *x *root; // 普通BST插入 while (x ! NULL) { y x; if (z-data x-data) x x-left; else x x-right; } z-parent y; if (y NULL) *root z; else if (z-data y-data) y-left z; else y-right z; // 调整红黑树性质 insertFixup(root, z); } // 中序遍历 void inorder(RBNode *root) { if (root NULL) return; inorder(root-left); printf(%d(%s) , root-data, root-color RED ? 红 : 黑); inorder(root-right); } // 打印树结构简化 void printTree(RBNode *root, int level) { if (root NULL) return; printTree(root-right, level 1); for (int i 0; i level; i) printf( ); printf(%d(%s)\n, root-data, root-color RED ? 红 : 黑); printTree(root-left, level 1); } int main() { RBTree root NULL; printf( 红黑树插入演示 \n); int values[] {10, 20, 30, 15, 25, 5, 1}; for (int i 0; i 7; i) { insert(root, values[i]); printf(\n插入 %d 后:\n, values[i]); printf(中序遍历: ); inorder(root); printf(\n树结构:\n); printTree(root, 0); } return 0; }运行结果部分text 红黑树插入演示 插入 10 后: 中序遍历: 10(黑) 树结构: 10(黑) 插入 20 后: 中序遍历: 10(黑) 20(红) 树结构: 20(红) 10(黑) 插入 30 后: 中序遍历: 10(红) 20(黑) 30(红) 树结构: 30(红) 20(黑) 10(红) 插入 15 后: 中序遍历: 10(黑) 15(红) 20(黑) 30(黑) 树结构: 30(黑) 20(黑) 15(红) 10(黑) ...五、红黑树的应用应用说明C STL map/set底层是红黑树Java TreeMap/TreeSet底层是红黑树Linux内核调度、内存管理、文件系统epoll事件驱动红黑树管理文件描述符Nginx定时器红黑树管理定时事件六、小结这一篇我们学习了红黑树的核心知识要点说明五大性质根黑、叶黑、红不连、黑高相同插入规则新节点红根据叔父颜色分情况处理核心操作变色、左旋、右旋复杂度查找/插入/删除 O(log n)工程地位最广泛应用的平衡树红黑树 vs AVL树AVL严格平衡查找快插入删除慢红黑树大致平衡查找略慢插入删除快下一篇我们讲哈希表。七、思考题为什么红黑树新插入的节点是红色的红黑树的性质5黑高相同如何保证树的平衡如果连续插入相同的值红黑树会如何处理查找操作比AVL树慢但为什么工程中更常用红黑树欢迎在评论区讨论你的答案。