Tag: red black tree

基于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让它变得非常不平衡。 修改树时，随后重新排列新树并重新绘制以恢复着色属性。 这些属性的设计使得可以有效地执行这种重新排列和重新着色。 我试图分析源代码，但无法理解以下内容： 假设我已经在树中有两个键“C”和“E”，然后我添加“D”。 如何安排节点（使用自然排序）。 如何在Java源代码中实现Tree的自我平衡。 我尝试搜索TreeMap的详细实现，但无法找到任何文章，例如我为HashMap找到的以下文章 从昨天起我就挂在这棵树上:(有人可以帮我下楼……

如何在RedBlackTree实现中修复删除？

这是我正在使用的RedBlackTree的实现（来自Mark Allen Weiss，Data Structures public class RedBlackTree<AnyKey extends Comparable, AnyValue extends Comparable> implements MyTreeMap{ private static final int BLACK = 1; private static final int RED = 0; // The psuedo(bogus) root, has a key value of negative infinity and a right link to the real root. private RedBlackNode header; // Used in place of […]