深圳网站设计公司有哪些,手机怎么做微信公众号,wordpress安装到的数据库名称,企业所得税是利润的25%吗为什么红黑树胜过AVL树 博主简介一、引言1.1、红黑树和AVL树简介1.2、红黑树在某些方面优于AVL树 二、红黑树和AVL树的基本原理2.1、红黑树的定义和性质2.2、AVL树的定义和性质2.3、对比两种树结构的特点 三、插入和删除操作的复杂性比较3.1、红黑树的插入操作和平衡性维护3.2、… 为什么红黑树胜过AVL树 博主简介一、引言1.1、红黑树和AVL树简介1.2、红黑树在某些方面优于AVL树 二、红黑树和AVL树的基本原理2.1、红黑树的定义和性质2.2、AVL树的定义和性质2.3、对比两种树结构的特点 三、插入和删除操作的复杂性比较3.1、红黑树的插入操作和平衡性维护3.2、AVL树的插入操作和平衡性维护3.3、分析并对比两种树在插入操作中的性能差异3.3.1、实现一个AVL树进行一万次数据插入3.3.2、实现一个红黑树进行一万次数据插入 3.4、红黑树相对于AVL树的优势 四、查找和遍历操作的效率比较4.1、红黑树的查找和遍历操作4.2、AVL树的查找和遍历操作4.3、对比两种树在查找和遍历操作中的性能差异 五、内存占用和空间复杂性比较5.1、红黑树的内存占用特点5.2、AVL树的内存占用特点5.3、对比两种树在内存占用和空间复杂性方面的优势 六、性能优化和应用场景6.1、如何根据具体应用场景选择合适的树结构6.2、红黑树的优化策略6.3、AVL树的优化策略6.4、实际应用中红黑树胜过AVL树的案例和场景 总结 博主简介 一个热爱分享高性能服务器后台开发知识的博主目标是通过理论与代码实践的结合让世界上看似难以掌握的技术变得易于理解与掌握。技能涵盖了多个领域包括C/C、Linux、Nginx、MySQL、Redis、fastdfs、kafka、Docker、TCP/IP、协程、DPDK等。 ️ CSDN实力新星、CSDN博客专家、华为云云享专家、阿里云专家博主 我的博客将提供以下内容 1. 高性能服务器后台开发知识深入剖析深入探讨各种技术的原理和内部工作机制帮助理解它们的核心概念和使用方法。 2. 实践案例与代码分享分享一些实际项目中的应用案例和代码实现帮助将理论知识转化为实际应用并提供实践中的经验和技巧。 3. 技术教程和指南编写简明扼要的教程和指南帮助初学者入门并逐步掌握这些技术同时也为有经验的开发者提供深入的技术进阶指导。 无论是一个刚入门的初学者还是一个有经验的开发者我的博客都将提供有价值的内容和实用的技术指导。 一、引言
1.1、红黑树和AVL树简介
红黑树和AVL树都是自平衡二叉搜索树它们在维护有序数据集合时非常有用。
红黑树 红黑树是一种高效的平衡树它是一种近似平衡的二叉搜索树在每个节点上都有一个额外的标志来表示节点的颜色红色或黑色。红黑树满足以下规则
节点是红色或黑色。根节点是黑色。所有叶子节点NIL节点都是黑色。如果一个节点是红色则其两个子节点都是黑色。从任意节点到其每个叶子节点的所有路径都包含相同数目的黑色节点这保证了树的近似平衡性。
这些规则确保了红黑树的平衡性使得在进行插入和删除操作时红黑树能够通过有限次旋转和重新着色来维护其平衡状态。红黑树在插入和删除操作上相对较快但在查找操作的性能上可能略有劣势。
AVL树 AVL树是一种更为严格的平衡树它的全称是Adelson-Velsky and Landis得名于其发明者。AVL树要求在任何节点的左子树和右子树高度差不超过1。因为它的平衡条件更为严格所以在进行插入和删除操作时AVL树可能需要更多的旋转来保持平衡因此在维护平衡性方面开销较大。但与此同时AVL树在查找操作上可能比红黑树更快因为它的高度比红黑树更低。 #mermaid-svg-9KnIWxsnbSK7C7TD {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-9KnIWxsnbSK7C7TD .error-icon{fill:#552222;}#mermaid-svg-9KnIWxsnbSK7C7TD .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-9KnIWxsnbSK7C7TD .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-9KnIWxsnbSK7C7TD .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-9KnIWxsnbSK7C7TD .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-9KnIWxsnbSK7C7TD .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-9KnIWxsnbSK7C7TD .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-9KnIWxsnbSK7C7TD .marker{fill:#333333;stroke:#333333;}#mermaid-svg-9KnIWxsnbSK7C7TD .marker.cross{stroke:#333333;}#mermaid-svg-9KnIWxsnbSK7C7TD svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-9KnIWxsnbSK7C7TD .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-9KnIWxsnbSK7C7TD .cluster-label text{fill:#333;}#mermaid-svg-9KnIWxsnbSK7C7TD .cluster-label span{color:#333;}#mermaid-svg-9KnIWxsnbSK7C7TD .label text,#mermaid-svg-9KnIWxsnbSK7C7TD span{fill:#333;color:#333;}#mermaid-svg-9KnIWxsnbSK7C7TD .node rect,#mermaid-svg-9KnIWxsnbSK7C7TD .node circle,#mermaid-svg-9KnIWxsnbSK7C7TD .node ellipse,#mermaid-svg-9KnIWxsnbSK7C7TD .node polygon,#mermaid-svg-9KnIWxsnbSK7C7TD .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-9KnIWxsnbSK7C7TD .node .label{text-align:center;}#mermaid-svg-9KnIWxsnbSK7C7TD .node.clickable{cursor:pointer;}#mermaid-svg-9KnIWxsnbSK7C7TD .arrowheadPath{fill:#333333;}#mermaid-svg-9KnIWxsnbSK7C7TD .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-9KnIWxsnbSK7C7TD .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-9KnIWxsnbSK7C7TD .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-9KnIWxsnbSK7C7TD .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-9KnIWxsnbSK7C7TD .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-9KnIWxsnbSK7C7TD .cluster text{fill:#333;}#mermaid-svg-9KnIWxsnbSK7C7TD .cluster span{color:#333;}#mermaid-svg-9KnIWxsnbSK7C7TD div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-9KnIWxsnbSK7C7TD :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 1 2 3 4 5 6 7 8 9 header 1.2、红黑树在某些方面优于AVL树 平衡性维护开销红黑树相对于AVL树来说在维护平衡性方面更加轻量级。AVL树要求每个节点的左子树和右子树的高度差不超过1因此在进行插入和删除操作时可能需要更频繁地进行旋转操作来维护这种严格的平衡性导致插入和删除的开销更大。而红黑树通过一系列的规则来保持近似平衡允许在一定程度上的不平衡减少了维护平衡性的开销。 插入和删除性能由于红黑树放宽了对平衡性的要求它在进行插入和删除操作时通常比AVL树更快。尤其是在频繁进行大量插入和删除操作的场景下红黑树相比AVL树会更高效。 内存占用红黑树通常比AVL树占用更少的内存空间。由于红黑树允许在一定程度上的不平衡它的高度相对较低这导致了更少的额外节点和指针。而AVL树由于要保持严格的平衡可能需要更多的节点和指针来维护树的结构从而增加了内存占用。 查找性能虽然在维护平衡性和插入删除方面红黑树优于AVL树但在查找操作上AVL树的性能通常优于红黑树。由于AVL树的严格平衡性查找操作的时间复杂度较低比红黑树更快。
红黑树在某些场景下可以提供更好的插入和删除性能以及更低的内存占用适用于需要频繁插入和删除操作而对查找性能要求相对较低的情况。然而对于需要高效查找操作的场景AVL树可能更适合因为它在查找性能上优于红黑树。在实际应用中根据具体的需求来选择合适的树结构是很重要的。
二、红黑树和AVL树的基本原理
2.1、红黑树的定义和性质
红黑树是一种自平衡的二叉查找树它在二叉查找树的基础上增加了额外的性质来保持树的平衡。这种自平衡的特性使得红黑树的插入、删除和查找操作的时间复杂度都能够保持在 O ( l o g n ) O(log n) O(logn)级别。
红黑树的定义
每个节点都有一个颜色要么是红色要么是黑色。根节点必须是黑色。叶子节点NIL 节点都是黑色的。如果一个节点是红色的则其子节点必须是黑色的。从任意节点到其每个叶子节点的路径上经过的黑色节点数量必须相同。
红黑树的性质
从根节点到叶子节点的最长可能路径不超过最短可能路径的两倍。这确保了红黑树的高度始终保持在 O(log n) 级别从而保持了其高效的插入、删除和查找操作。因为根节点是黑色的所以红黑树没有根节点到叶子节点全为红色的路径。每个叶子节点都是黑色的通常使用 NIL 节点表示这样可以确保空指针问题。如果一个节点是红色的它的两个子节点都是黑色的。这意味着不存在两个连续的红色节点从而避免了出现红色节点的连续路径保持了树的平衡。从任意节点到其每个叶子节点的路径上经过的黑色节点数量必须相同。这个性质保证了红黑树在插入和删除操作后能够自动调整重新保持平衡。
红黑树的这些性质共同保证了树的平衡性和高效性。在插入和删除节点时红黑树会根据这些性质进行自我调整通过颜色变换和树的旋转操作来保持性质的满足从而保持了树的平衡。这些自平衡的操作确保了红黑树的搜索、插入和删除操作都能够保持在 O ( l o g n ) O(log n) O(logn) 的时间复杂度使得红黑树成为一种广泛应用于数据结构和算法中的二叉查找树。
2.2、AVL树的定义和性质
AVL树是一种自平衡的二叉搜索树它的定义和性质如下
定义AVL树是一种二叉搜索树其中每个节点的左子树和右子树的高度差平衡因子不超过1。
性质
AVL树是一棵二叉搜索树所以它满足二叉搜索树的性质对于每个节点它的左子树的所有节点都小于该节点的值右子树的所有节点都大于该节点的值。每个节点的平衡因子等于其右子树的高度减去左子树的高度。平衡因子只能是-1、0或1否则不满足AVL树的定义。AVL树中的每个子树也是AVL树这意味着在插入或删除节点后整棵树需要通过旋转操作来保持平衡。
AVL树的自平衡特性保证了树的高度保持较小使得查找、插入和删除操作的时间复杂度都能够保持在O(log n)。然而由于其频繁的自平衡操作相比于红黑树AVL树可能会在某些场景下有更高的常数时间开销。
2.3、对比两种树结构的特点
平衡性要求 红黑树对于红黑树它允许节点的左右子树高度差在一定范围内不超过2倍而不是像AVL树那样严格要求平衡因子不超过1。这使得红黑树的平衡要求相对较宽松。 AVL树AVL树要求任何节点的左右子树高度差不超过1这是一种严格的平衡性要求。
插入和删除操作 红黑树由于红黑树的平衡性要求相对较松插入和删除操作相对较快。当执行插入和删除时红黑树可能需要进行少量的旋转和重新着色操作来维持平衡。 AVL树AVL树的平衡性要求更严格因此在插入和删除操作时可能需要进行多次旋转来保持树的平衡。这使得插入和删除操作相对较慢。
搜索性能 红黑树由于红黑树的平衡性要求较松它的高度可能相对较高。这可能导致搜索操作的性能略低于AVL树。 AVL树由于AVL树的严格平衡性要求它的高度相对较小因此搜索性能较好。
红黑树示意图 #mermaid-svg-ypfdaGjR4dYsuWrI {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-ypfdaGjR4dYsuWrI .error-icon{fill:#552222;}#mermaid-svg-ypfdaGjR4dYsuWrI .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-ypfdaGjR4dYsuWrI .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-ypfdaGjR4dYsuWrI .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-ypfdaGjR4dYsuWrI .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-ypfdaGjR4dYsuWrI .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-ypfdaGjR4dYsuWrI .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-ypfdaGjR4dYsuWrI .marker{fill:#333333;stroke:#333333;}#mermaid-svg-ypfdaGjR4dYsuWrI .marker.cross{stroke:#333333;}#mermaid-svg-ypfdaGjR4dYsuWrI svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-ypfdaGjR4dYsuWrI .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-ypfdaGjR4dYsuWrI .cluster-label text{fill:#333;}#mermaid-svg-ypfdaGjR4dYsuWrI .cluster-label span{color:#333;}#mermaid-svg-ypfdaGjR4dYsuWrI .label text,#mermaid-svg-ypfdaGjR4dYsuWrI span{fill:#333;color:#333;}#mermaid-svg-ypfdaGjR4dYsuWrI .node rect,#mermaid-svg-ypfdaGjR4dYsuWrI .node circle,#mermaid-svg-ypfdaGjR4dYsuWrI .node ellipse,#mermaid-svg-ypfdaGjR4dYsuWrI .node polygon,#mermaid-svg-ypfdaGjR4dYsuWrI .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-ypfdaGjR4dYsuWrI .node .label{text-align:center;}#mermaid-svg-ypfdaGjR4dYsuWrI .node.clickable{cursor:pointer;}#mermaid-svg-ypfdaGjR4dYsuWrI .arrowheadPath{fill:#333333;}#mermaid-svg-ypfdaGjR4dYsuWrI .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-ypfdaGjR4dYsuWrI .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-ypfdaGjR4dYsuWrI .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-ypfdaGjR4dYsuWrI .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-ypfdaGjR4dYsuWrI .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-ypfdaGjR4dYsuWrI .cluster text{fill:#333;}#mermaid-svg-ypfdaGjR4dYsuWrI .cluster span{color:#333;}#mermaid-svg-ypfdaGjR4dYsuWrI div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-ypfdaGjR4dYsuWrI :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 5 10 13 15 20 header AVL树示意图 #mermaid-svg-qRJlaAykjNVhFhEV {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-qRJlaAykjNVhFhEV .error-icon{fill:#552222;}#mermaid-svg-qRJlaAykjNVhFhEV .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-qRJlaAykjNVhFhEV .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-qRJlaAykjNVhFhEV .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-qRJlaAykjNVhFhEV .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-qRJlaAykjNVhFhEV .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-qRJlaAykjNVhFhEV .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-qRJlaAykjNVhFhEV .marker{fill:#333333;stroke:#333333;}#mermaid-svg-qRJlaAykjNVhFhEV .marker.cross{stroke:#333333;}#mermaid-svg-qRJlaAykjNVhFhEV svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-qRJlaAykjNVhFhEV .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-qRJlaAykjNVhFhEV .cluster-label text{fill:#333;}#mermaid-svg-qRJlaAykjNVhFhEV .cluster-label span{color:#333;}#mermaid-svg-qRJlaAykjNVhFhEV .label text,#mermaid-svg-qRJlaAykjNVhFhEV span{fill:#333;color:#333;}#mermaid-svg-qRJlaAykjNVhFhEV .node rect,#mermaid-svg-qRJlaAykjNVhFhEV .node circle,#mermaid-svg-qRJlaAykjNVhFhEV .node ellipse,#mermaid-svg-qRJlaAykjNVhFhEV .node polygon,#mermaid-svg-qRJlaAykjNVhFhEV .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-qRJlaAykjNVhFhEV .node .label{text-align:center;}#mermaid-svg-qRJlaAykjNVhFhEV .node.clickable{cursor:pointer;}#mermaid-svg-qRJlaAykjNVhFhEV .arrowheadPath{fill:#333333;}#mermaid-svg-qRJlaAykjNVhFhEV .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-qRJlaAykjNVhFhEV .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-qRJlaAykjNVhFhEV .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-qRJlaAykjNVhFhEV .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-qRJlaAykjNVhFhEV .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-qRJlaAykjNVhFhEV .cluster text{fill:#333;}#mermaid-svg-qRJlaAykjNVhFhEV .cluster span{color:#333;}#mermaid-svg-qRJlaAykjNVhFhEV div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-qRJlaAykjNVhFhEV :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 5 10 13 15 20 三、插入和删除操作的复杂性比较
3.1、红黑树的插入操作和平衡性维护 插入节点首先按照二叉搜索树的规则将新节点插入到红黑树中通常将新节点标记为红色。 重新着色和旋转为了维护红黑树的平衡性需要对插入的节点进行着色和旋转操作。 a. 若插入节点的父节点是黑色则不会破坏红黑树的性质插入后树依然保持平衡。 b. 若插入节点的父节点是红色则需要进一步考虑调整。 c. 当插入节点的叔节点父节点的兄弟节点也是红色时需要进行重新着色将父节点和叔节点设为黑色祖父节点设为红色并将祖父节点作为当前节点继续处理。 d. 当插入节点的叔节点是黑色或者缺失时需要进行旋转操作。
例如 #mermaid-svg-K6FgOT7WmwmT9Lnx {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-K6FgOT7WmwmT9Lnx .error-icon{fill:#552222;}#mermaid-svg-K6FgOT7WmwmT9Lnx .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-K6FgOT7WmwmT9Lnx .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-K6FgOT7WmwmT9Lnx .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-K6FgOT7WmwmT9Lnx .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-K6FgOT7WmwmT9Lnx .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-K6FgOT7WmwmT9Lnx .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-K6FgOT7WmwmT9Lnx .marker{fill:#333333;stroke:#333333;}#mermaid-svg-K6FgOT7WmwmT9Lnx .marker.cross{stroke:#333333;}#mermaid-svg-K6FgOT7WmwmT9Lnx svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-K6FgOT7WmwmT9Lnx .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-K6FgOT7WmwmT9Lnx .cluster-label text{fill:#333;}#mermaid-svg-K6FgOT7WmwmT9Lnx .cluster-label span{color:#333;}#mermaid-svg-K6FgOT7WmwmT9Lnx .label text,#mermaid-svg-K6FgOT7WmwmT9Lnx span{fill:#333;color:#333;}#mermaid-svg-K6FgOT7WmwmT9Lnx .node rect,#mermaid-svg-K6FgOT7WmwmT9Lnx .node circle,#mermaid-svg-K6FgOT7WmwmT9Lnx .node ellipse,#mermaid-svg-K6FgOT7WmwmT9Lnx .node polygon,#mermaid-svg-K6FgOT7WmwmT9Lnx .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-K6FgOT7WmwmT9Lnx .node .label{text-align:center;}#mermaid-svg-K6FgOT7WmwmT9Lnx .node.clickable{cursor:pointer;}#mermaid-svg-K6FgOT7WmwmT9Lnx .arrowheadPath{fill:#333333;}#mermaid-svg-K6FgOT7WmwmT9Lnx .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-K6FgOT7WmwmT9Lnx .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-K6FgOT7WmwmT9Lnx .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-K6FgOT7WmwmT9Lnx .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-K6FgOT7WmwmT9Lnx .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-K6FgOT7WmwmT9Lnx .cluster text{fill:#333;}#mermaid-svg-K6FgOT7WmwmT9Lnx .cluster span{color:#333;}#mermaid-svg-K6FgOT7WmwmT9Lnx div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-K6FgOT7WmwmT9Lnx :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 右旋 插入节点 8 8 10 14 20 nil 调整后 8 10 14 nil 20 旋转操作旋转操作主要包括左旋和右旋。 a. 左旋当插入节点在父节点的右子树中且插入节点的父节点和祖父节点都为红色时需要进行左旋操作以保持平衡。 b. 右旋当插入节点在父节点的左子树中且插入节点的父节点和祖父节点都为红色时需要进行右旋操作以保持平衡。
3.2、AVL树的插入操作和平衡性维护
AVL树是一种自平衡二叉搜索树与红黑树类似它也需要在插入操作后保持平衡性。AVL树通过旋转操作来维护平衡性但与红黑树不同的是AVL树使用不同类型的旋转左旋、右旋、左右旋、右左旋。
AVL树的插入操作和平衡性维护步骤如下 插入新节点首先按照二叉搜索树的规则将新节点插入到AVL树中。 自底向上更新高度从插入点开始沿着插入路径向上更新所有父节点的高度直到达到根节点。AVL树的高度是左子树高度和右子树高度中较大值加1。 检查平衡因子在更新高度后从插入点向上检查每个节点的平衡因子平衡因子定义为节点的左子树高度减去右子树高度。 平衡维护如果发现某个节点的平衡因子不满足平衡性要求平衡因子的绝对值大于1则需要进行相应的旋转操作来重新平衡这个节点的子树。 a. 左旋LL旋转当一个节点的左子树高度比右子树高度多2或以上时且插入操作发生在左子树的左子树左-左情况执行左旋操作。 b. 右旋RR旋转当一个节点的右子树高度比左子树高度多2或以上时且插入操作发生在右子树的右子树右-右情况执行右旋操作。 c. 左右旋LR旋转当一个节点的左子树高度比右子树高度多2或以上时且插入操作发生在左子树的右子树左-右情况执行左旋后再执行右旋操作。 d. 右左旋RL旋转当一个节点的右子树高度比左子树高度多2或以上时且插入操作发生在右子树的左子树右-左情况执行右旋后再执行左旋操作。
注意每次进行旋转后需要更新涉及节点的高度。 递归完成旋转后可能会影响到更上层节点的平衡性所以需要继续向上检查和递归地执行旋转操作直到达到根节点。 最终平衡在整个插入和旋转操作完成后AVL树的平衡性得到维护。
图解示例
原始AVL树平衡因子用数字表示 #mermaid-svg-P72FdY3e7qkhFMqT {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-P72FdY3e7qkhFMqT .error-icon{fill:#552222;}#mermaid-svg-P72FdY3e7qkhFMqT .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-P72FdY3e7qkhFMqT .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-P72FdY3e7qkhFMqT .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-P72FdY3e7qkhFMqT .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-P72FdY3e7qkhFMqT .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-P72FdY3e7qkhFMqT .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-P72FdY3e7qkhFMqT .marker{fill:#333333;stroke:#333333;}#mermaid-svg-P72FdY3e7qkhFMqT .marker.cross{stroke:#333333;}#mermaid-svg-P72FdY3e7qkhFMqT svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-P72FdY3e7qkhFMqT .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-P72FdY3e7qkhFMqT .cluster-label text{fill:#333;}#mermaid-svg-P72FdY3e7qkhFMqT .cluster-label span{color:#333;}#mermaid-svg-P72FdY3e7qkhFMqT .label text,#mermaid-svg-P72FdY3e7qkhFMqT span{fill:#333;color:#333;}#mermaid-svg-P72FdY3e7qkhFMqT .node rect,#mermaid-svg-P72FdY3e7qkhFMqT .node circle,#mermaid-svg-P72FdY3e7qkhFMqT .node ellipse,#mermaid-svg-P72FdY3e7qkhFMqT .node polygon,#mermaid-svg-P72FdY3e7qkhFMqT .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-P72FdY3e7qkhFMqT .node .label{text-align:center;}#mermaid-svg-P72FdY3e7qkhFMqT .node.clickable{cursor:pointer;}#mermaid-svg-P72FdY3e7qkhFMqT .arrowheadPath{fill:#333333;}#mermaid-svg-P72FdY3e7qkhFMqT .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-P72FdY3e7qkhFMqT .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-P72FdY3e7qkhFMqT .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-P72FdY3e7qkhFMqT .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-P72FdY3e7qkhFMqT .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-P72FdY3e7qkhFMqT .cluster text{fill:#333;}#mermaid-svg-P72FdY3e7qkhFMqT .cluster span{color:#333;}#mermaid-svg-P72FdY3e7qkhFMqT div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-P72FdY3e7qkhFMqT :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 原始AVL树 5 10 插入节点 3 #mermaid-svg-1Jl3aORrvlVMRGHa {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-1Jl3aORrvlVMRGHa .error-icon{fill:#552222;}#mermaid-svg-1Jl3aORrvlVMRGHa .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-1Jl3aORrvlVMRGHa .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-1Jl3aORrvlVMRGHa .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-1Jl3aORrvlVMRGHa .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-1Jl3aORrvlVMRGHa .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-1Jl3aORrvlVMRGHa .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-1Jl3aORrvlVMRGHa .marker{fill:#333333;stroke:#333333;}#mermaid-svg-1Jl3aORrvlVMRGHa .marker.cross{stroke:#333333;}#mermaid-svg-1Jl3aORrvlVMRGHa svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-1Jl3aORrvlVMRGHa .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-1Jl3aORrvlVMRGHa .cluster-label text{fill:#333;}#mermaid-svg-1Jl3aORrvlVMRGHa .cluster-label span{color:#333;}#mermaid-svg-1Jl3aORrvlVMRGHa .label text,#mermaid-svg-1Jl3aORrvlVMRGHa span{fill:#333;color:#333;}#mermaid-svg-1Jl3aORrvlVMRGHa .node rect,#mermaid-svg-1Jl3aORrvlVMRGHa .node circle,#mermaid-svg-1Jl3aORrvlVMRGHa .node ellipse,#mermaid-svg-1Jl3aORrvlVMRGHa .node polygon,#mermaid-svg-1Jl3aORrvlVMRGHa .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-1Jl3aORrvlVMRGHa .node .label{text-align:center;}#mermaid-svg-1Jl3aORrvlVMRGHa .node.clickable{cursor:pointer;}#mermaid-svg-1Jl3aORrvlVMRGHa .arrowheadPath{fill:#333333;}#mermaid-svg-1Jl3aORrvlVMRGHa .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-1Jl3aORrvlVMRGHa .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-1Jl3aORrvlVMRGHa .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-1Jl3aORrvlVMRGHa .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-1Jl3aORrvlVMRGHa .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-1Jl3aORrvlVMRGHa .cluster text{fill:#333;}#mermaid-svg-1Jl3aORrvlVMRGHa .cluster span{color:#333;}#mermaid-svg-1Jl3aORrvlVMRGHa div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-1Jl3aORrvlVMRGHa :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 插入节点 3 3 10 5 插入节点 2破坏平衡 #mermaid-svg-8qHRbn9uC85aGcpY {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-8qHRbn9uC85aGcpY .error-icon{fill:#552222;}#mermaid-svg-8qHRbn9uC85aGcpY .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-8qHRbn9uC85aGcpY .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-8qHRbn9uC85aGcpY .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-8qHRbn9uC85aGcpY .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-8qHRbn9uC85aGcpY .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-8qHRbn9uC85aGcpY .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-8qHRbn9uC85aGcpY .marker{fill:#333333;stroke:#333333;}#mermaid-svg-8qHRbn9uC85aGcpY .marker.cross{stroke:#333333;}#mermaid-svg-8qHRbn9uC85aGcpY svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-8qHRbn9uC85aGcpY .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-8qHRbn9uC85aGcpY .cluster-label text{fill:#333;}#mermaid-svg-8qHRbn9uC85aGcpY .cluster-label span{color:#333;}#mermaid-svg-8qHRbn9uC85aGcpY .label text,#mermaid-svg-8qHRbn9uC85aGcpY span{fill:#333;color:#333;}#mermaid-svg-8qHRbn9uC85aGcpY .node rect,#mermaid-svg-8qHRbn9uC85aGcpY .node circle,#mermaid-svg-8qHRbn9uC85aGcpY .node ellipse,#mermaid-svg-8qHRbn9uC85aGcpY .node polygon,#mermaid-svg-8qHRbn9uC85aGcpY .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-8qHRbn9uC85aGcpY .node .label{text-align:center;}#mermaid-svg-8qHRbn9uC85aGcpY .node.clickable{cursor:pointer;}#mermaid-svg-8qHRbn9uC85aGcpY .arrowheadPath{fill:#333333;}#mermaid-svg-8qHRbn9uC85aGcpY .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-8qHRbn9uC85aGcpY .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-8qHRbn9uC85aGcpY .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-8qHRbn9uC85aGcpY .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-8qHRbn9uC85aGcpY .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-8qHRbn9uC85aGcpY .cluster text{fill:#333;}#mermaid-svg-8qHRbn9uC85aGcpY .cluster span{color:#333;}#mermaid-svg-8qHRbn9uC85aGcpY div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-8qHRbn9uC85aGcpY :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 插入节点 3 2 3 10 5 由于节点 5 的平衡因子为 2需要进行旋转操作来恢复平衡。进行左旋转 #mermaid-svg-R3tfnwujFsx7st2x {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-R3tfnwujFsx7st2x .error-icon{fill:#552222;}#mermaid-svg-R3tfnwujFsx7st2x .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-R3tfnwujFsx7st2x .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-R3tfnwujFsx7st2x .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-R3tfnwujFsx7st2x .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-R3tfnwujFsx7st2x .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-R3tfnwujFsx7st2x .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-R3tfnwujFsx7st2x .marker{fill:#333333;stroke:#333333;}#mermaid-svg-R3tfnwujFsx7st2x .marker.cross{stroke:#333333;}#mermaid-svg-R3tfnwujFsx7st2x svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-R3tfnwujFsx7st2x .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-R3tfnwujFsx7st2x .cluster-label text{fill:#333;}#mermaid-svg-R3tfnwujFsx7st2x .cluster-label span{color:#333;}#mermaid-svg-R3tfnwujFsx7st2x .label text,#mermaid-svg-R3tfnwujFsx7st2x span{fill:#333;color:#333;}#mermaid-svg-R3tfnwujFsx7st2x .node rect,#mermaid-svg-R3tfnwujFsx7st2x .node circle,#mermaid-svg-R3tfnwujFsx7st2x .node ellipse,#mermaid-svg-R3tfnwujFsx7st2x .node polygon,#mermaid-svg-R3tfnwujFsx7st2x .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-R3tfnwujFsx7st2x .node .label{text-align:center;}#mermaid-svg-R3tfnwujFsx7st2x .node.clickable{cursor:pointer;}#mermaid-svg-R3tfnwujFsx7st2x .arrowheadPath{fill:#333333;}#mermaid-svg-R3tfnwujFsx7st2x .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-R3tfnwujFsx7st2x .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-R3tfnwujFsx7st2x .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-R3tfnwujFsx7st2x .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-R3tfnwujFsx7st2x .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-R3tfnwujFsx7st2x .cluster text{fill:#333;}#mermaid-svg-R3tfnwujFsx7st2x .cluster span{color:#333;}#mermaid-svg-R3tfnwujFsx7st2x div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-R3tfnwujFsx7st2x :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 插入节点 3 2 3 10 5 最终平衡的AVL树 #mermaid-svg-elcYJV1oTdcD7ObW {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-elcYJV1oTdcD7ObW .error-icon{fill:#552222;}#mermaid-svg-elcYJV1oTdcD7ObW .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-elcYJV1oTdcD7ObW .edge-thickness-normal{stroke-width:2px;}#mermaid-svg-elcYJV1oTdcD7ObW .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-elcYJV1oTdcD7ObW .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-elcYJV1oTdcD7ObW .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-elcYJV1oTdcD7ObW .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-elcYJV1oTdcD7ObW .marker{fill:#333333;stroke:#333333;}#mermaid-svg-elcYJV1oTdcD7ObW .marker.cross{stroke:#333333;}#mermaid-svg-elcYJV1oTdcD7ObW svg{font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-elcYJV1oTdcD7ObW .label{font-family:"trebuchet ms",verdana,arial,sans-serif;color:#333;}#mermaid-svg-elcYJV1oTdcD7ObW .cluster-label text{fill:#333;}#mermaid-svg-elcYJV1oTdcD7ObW .cluster-label span{color:#333;}#mermaid-svg-elcYJV1oTdcD7ObW .label text,#mermaid-svg-elcYJV1oTdcD7ObW span{fill:#333;color:#333;}#mermaid-svg-elcYJV1oTdcD7ObW .node rect,#mermaid-svg-elcYJV1oTdcD7ObW .node circle,#mermaid-svg-elcYJV1oTdcD7ObW .node ellipse,#mermaid-svg-elcYJV1oTdcD7ObW .node polygon,#mermaid-svg-elcYJV1oTdcD7ObW .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-elcYJV1oTdcD7ObW .node .label{text-align:center;}#mermaid-svg-elcYJV1oTdcD7ObW .node.clickable{cursor:pointer;}#mermaid-svg-elcYJV1oTdcD7ObW .arrowheadPath{fill:#333333;}#mermaid-svg-elcYJV1oTdcD7ObW .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-elcYJV1oTdcD7ObW .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-elcYJV1oTdcD7ObW .edgeLabel{background-color:#e8e8e8;text-align:center;}#mermaid-svg-elcYJV1oTdcD7ObW .edgeLabel rect{opacity:0.5;background-color:#e8e8e8;fill:#e8e8e8;}#mermaid-svg-elcYJV1oTdcD7ObW .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-elcYJV1oTdcD7ObW .cluster text{fill:#333;}#mermaid-svg-elcYJV1oTdcD7ObW .cluster span{color:#333;}#mermaid-svg-elcYJV1oTdcD7ObW div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-elcYJV1oTdcD7ObW :root{--mermaid-font-family:"trebuchet ms",verdana,arial,sans-serif;} 插入节点 3 2 3 10 5 与红黑树相比AVL树的平衡性维护相对严格因为它要求节点的左右子树高度差不能超过1。这也使得在插入操作频繁的情况下红黑树的性能可能更优因为红黑树在牺牲一定的平衡性的前提下保证了插入和删除操作的时间复杂度为O(logN)。而AVL树的旋转操作可能会频繁地触发导致额外的开销。
3.3、分析并对比两种树在插入操作中的性能差异
红黑树Red-Black Tree和AVL树Adelson-Velsky and Landis Tree都是自平衡二叉搜索树用于保持树的平衡性以保证各种操作插入、删除、查找等的时间复杂度在较低的范围内。然而它们在自平衡的方式和性能方面有一些不同之处特别是在插入操作中。
自平衡策略不同 红黑树 红黑树通过维护五个重要的性质来保持平衡其中包括节点的颜色红色或黑色和一些限制条件确保了从根到任意叶子节点的最长路径不会超过最短路径的两倍。插入操作可能会引发颜色变换和旋转操作来保持这些性质。 AVL树 AVL树通过在每个节点上维护一个平衡因子左子树高度减去右子树高度来保持平衡。插入操作可能会导致旋转操作以使平衡因子保持在特定的范围内通常是-1、0或1。
插入操作性能
红黑树 由于红黑树的自平衡策略相对较为宽松插入操作的性能一般来说会比AVL树更好。虽然插入后可能需要进行颜色变换和旋转但是这些操作的数量较少平均情况下仍然能够维持较低的时间复杂度。AVL树 AVL树对于插入操作来说是相对严格的因为它要求保持平衡因子的绝对值不超过1。这意味着在插入操作后可能需要进行更多的旋转操作来调整树的结构以满足平衡要求。这可能会导致插入操作的性能相对较差尤其是在频繁插入的情况下。
在插入操作方面红黑树通常比AVL树具有更好的性能。但需要注意的是性能差异在不同情况下可能会有所变化因为实际性能还受到其他因素的影响如具体的插入顺序、硬件性能等。
3.3.1、实现一个AVL树进行一万次数据插入
#include stdio.h
#include stdlib.h
#include sys/time.h
// AVL树节点结构
struct Node {int key;struct Node* left;struct Node* right;int height;
};// 获取节点的高度
int getHeight(struct Node* node) {if (node NULL) {return 0;}return node-height;
}// 获取两个整数中的较大值
int max(int a, int b) {return (a b) ? a : b;
}// 创建新节点
struct Node* newNode(int key) {struct Node* node (struct Node*)malloc(sizeof(struct Node));node-key key;node-left NULL;node-right NULL;node-height 1;return node;
}// 右旋操作
struct Node* rightRotate(struct Node* y) {struct Node* x y-left;struct Node* T2 x-right;x-right y;y-left T2;y-height max(getHeight(y-left), getHeight(y-right)) 1;x-height max(getHeight(x-left), getHeight(x-right)) 1;return x;
}// 左旋操作
struct Node* leftRotate(struct Node* x) {struct Node* y x-right;struct Node* T2 y-left;y-left x;x-right T2;x-height max(getHeight(x-left), getHeight(x-right)) 1;y-height max(getHeight(y-left), getHeight(y-right)) 1;return y;
}// 获取平衡因子
int getBalanceFactor(struct Node* node) {if (node NULL) {return 0;}return getHeight(node-left) - getHeight(node-right);
}if (node NULL) {return newNode(key);} if (key node-key) {node-left insert(node-left, key);} else if (key node-key) {node-right insert(node-right, key);} else {return node; // 不允许插入相同的键值} node-height 1 max(getHeight(node-left), getHeight(node-right));int balance getBalanceFactor(node);// 左-左情况if (balance 1 key node-left-key) {return rightRotate(node);} // 右-右情况if (balance -1 key node-right-key) {return leftRotate(node);} // 左-右情况if (balance 1 key node-left-key) {node-left leftRotate(node-left);return rightRotate(node);} // 右-左情况if (balance -1 key node-right-key) {node-right rightRotate(node-right); return leftRotate(node);} return node;
} // 获取树的高度
int treeHeight(struct Node* node) {if (node NULL) {return 0;}return node-height;
}int main() {struct Node* root NULL;struct timeval start_time, end_time;long long start_microseconds, end_microseconds, elapsed_microseconds;// 获取起始时间gettimeofday(start_time, NULL);start_microseconds start_time.tv_sec * 1000000 start_time.tv_usec;// 进行10000次插入操作for (int i 1; i 10000; i) {root insert(root, i);}// 获取结束时间gettimeofday(end_time, NULL);end_microseconds end_time.tv_sec * 1000000 end_time.tv_usec;// 计算时间差elapsed_microseconds end_microseconds - start_microseconds;printf(Time taken: %lld microseconds\n, elapsed_microseconds);// 打印树的高度printf(树的高度: %d\n, treeHeight(root));return 0;
}
执行结果
Time taken: 2498 microseconds
树的高度: 143.3.2、实现一个红黑树进行一万次数据插入
#include stdio.h
#include stdlib.h
#include sys/time.h
typedef enum Color {RED,BLACK
} Color;typedef struct Node {int data;Color color;struct Node* parent;struct Node* left;struct Node* right;
} Node;Node* createNode(int data) {Node* newNode (Node*)malloc(sizeof(Node));newNode-data data;newNode-color RED; // New nodes are always red initiallynewNode-parent NULL;newNode-left NULL;newNode-right NULL;return newNode;
}void leftRotate(Node** root, Node* x) {Node* 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(Node** root, Node* y) {Node* 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(Node** root, Node* z) {while (z-parent ! NULL z-parent-color RED) {if (z-parent z-parent-parent-left) {Node* y z-parent-parent-right;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-right) {z z-parent;leftRotate(root, z);}z-parent-color BLACK;z-parent-parent-color RED;rightRotate(root, z-parent-parent);}} else {Node* 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(Node** root, int data) {Node* z createNode(data);Node* y NULL;Node* x *root;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 inorderTraversal(Node* root) {if (root ! NULL) {inorderTraversal(root-left);printf(%d , root-data);inorderTraversal(root-right);}
}int max(int a, int b) {return (a b) ? a : b;
}int blackHeight(Node* node) {if (node NULL)return 1;int leftHeight blackHeight(node-left);int rightHeight blackHeight(node-right);if (leftHeight 0 || rightHeight 0 || leftHeight ! rightHeight)return 0;return leftHeight ((node-color BLACK) ? 1 : 0);
}int getBlackHeight(Node* root) {if (root NULL)return 0;return blackHeight(root-left);
}int main() {Node* root NULL;struct timeval start_time, end_time;long long start_microseconds, end_microseconds, elapsed_microseconds;// 获取起始时间gettimeofday(start_time, NULL);start_microseconds start_time.tv_sec * 1000000 start_time.tv_usec;// 进行10000次插入操作for (int i 1; i 10000; i) {insert(root, i);}// 获取结束时间gettimeofday(end_time, NULL);end_microseconds end_time.tv_sec * 1000000 end_time.tv_usec;// 计算时间差elapsed_microseconds end_microseconds - start_microseconds;printf(Time taken: %lld microseconds\n, elapsed_microseconds);// printf(Inorder traversal of the Red-Black Tree:\n);// inorderTraversal(root);// printf(\n);int height getBlackHeight(root);printf(Black height of the Red-Black Tree: %d\n, height);return 0;
}
执行结果
Time taken: 2494 microseconds
Black height of the Red-Black Tree: 123.4、红黑树相对于AVL树的优势
红黑树和AVL树都是自平衡二叉搜索树它们在保持二叉搜索树的性质的同时通过旋转和节点操作来保持树的平衡。虽然它们都有类似的目标但在某些方面红黑树相对于AVL树有一些优势主要体现在以下几点 插入和删除操作的效率 红黑树相对于AVL树的主要优势之一是在插入和删除操作上更为高效。红黑树的平衡要求相对较松因此插入和删除操作可能需要更少的旋转从而减少了平衡操作的次数。而AVL树由于平衡要求较为严格可能需要更频繁的旋转来维持平衡导致插入和删除操作相对较慢。 空间开销 红黑树相对于AVL树在存储平衡信息方面具有优势。红黑树只需要一个比特来存储节点的颜色信息红或黑而AVL树需要存储每个节点的平衡因子通常需要更多的空间。 查询性能 在纯粹的查询操作上AVL树可能略微优于红黑树因为AVL树的平衡要求更严格可能导致树更加扁平从而在某些情况下查找效率略高。
四、查找和遍历操作的效率比较
4.1、红黑树的查找和遍历操作
红黑树是一种平衡的二叉搜索树。其查找和遍历操作与普通的二叉搜索树类似但是由于红黑树的特性其最坏的查找时间复杂度是O(log n)。
1查找操作: 查找操作在红黑树中非常简单。如果我们要查找一个值k我们可以从根节点开始
如果k等于当前节点的值查找成功。如果k小于当前节点的值转到左子树。如果k大于当前节点的值转到右子树。如果当前节点为空则查找失败。
Node* search(Node* root, int k) {while (root ! NULL) {if (k root-data)return root;else if (k root-data)root root-left;elseroot root-right;}return NULL; // Value not found
}2遍历操作: 红黑树的遍历可以分为前序、中序和后序遍历与普通二叉搜索树的遍历方法相同。
中序遍历In-order: 左子树 - 当前节点 - 右子树前序遍历Pre-order: 当前节点 - 左子树 - 右子树后序遍历Post-order: 左子树 - 右子树 - 当前节点
例如中序遍历的代码可以是这样的
void inorderTraversal(Node* root) {if (root NULL)return;inorderTraversal(root-left);printf(%d , root-data);inorderTraversal(root-right);
}4.2、AVL树的查找和遍历操作
1查找操作
步骤1从根节点开始与待查找值进行比较。步骤2如果待查找值等于当前节点的值则返回该节点。步骤3如果待查找值小于当前节点的值则继续在左子树中递归查找。步骤4如果待查找值大于当前节点的值则继续在右子树中递归查找。步骤5如果遍历完整个树仍未找到相应节点则说明该节点不存在。
typedef struct Node {int value;struct Node* left;struct Node* right;int height;
} Node;Node* search(Node* root, int target) {if (root NULL || target root-value) {return root;}if (target root-value) {return search(root-left, target);}return search(root-right, target);
}
2遍历操作
前序遍历根节点 - 左子树 - 右子树中序遍历左子树 - 根节点 - 右子树后序遍历左子树 - 右子树 - 根节点
void preorderTraversal(Node* root) {if (root ! NULL) {printf(%d , root-value);preorderTraversal(root-left);preorderTraversal(root-right);}
}void inorderTraversal(Node* root) {if (root ! NULL) {inorderTraversal(root-left);printf(%d , root-value);inorderTraversal(root-right);}
}void postorderTraversal(Node* root) {if (root ! NULL) {postorderTraversal(root-left);postorderTraversal(root-right);printf(%d , root-value);}
}
4.3、对比两种树在查找和遍历操作中的性能差异
1查找操作 平均情况下红黑树和AVL树的查找操作都具有O(log n)的时间复杂度其中n是树中节点的数量。这是由于它们都是二叉搜索树结构每次查找可以通过比较节点的键值来确定目标节点的位置并且树的平衡性质保证了查找路径的长度接近树的高度。
2遍历操作 前序、中序和后序遍历对于红黑树和AVL树而言在时间复杂度上没有显著差异。这是因为无论是红黑树还是AVL树遍历操作都需要访问每个节点一次并以相同的顺序输出节点的值所以它们的时间复杂度都是O(n)其中n是树中节点的数量。
红黑树和AVL树在查找和遍历操作的性能方面没有太大差异。它们的主要区别在于维护平衡的方式和性质要求。
五、内存占用和空间复杂性比较
5.1、红黑树的内存占用特点
红黑树相对于其他平衡树结构来说在内存占用方面有以下特点 相对于AVL树红黑树在保持树的平衡性方面放宽了平衡要求通过一些特定的性质来维持近似平衡。这使得红黑树的高度可能稍微比AVL树更大因此红黑树可能需要更多的内存空间来存储相同数量的节点。 比较其他平衡树结构相对于一些其他平衡树结构如B树或B树等红黑树通常会占用更多的内存空间。红黑树中每个节点都需要保存颜色信息一般使用一个额外的位来表示红色或黑色而其他平衡树结构可能只需要保存键值和指针信息。
红黑树相对于其他平衡树结构在内存占用方面可能略高但其在平衡性和时间复杂度上的优势使得它依然是一个被广泛使用的数据结构。
5.2、AVL树的内存占用特点
相对于其他平衡树结构AVL树在内存占用方面有以下特点 节点结构AVL树的每个节点通常需要保存键值、指向左右子树的指针以及平衡因子即左右子树的高度差。这些额外的信息会增加每个节点的内存消耗。 平衡因子AVL树中的平衡因子可以是一个整数或枚举类型需要额外的空间来存储。一般情况下平衡因子使用8位或更少的比特位表示所以占用的额外内存很小。 平衡维护AVL树为了维持平衡性可能需要进行旋转操作来调整树的结构。这些旋转操作本身并不会引入额外的内存消耗但在执行旋转操作过程中需要使用一些临时变量这些临时变量的内存开销可能较小。
AVL树相对于其他平衡树结构来说在内存占用方面没有显著的差异。它们都需要为每个节点保存一定的键值和指针信息并且可能需要一些额外的信息来维持平衡。真正影响内存占用的因素更多地取决于具体实现的细节例如节点结构的大小和平衡因子的表示方式等。
5.3、对比两种树在内存占用和空间复杂性方面的优势
1内存占用
AVL树相对于红黑树来说每个节点需要额外存储平衡因子来维持严格的平衡。这使得AVL树在内存占用上略高于红黑树。红黑树相对于AVL树来说由于放宽了平衡要求不需要额外存储平衡因子。因此在相同数量的节点下红黑树的总体内存占用可能略低于AVL树。
空间复杂性 平均情况下红黑树和AVL树在插入、删除和查找操作的时间复杂度都是O(log n)其中n是树中节点的数量。这意味着它们在空间复杂性上没有显著差异。 但是红黑树相对于AVL树有更松散的平衡要求可以忍受一定程度的不平衡因此在频繁地插入和删除操作时红黑树可能更具优势因为其自平衡操作的代价较低。
红黑树和AVL树在内存占用和空间复杂性方面有不同的优势
AVL树在内存占用上可能稍高但在查找操作上更稳定且具备严格的平衡性。红黑树在内存占用上相对较低且适合于频繁的插入和删除操作。
六、性能优化和应用场景
6.1、如何根据具体应用场景选择合适的树结构
1二叉搜索树 (BST)
优点适用于快速查找、插入和删除操作。中序遍历可以得到有序序列。适用场景当需要频繁进行查找和动态插入/删除操作时。然而原始的BST可能会变得不平衡导致性能下降。
2AVL树
优点自平衡的BST保证了树的高度较小因此查找、插入和删除操作的时间复杂度都保持在对数级别。适用场景当需要高效的平衡树结构以确保各种操作的稳定性能时。但由于自平衡操作可能会带来一些额外开销因此在插入和删除操作频繁的情况下可能会略微降低性能。
3红黑树
优点与AVL树类似是一种自平衡的BST但相对于AVL树红黑树的自平衡操作更简单插入和删除操作的代价较小。适用场景在需要保持相对平衡的同时对于插入和删除操作的性能要求较高的场景。
3B树和B树
优点这些树结构被设计用于在磁盘等外部存储上进行高效的数据存储和检索。B树适合随机访问B树适合范围查询。适用场景数据库索引、文件系统等需要在外部存储上组织数据的场景。
4Trie树前缀树
优点适用于高效地存储和查找字符串数据。特别适合用于搜索和自动补全等字符串相关的应用。适用场景字典、搜索引擎、拼写检查等需要处理字符串的场景。
5堆
优点用于高效地获取最大或最小元素。堆排序、优先队列等算法基于堆实现。适用场景调度算法、最短路径算法、动态选取最值等需要优先级管理的场景。
在选择合适的树结构时要考虑数据操作的频率、特点以及数据的插入、删除和查找等操作的性能需求。没有一种树结构适用于所有情况。。
6.2、红黑树的优化策略 局部性优化在进行插入、删除等操作时可以尽量减少树的旋转和重新着色操作以降低操作的开销。例如在插入元素时可以通过旋转和着色操作来保持树的平衡但不一定非得追求完美平衡可以在一定程度上容忍一些不平衡从而减少调整的次数。 批量操作如果需要执行大量的插入或删除操作可以采用一种叫做“延迟删除”的策略。即先将要删除的节点标记为删除而不立即删除它而是等到执行一次大规模调整操作时再一并删除这样可以减少频繁的调整操作。 自适应调整根据实际数据的特点和操作模式可以动态地调整某些操作的策略。例如对于频繁访问的节点可以将它们置于树的较浅层以加快访问速度。 优化旋转操作在红黑树的插入和删除过程中可能需要进行旋转操作来保持平衡。优化旋转操作的方式包括路径压缩将中间节点向上移动减少旋转操作的次数和双旋转等。 缓存友好性在实际应用中可以考虑红黑树的节点布局使得相邻节点在内存中也是相邻的以提高缓存的命中率从而加速树的访问。 扩展功能根据实际需求可以对红黑树进行一些功能扩展例如添加范围查询、区间更新等操作以满足特定场景下的需求。
6.3、AVL树的优化策略
虽然AVL树本身已经具备较好的平衡性能但在某些特定的应用场景下仍然可以考虑一些优化策略来进一步提高性能。 延迟更新在AVL树的插入和删除操作中可能会涉及多次旋转来保持平衡这会带来一些性能开销。延迟更新策略可以在一次操作结束后再进行平衡因子的更新和旋转操作从而减少不必要的操作次数。 局部重构在插入和删除操作中如果发现某个节点的平衡因子超过了允许的范围可以考虑对该节点及其祖先节点进行局部重构以避免多次单旋转。这可以减少整体的旋转次数提高性能。 批量操作如果需要对AVL树进行一系列的插入或删除操作可以将这些操作批量执行然后再一次性进行平衡操作。这样可以减少多次单独操作带来的开销提高整体效率。 局部性优化类似于红黑树中的缓存友好性可以考虑优化AVL树节点的布局使得相邻节点在内存中也是相邻的。这有助于提高缓存的命中率加速树的访问。 自适应调整根据实际应用中的数据分布和操作频率可以考虑调整平衡因子的阈值使得树的平衡调整更加自适应从而在不同情况下都能保持较好的性能。
6.4、实际应用中红黑树胜过AVL树的案例和场景 插入和删除操作频繁的情况红黑树的平衡因子要求相对宽松一些相比AVL树更容易维护平衡这在频繁执行插入和删除操作的场景下可能会表现更好。例如文件系统中的目录结构维护、数据库的索引维护等。 读操作远多于写操作的情况红黑树的平衡调整次数相对较少因此在读取操作明显多于写入操作的场景中红黑树可能更适合因为它不会频繁执行复杂的平衡旋转操作从而减少了开销。 内存限制下的应用AVL树因为需要维护严格的平衡可能会导致树的高度相对较低这在存储大量数据时可能占用更多的内存。而红黑树在平衡和内存占用之间有更好的权衡适用于内存有限的环境。 实时应用在需要快速的插入和删除操作的实时应用中红黑树的平衡特性可能更适合因为它可以在一定程度上保持树的相对平衡避免频繁的旋转操作。
红黑树和AVL树都有各自的优势和劣势并且选择合适的数据结构要根据具体的应用需求来决定。在某些情况下红黑树可能更适合但在其他情况下AVL树可能表现更好。最终的选择应该基于性能需求、内存限制以及具体操作的频率和类型来进行权衡。
总结
在文章中着重比较红黑树和AVL树在插入、删除、查找、遍历以及内存占用等方面的性能指出红黑树在某些应用场景下优于AVL树。同时还将探讨两种树的优化策略和实际应用案例。
红黑树相对于AVL树的综合优势主要体现在以下几个方面 插入和删除操作的性能 红黑树在保持相对平衡的同时对于插入和删除操作的性能表现通常优于AVL树。虽然AVL树的平衡性更为严格但在插入和删除时需要更频繁地进行旋转操作而红黑树通过放宽平衡要求减少了旋转的次数从而在实际应用中可能更快速地处理这些操作。 内存占用 红黑树相对于AVL树在维护平衡时要求更少的额外信息因此通常会占用更少的内存。这使得红黑树在内存有限的情况下表现更优。 实时应用 在需要快速插入和删除操作的实时应用中红黑树的平衡特性可能更适合因为它可以在一定程度上维护树的平衡性避免过度频繁的平衡操作。 适应性 红黑树的相对宽松的平衡要求使得它对于动态变化的数据集更具有适应性。当数据集的变化幅度较大而不仅仅是顺序插入时红黑树可能更容易维持相对平衡。
在这里插入图片描述
