本文旨在让小白快速了解 学会红黑树的使用 和对二叉树 平衡树的基本认识 如果希望完全掌握 建议跟着我的代码然后看着图走一遍哈 方便理解
如果已经有一定基础的小伙伴可以用传送门跳到自己需要看的地方哦
1.1 二叉树基础
什么是二叉树？
二叉树是一种每个节点最多有两个子节点的树结构，通常分为左子节点和右子节点。它在数据组织、资源管理等方面有着广泛应用。
二叉树的类型
1.2 二叉树的遍历
想象我们有一个简单的二叉树，其结构如下：
这棵树的节点分布可以用emoji表示为：根节点是🌳，它的左子节点是🌿，右子节点是🌾；🌿的左子节点是🍃。
前序遍历（根左右）
前序遍历结果：🌳 → 🌿 → 🍃 → 🌾
中序遍历（左根右）
中序遍历结果：🍃 → 🌿 → 🌳 → 🌾
后序遍历（左右根）
后序遍历结果：🍃 → 🌿 → 🌾 → 🌳
层序遍历（逐层从左到右）
层序遍历结果：
1.3 实战演练：构建你的第一个二叉树
让我们动手编写一个简单的二叉树实现，并进行前序遍历：
平衡树的定义与重要性
什么是平衡树？
平衡树，顾名思义，是一种内部结构平衡的树。它确保了树的高度保持在一个低水平，从而使得增加、删除、查找等操作都能在对数时间内完成。这种平衡通过确保树的每个节点的左右子树的高度差不超过特定的值来实现。
平衡树的应用场景
平衡树广泛应用于数据库索引、文件系统、网络路由等领域，几乎在任何需要快速数据检索的场合都能见到它的身影。
2.2 AVL树：平衡树的典范
AVL树的定义
AVL树是最早被发明的自平衡二叉搜索树。在AVL树中，任意节点的两个子树的高度最大差别为1，这使得AVL树几乎是完全平衡的。
AVL树的旋转操作详解
为了维持平衡，AVL树引入了旋转操作，主要有四种类型：左旋、右旋、左右旋和右左旋。
2.3 实战演练：平衡树的构建与操作
现在，让我们来看看如何构建一个AVL树，并执行基本操作。
构建AVL树的步骤
平衡树的插入示例代码：
假设我们按顺序插入一系列的键值：9, 5, 10, 0, 6, 11, -1, 1, 2。我们将逐步展示每次插入后的树结构和必要的旋转操作。
首先，初始化AVL树并插入上述键值：
插入9：
插入5：
插入10：
插入0（无需旋转）：
插入6（无需旋转）：
插入11：
插入-1（无需旋转）：
插入1，然后进行旋转调整：
插入2，导致需要进行左右旋转（左旋在5上，然后右旋在9上）：
红黑树是一种特殊的二叉搜索树，它通过一系列的规则和调整操作来保持树的平衡，确保在最坏的情况下仍能提供良好的时间复杂度。接下来，让我们一起深入探索红黑树的奥秘。
3.1 红黑树的基本原理
红黑树的定义
红黑树是每个节点都带有颜色属性的二叉搜索树，颜色或为红色或为黑色。但它不仅仅是一个普通的二叉搜索树，它通过一系列的性质来维护树的平衡。
红黑树的性质
红黑树维持平衡的关键在于五个基本性质：
这些性质共同作用，确保了红黑树的高效性能。
3.2 红黑树的操作精讲
插入操作与调整机制
插入操作可能会破坏红黑树的性质，因此需要通过旋转和重新着色来恢复这些性质。插入操作大致可以分为以下几个步骤：
现在展示一个比较难的插入示例：
初始树长这样
现在我们要在这棵树上面插入一个3的点
因为此时3和4都是红色 并且3是左节点 而3的父节点4是一个右子节点 所以要单向向右旋转（就是上图中的4和3节点顺时针旋转）变成下图这样
但是违背了红色节点不能相邻的原则 所以需要调整
就变成这样了 这样就不违反红黑树的性质了
上方的过程我们用代码实现如下
删除操作
相信这个也是让很多小伙伴头疼的地方
删除操作是红黑树中较为复杂的一部分，因为它可能会破坏红黑树的性质。删除节点后，需要通过一系列的调整来恢复这些性质。删除操作主要分为以下几个步骤：
删除操作可能违反的红黑树性质包括：
调整过程中，我们需要处理以下几种情况：
情况1：需要删除的节点是红色
1.1如下
删除22这种情况就不用说 直接删就好了 因为他是叶节点
但如果要删除30
首先 先二分查找找到30
找到以后 往左找 找比他小的
把这个找到的替代品复制一份 赋值到他原来的节点上，然后那个原先的25就去掉了
此时违背了红色节点不能相邻的原则 所以要调整
把22变成黑色 完成
情况2：兄弟节点是黑色，且兄弟的两个子节点都是黑色
将兄弟节点染成红色，并将父节点设置为新的当前节点，继续进行调整。
情况3：兄弟节点是黑色，且兄弟的左子节点是红色，右子节点是黑色
将兄弟节点染成红色，兄弟的左子节点染成黑色，并对兄弟节点进行右旋转，这样可以转换为情况4。
情况4：兄弟节点是黑色，且兄弟的右子节点是红色
将兄弟节点染成父节点的颜色，父节点染成黑色，兄弟的右子节点染成黑色，然后对父节点进行左旋转，最后将根节点染成黑色。
下面是一个简化的代码示例，展示了如何处理这些情况：
查找操作
在红黑树中，查找操作与二叉搜索树相同 其实就是二分查找
在这个示例中，🖤 表示黑色节点，🔴 表示红色节点。这棵树满足红黑树的性质。
现在我们来搜索值为 10 的节点。
第一步：从根节点开始搜索，比较目标值 10 和当前节点值 7，由于 10 大于 7，因此我们向右子树搜索。
第二步：我们到达节点值为 18 的节点，继续比较目标值 10 和当前节点值 18，由于 10 小于 18，因此我们向左子树搜索。
第三步：我们到达节点值为 10 的节点，发现目标值和当前节点值相等，搜索结束，找到了目标节点。
下面是实现的代码
遍历操作
中序遍历
的顺序是 3, 7, 10, 18, 22。
步骤：
前序遍历
前序遍历按照根左右的顺序访问节点。
步骤：
后序遍历
后序遍历按照左右根的顺序访问节点。
步骤：
看到这你大概已经对红黑树，这个神秘而强大的数据结构有了一个清晰的认知了，它不仅要求你掌握二叉搜索树的基本操作，还需要你深入理解如何通过旋转和重新着色来维持树的平衡性！这不是普通的数据结构，这是一种充满力量和平衡之道的结构！💪🌲
要真正掌握红黑树，我们需要进入实战阶段！只有实践，才能让我们更好地掌握它！🚀
版权声明：
本文来源网络，所有图片文章版权属于原作者，如有侵权，联系删除。
本文网址：https://www.mushiming.com/mjsbk/1724.html