基于Red-Black树的JAVA中TreeMap实现的解释 [英] Explanation of Red-Black tree based implementation of TreeMap in JAVA

问题描述

我在 JAVA 中浏览了 TreeMap 的源代码。
根据JAVA doc：

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

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

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.

此实现为containsKey，get，put和remove操作提供有保证的log（n）时间成本。算法是对Cormen，Leiserson和Rivest的算法导论中的算法的改编。

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.

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

In the source code I found that an Inner Class Entry was 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.

我试图分析源代码但是不能我不明白以下几点：

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

1. 假设我已经在树中有两个键C和E然后我正在添加D。如何安排节点（使用自然排序）。

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

如何在Java源代码中实现Tree的自我平衡。

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

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

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

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

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

推荐答案

1. TreeMap 的目标是拥有一个键树，其中低于父键的键位于左侧，键高于父键的键位于右侧那么，如果您添加 C ，然后 E ，您将拥有此树：

1. The goal of the TreeMap is 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

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

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

重新平衡发生在 fixAfterInsertion（）方法中，该方法检查插入后是否仍保留树的红黑属性。并且，如果没有，则重新平衡执行 rotateLeft（）或 rotateRight（）的树。违规分支以恢复平衡。然后它向上移动树并检查余额，依此类推，直到它到达根节点。

Rebalancing takes place inside the fixAfterInsertion() method, which checks whether the red-black properties of 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.

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

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

TreeMap中没有什么特别的实施RBT。它严格遵循CLRS（Cormen，Leiserson，Rivest和Stein）一书中给出的伪代码，这是99％的实现。

There is nothing peculiar in the TreeMap implementation 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.

这篇关于基于Red-Black树的JAVA中TreeMap实现的解释的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！