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

Question

我在JAVA中浏览了TreeMap的源代码.根据JAVA doc:

基于红黑树的NavigableMap实现.地图根据其键的自然顺序进行排序,或者根据使用的构造函数在地图创建时提供的比较器进行排序.

此实现为containsKey,get,put和remove操作提供有保证的log(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;
        ....

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

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

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

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

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

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

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

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

Answer 1

1. 其目标TreeMap是拥有一个键树,其中低于父键的键位于左侧,而高于父键的键位于右侧.那么,如果你添加C,那么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()在违规分支上的树以恢复平衡.然后它向上移动树并检查平衡,依此类推,直到它到达根节点.

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

TreeMapRBT 的实施没有什么特别之处.它严格遵循CLRS(Cormen,Leiserson,Rivest和Stein)一书中给出的伪代码,这是99%的实现.