Skip to main content

红黑树

红黑树的实现原理​

红黑树是一种自平衡二叉搜索树，它在每个节点上增加了一个存储位表示节点的颜色，可以是红(Red)或黑(Black)。红黑树的实现原理是通过对任何一条从根到叶子的路径上各个节点的颜色进行约束，从而确保没有路径会比其他路径长出两倍，因此是近似平衡的。它维护以下性质：

  1. 节点颜色：每个节点要么是红色，要么是黑色。
  2. 根节点是黑色：树的根节点总是黑色的。
  3. 所有叶子节点是黑色：这里的叶子节点指的是空的叶子节点（NIL节点），它们都是黑色的。
  4. 红色节点的子节点必须是黑色：也就是说，两个红色节点不能相邻。
  5. 任何一个节点到其每个叶子节点的所有路径都包含相同数目的黑色节点：这也被称为“黑色完美平衡”。

当通过插入或删除节点破坏了这些性质时，红黑树通过旋转和重新着色节点来进行修正，从而恢复平衡。这些操作包括：

  • 左旋（Left Rotation）：对节点进行左旋，即将节点的右子节点提升为父节点，原节点变成左子节点。
  • 右旋（Right Rotation）：对节点进行右旋，即将节点的左子节点提升为父节点，原节点变成右子节点。
  • 重新着色（Recoloring）：改变节点的颜色，以满足红黑树的性质。

通过这些操作，红黑树确保了在插入和删除操作后，树依然保持平衡，所有操作（插入、删除、查找）的最坏时间复杂度都是O(log n)。

红黑树的用途​

红黑树是一种非常通用的数据结构，它在计算机科学中有着广泛的应用，主要用途包括：

  1. 关联数组：红黑树可以用来实现关联数组数据结构，如Java中的TreeMap和TreeSet，C++ STL中的map、multimap、set和multiset。

  2. 动态数据结构：由于红黑树在插入和删除时能够快速重新平衡，它适合用作动态数据结构，可以在保持元素排序的同时，快速响应元素的插入和删除。

  3. 内存管理：一些操作系统的内存管理子系统使用红黑树来跟踪空闲内存块。

  4. 数据库：数据库系统中的索引通常使用红黑树来实现，以便快速检索数据。

  5. 实时应用：由于红黑树的操作具有可预测的时间复杂度，因此它适用于需要实时性保证的系统。

  6. 其他各种需要平衡树的场合：任何需要有序数据快速访问的场合都可能使用红黑树，例如范围查询、排序列表等。

红黑树之所以受欢迎，主要是因为它是一种自平衡的二叉搜索树，能够在数据频繁更新的情况下，仍然保持较高的搜索效率。

红黑树的结构​

想象一个二叉搜索树，其中每个节点都有一个颜色属性，可以是红色或黑色。以下是该树的一个简化表示：

    (B)10
     /   \
   (R)5  (R)15
   / \    /  \
(B)3 (B)7(B)13(B)20

在这个图中，(B)表示黑色节点，(R)表示红色节点，数字是节点的键值。这棵树满足红黑树的所有性质。

插入操作​

当插入一个新节点时，新节点总是被着色为红色。假设我们要插入键值为8的新节点，它首先会被插入到5和7之间，并着色为红色：

    (B)10
     /   \
   (R)5  (R)15
   / \    /  \
(B)3 (B)7(B)13(B)20
       \
      (R)8

这个插入可能会破坏红黑树的性质，尤其是如果父节点也是红色的话。在这种情况下，我们需要进行一系列的重新着色和旋转操作来修复树，以确保它仍然是一个有效的红黑树。

删除操作​

删除操作比插入操作更复杂，因为它可能需要多次重新平衡。当删除一个节点时，如果它有两个子节点，通常会用它的后继节点（中序遍历下的下一个节点）来替代它，然后删除后继节点。这样做可能会导致需要重新平衡树。

例如，如果我们删除上面树中的节点5，我们需要用后继节点7来替代它，然后删除7。这可能需要一系列的重新平衡操作。

旋转和重新着色​

在插入和删除操作中，我们可能需要执行以下操作来维持红黑树的性质：

  • 左旋：使一个节点成为其右子节点的左子节点。
  • 右旋：使一个节点成为其左子节点的右子节点。
  • 重新着色：改变一个或多个节点的颜色。

这些操作的目的是确保树保持平衡，并且符合红黑树的五个基本性质。

如果您需要可视化的图表，我建议使用在线资源，如可视化算法网站，或者在纸上画出节点和颜色，以更好地理解红黑树的结构和操作。

参考

  1. https://youtu.be/MNvsxKDS6II