企业官网建设流程全解析

建设网站有什么好处,微博网站认证 备案名称,建站需要注意哪些,营销型网站建设 ppt红黑树入门指南#xff08;C语言版#xff09; 文章目录红黑树入门指南#xff08;C语言版#xff09;前言一、红黑树的基本概念1.1 核心定义1.2 关键特性二、红黑树的操作2.1 旋转#xff08;Rotation#xff09;左旋#xff08;Left Rotation#xff09;右旋#xf…红黑树入门指南C语言版文章目录红黑树入门指南C语言版前言一、红黑树的基本概念1.1 核心定义1.2 关键特性二、红黑树的操作2.1 旋转Rotation左旋Left Rotation右旋Right Rotation2.2 插入操作插入修复的三种情况父节点为红色时2.3 删除操作删除修复的四种情况替代节点s为黑色时三、红黑树的C语言实现3.1 数据结构定义3.2 辅助函数创建节点、打印树3.3 旋转操作实现3.4 插入与修复操作3.5 测试代码四、红黑树的应用场景五、总结前言红黑树是一种自平衡二叉搜索树它通过额外的颜色规则保证在最坏情况下基本操作插入、删除、查找的时间复杂度为O(log n)。相比AVL树红黑树的平衡条件更宽松因此旋转操作更少适合需要频繁修改的场景如STL的map、set。一、红黑树的基本概念1.1 核心定义红黑树是每个节点带有颜色属性红色或黑色的二叉搜索树需满足以下5条性质节点颜色每个节点要么是红色要么是黑色。根节点根节点是黑色。叶子节点NIL所有叶子节点空节点通常用NIL表示是黑色。红色节点的子节点若一个节点是红色则它的两个子节点必须是黑色即不存在连续的红色节点。黑高一致从任一节点到其所有后代叶子节点的路径中包含相同数量的黑色节点称为该节点的黑高。1.2 关键特性近似平衡红黑树不追求严格的左右子树高度差≤1如AVL树但通过性质4和5确保最长路径不超过最短路径的2倍最短路径全黑最长路径红黑交替。NIL节点实际实现中为了简化边界条件如叶子节点无子节点通常用一个统一的NIL节点代替所有空指针颜色为黑。二、红黑树的操作红黑树的核心操作包括查找、插入和删除。其中查找与普通二叉搜索树一致插入和删除后可能破坏红黑树性质需通过旋转和重新着色修复。2.1 旋转Rotation旋转是调整树结构的基础操作分为左旋和右旋用于保持二叉搜索树性质的同时调整节点位置。左旋Left Rotation以节点x为中心将x的右子节点y提升为父节点x成为y的左子节点y的原左子节点成为x的右子节点。右旋Right Rotation与左旋对称以节点y为中心将y的左子节点x提升为父节点y成为x的右子节点x的原右子节点成为y的左子节点。2.2 插入操作插入步骤按二叉搜索树规则插入新节点初始颜色设为红色避免破坏性质5。若插入后父节点是黑色无需调整若父节点是红色违反性质4需通过重新着色或旋转修复。插入修复的三种情况父节点为红色时假设新节点为z父节点p(z)祖父节点g(z)叔节点u(z)p(z)的兄弟节点情况1叔节点u(z)是红色 → 将p(z)和u(z)设为黑色g(z)设为红色然后递归检查g(z)。情况2叔节点u(z)是黑色且z是p(z)的右子节点 → 对p(z)左旋转化为情况3。情况3叔节点u(z)是黑色且z是p(z)的左子节点 → 将p(z)设为黑色g(z)设为红色对g(z)右旋。2.3 删除操作删除步骤按二叉搜索树规则删除节点找到替代节点s可能是后继或前驱。若替代节点是黑色删除后会破坏性质5黑高减少需通过重新着色和旋转修复。删除修复的四种情况替代节点s为黑色时假设当前节点为x替代节点兄弟节点s情况1s是红色 → 将s设为黑色父节点设为红色对父节点左旋更新s为新兄弟节点。情况2s是黑色且s的两个子节点都是黑色 → 将s设为红色x上移至父节点。情况3s是黑色左子红、右子黑 → 将s设为红色左子设为黑色对s右旋更新s为新兄弟节点。情况4s是黑色右子红 → 将s的颜色设为父节点颜色父节点设为黑色右子设为黑色对父节点左旋x设为根节点结束。三、红黑树的C语言实现以下是简化版的红黑树实现仅包含插入和遍历删除操作类似但更复杂3.1 数据结构定义// 节点颜色枚举typedefenum{RED,BLACK}Color;// 红黑树节点使用NIL节点简化边界处理typedefstructNode{intdata;// 数据域Color color;// 颜色structNode*left;// 左子节点structNode*right;// 右子节点structNode*parent;// 父节点}Node;// 全局NIL节点所有空指针指向它Node*NIL;// 初始化NIL节点voidinitNIL(){NIL(Node*)malloc(sizeof(Node));NIL-colorBLACK;NIL-leftNIL-rightNIL-parentNULL;}3.2 辅助函数创建节点、打印树// 创建新节点初始颜色为REDNode*createNode(intdata){Node*node(Node*)malloc(sizeof(Node));node-datadata;node-colorRED;// 新节点默认红色node-leftnode-rightnode-parentNIL;returnnode;}// 中序遍历验证二叉搜索树性质voidinOrderTraversal(Node*root){if(rootNIL)return;inOrderTraversal(root-left);printf(%d(%s) ,root-data,root-colorRED?R:B);inOrderTraversal(root-right);}// 层序遍历直观查看树结构voidlevelOrderTraversal(Node*root){if(rootNIL){printf(Tree is empty\n);return;}Node*queue[100];intfront0,rear0;queue[rear]root;while(frontrear){Node*currentqueue[front];printf(%d(%s) ,current-data,current-colorRED?R:B);if(current-left!NIL)queue[rear]current-left;if(current-right!NIL)queue[rear]current-right;}printf(\n);}3.3 旋转操作实现// 左旋x为旋转中心voidleftRotate(Node**root,Node*x){Node*yx-right;// y是x的右子节点x-righty-left;// y的左子节点变为x的右子节点if(y-left!NIL){y-left-parentx;}y-parentx-parent;// y继承x的父节点if(x-parentNIL){*rooty;// x是根节点y成为新根}elseif(xx-parent-left){x-parent-lefty;// x是左子节点y替换x的位置}else{x-parent-righty;// x是右子节点y替换x的位置}y-leftx;// x成为y的左子节点x-parenty;}// 右旋与左旋对称voidrightRotate(Node**root,Node*y){Node*xy-left;// x是y的左子节点y-leftx-right;// x的右子节点变为y的左子节点if(x-right!NIL){x-right-parenty;}x-parenty-parent;// x继承y的父节点if(y-parentNIL){*rootx;// y是根节点x成为新根}elseif(yy-parent-left){y-parent-leftx;// y是左子节点x替换y的位置}else{y-parent-rightx;// y是右子节点x替换y的位置}x-righty;// y成为x的右子节点y-parentx;}3.4 插入与修复操作// 插入修复处理插入后可能的红红冲突voidinsertFixup(Node**root,Node*z){while(z-parent-colorRED){// 父节点为红色时需修复if(z-parentz-parent-parent-left){// 父节点是祖父的左子Node*yz-parent-parent-right;// 叔节点if(y-colorRED){// 情况1叔节点红z-parent-colorBLACK;y-colorBLACK;z-parent-parent-colorRED;zz-parent-parent;// 检查祖父}else{if(zz-parent-right){// 情况2z是右子zz-parent;leftRotate(root,z);}// 情况3z是左子z-parent-colorBLACK;z-parent-parent-colorRED;rightRotate(root,z-parent-parent);}}else{// 父节点是祖父的右子对称处理Node*yz-parent-parent-left;// 叔节点if(y-colorRED){z-parent-colorBLACK;y-colorBLACK;z-parent-parent-colorRED;zz-parent-parent;}else{if(zz-parent-left){zz-parent;rightRotate(root,z);}z-parent-colorBLACK;z-parent-parent-colorRED;leftRotate(root,z-parent-parent);}}}(*root)-colorBLACK;// 确保根节点为黑}// 插入节点返回根节点Node*insert(Node*root,intdata){Node*zcreateNode(data);Node*yNIL;// y记录z的父节点Node*xroot;// 寻找插入位置类似BST插入while(x!NIL){yx;if(z-datax-data){xx-left;}else{xx-right;}}z-parenty;if(yNIL){rootz;// 树为空z成为根}elseif(z-datay-data){y-leftz;}else{y-rightz;}// 修复红黑树性质insertFixup(root,z);returnroot;}3.5 测试代码intmain(){initNIL();// 初始化NIL节点Node*rootNIL;// 插入测试数据inttestData[]{10,20,30,15,25,5};intnsizeof(testData)/sizeof(testData[0]);for(inti0;in;i){rootinsert(root,testData[i]);printf(插入 %d 后层序遍历: ,testData[i]);levelOrderTraversal(root);}// 验证中序遍历应有序printf(中序遍历结果: );inOrderTraversal(root);printf(\n);return0;}四、红黑树的应用场景红黑树因其高效的动态操作性能被广泛应用于需要快速查找、插入、删除的场景C STLmap、set、multimap、multiset的底层实现GCC使用红黑树。Java集合TreeMap、TreeSet基于红黑树。Linux内核进程调度CFS、内存管理中的区间树。数据库索引部分数据库的索引结构如MySQL的某些存储引擎。五、总结红黑树通过颜色规则和旋转操作在动态数据维护中实现了高效的平衡。其核心是理解插入/删除后的修复逻辑尤其是各种情况的处理顺序。尽管代码实现较复杂但掌握红黑树能帮助我们理解许多高级数据结构的设计思想。