基于Red-Black树的JAVA中TreeMap实现的解释

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

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

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

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

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

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

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

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

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

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

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

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

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

Answer 1

1. TreeMap的目标是拥有一个键树，其中低于父键的键位于左侧，而高于父键的键位于右侧。 所以，如果你添加C ，那么E ，你将拥有这棵树：

    C \ E 

   如果你然后添加D ，最初你会有：

    C \ E / D 

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

    CC \ rotate \ rotate D E --- right ---> D --- left ---> / \ / around \ around CE DEED 

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

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

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