基于红黑树的Java中TreeMap实现的说明

java treemap red-black-tree

2022-09-01 10:42:25

我正在浏览Java中TreeMap的源代码。根据 JAVA 文档：

基于红黑树的导航映射实现。地图根据其键的自然顺序进行排序，或者由地图创建时提供的比较器进行排序，具体取决于使用的构造函数。

此实现为包含密钥、获取、放置和删除操作提供有保证的日志（n）时间成本。算法是对Cormen，Leiserson和Rivest的《算法导论》中的算法的改编。

在源代码中，我发现内部类条目被用作节点。

static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left = null;
        Entry<K,V> right = null;
        Entry<K,V> parent;
        boolean color = BLACK;
        ....

至于红黑树的定义。从维基百科中我发现：

红黑树是一种自平衡的二叉搜索树，是计算机科学中使用的一种数据结构。

通过用两种颜色之一（这些颜色通常称为“红色”和“黑色”，因此树的名称）绘制每个节点来提供自平衡，从而使生成的绘制树满足某些不允许其变得明显不平衡的属性。修改树时，随后会重新排列并重新绘制新树，以恢复着色属性。这些属性的设计方式可以有效地执行这种重新排列和重新着色。

我试图分析souce代码，但无法理解以下内容：

假设我已经在树中有两个键“C”和“E”，然后我正在添加“D”。节点的排列方式（使用自然排序）。
Tree的自平衡是如何在java源代码中实现的。

我尝试搜索TreeMap的详细实现，但找不到任何文章，例如我为HashMap找到的以下文章

从昨天开始，我就挂在这棵树上:(有人可以帮我下来吗？

答案 1

的目标是创建一个键树，其中低于父项键的键位于左侧，高于父项键的键位于右侧。因此，如果您添加，那么，您将拥有以下树：TreeMapCE
```
C
 \
  E
```
如果随后添加，最初您将获得：D
```
C
 \
  E
 /
D
```
但是这棵树是不平衡的，因此搜索会更慢。因此，树被重新平衡。平衡后，树现在变得更加高效：
```
C                     C
 \        rotate       \         rotate         D
  E   --- right --->    D    ---  left --->    / \
 /        around         \       around       C   E
D           E             E        D
```
重新平衡在方法内部进行，该方法检查树的红黑色属性在插入后是否仍保持不变。而且，如果没有，那么它会重新平衡执行的树或在有问题的分支上恢复平衡。然后，它在树上移动并检查平衡，依此类推，直到到达根节点。fixAfterInsertion()rotateLeft()rotateRight()

互联网上有几个资源可以深入解释红黑树。但是，我认为理解这个过程的最好方法是遵循这样的动画教程：http://www.csanimated.com/animation.php?t=Red-black_tree

在实施RBT方面没有什么特别之处。它紧随CLRS（Cormen，Leiserson，Rivest和Stein）书中给出的伪代码，这是99%的实现所做的事情。TreeMap

答案 2