JAVA中TreeMap基于红黑树的实现详解

Explanation of Red-Black tree based implementation of TreeMap in JAVA

提问by Zeeshan

I was going through the source code of TreeMapin JAVA. As per JAVA doc:

我经历的源代码TreeMap的在JAVA。根据 JAVA 文档：

A Red-Black tree based NavigableMap implementation. The map is sorted according to the natural ordering of its keys, or by a Comparator provided at map creation time, depending on which constructor is used.

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

基于红黑树的 NavigableMap 实现。映射根据其键的自然顺序进行排序，或者通过映射创建时提供的 Comparator 进行排序，具体取决于使用的构造函数。

此实现为 containsKey、get、put 和 remove 操作提供有保证的 log(n) 时间成本。算法是对 Cormen、Leiserson 和 Rivest 的算法简介中的算法的改编。

In the source code I found that an Inner Class Entrywas used as a node.

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

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;
        ....

As for the defination of Red-Black tree. From Wikipedia I found:

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

A red–black tree is a type of self-balancing binary search tree, a data structure used in computer science.

The self-balancing is provided by painting each node with one of two colors (these are typically called 'red' and 'black', hence the name of the trees) in such a way that the resulting painted tree satisfies certain properties that don't allow it to become significantly unbalanced. When the tree is modified, the new tree is subsequently rearranged and repainted to restore the coloring properties. The properties are designed in such a way that this rearranging and recoloring can be performed efficiently.

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

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

I tried to analyse the souce code but couldn't understand the following:

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

1. Suppose I am already having two keys "C" and "E" in the Tree and then I am adding "D". How the nodes will be arranged (Using natural ordering).

2. How is self-balancing of Tree is implemented in the java source code.

1. 假设我已经在树中有两个键“C”和“E”，然后我添加了“D”。节点的排列方式（使用自然排序）。

2. java源代码中是如何实现Tree的自平衡的。

I tried searching for detail implementationof TreeMap but was unable to find any article such as the following articleI have found for HashMap

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

Since yesterday I am hanging on this Tree :( Can someone please help me get down...

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

采纳答案by EmirCalabuch

1. The goal of the TreeMapis to have a tree of keys where keys that are lower than the parent's key are to the left and keys higher than the parent's key are to the right. So, if you add C, then E, you will have this tree:

   C
    \
     E
   

   If you then add D, initially you will have:

   C
    \
     E
    /
   D
   

   But this tree is unbalanced and therefore searches would be slower. So, the tree is rebalanced. After balancing, the tree now becomes much more efficient:

   C                     C
    \        rotate       \         rotate         D
     E   --- right --->    D    ---  left --->    / \
    /        around         \       around       C   E
   D           E             E        D
   

2. Rebalancing takes place inside the fixAfterInsertion()method, which checks whether the red-black propertiesof the tree are still maintained after insertion. And, if it doesn't, then it rebalances the tree performing either rotateLeft()or rotateRight()on the offending branch to restore the balance. Then it moves up the tree and checks the balance and so on until it reaches the root node.

1. 的目标TreeMap是拥有一棵键树，其中低于父键的键位于左侧，高于父键的键位于右侧。因此，如果您添加C, then E，您将拥有这棵树：

   C
    \
     E
   

   如果然后添加D，最初您将拥有：

   C
    \
     E
    /
   D
   

   但是这棵树是不平衡的，因此搜索会更慢。因此，树被重新平衡。平衡后，树现在变得更有效率：

   C                     C
    \        rotate       \         rotate         D
     E   --- right --->    D    ---  left --->    / \
    /        around         \       around       C   E
   D           E             E        D
   

2. 重新平衡发生在fixAfterInsertion()方法内部，它检查插入后树的红黑属性是否仍然保持。并且，如果没有，那么它会重新平衡在有问题的分支上执行rotateLeft()或rotateRight()在有问题的分支上执行的树以恢复平衡。然后它向上移动树并检查余额等等，直到它到达根节点。

There are several resources around the internet that explain Red-Black Trees in depth. But, I think the best way of understanding the process is following an animated tutorial like this: http://www.csanimated.com/animation.php?t=Red-black_tree

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

There is nothing peculiar in the TreeMapimplementation of RBT. It closely follows the pseudocode given in CLRS's (Cormen, Leiserson, Rivest and Stein) book, which is what 99% of the implementations around do.

TreeMapRBT的实现没有什么特别之处。它严格遵循 CLRS（Cormen、Leiserson、Rivest 和 Stein）书中给出的伪代码，这是周围 99% 的实现所做的。