`
mabusyao
  • 浏览: 253413 次
  • 性别: Icon_minigender_1
  • 来自: 南京
社区版块
存档分类
最新评论

红黑树的TreeMap实现

 
阅读更多
红黑树是每个节点都带有颜色属性的二叉查找树,颜色或红色或黑色。在二叉查找树强制一般要求以外,对于任何有效的红黑树我们增加了如下的额外要求:

性质1. 节点是红色或黑色。

性质2. 根是黑色。

性质3. 所有叶子都是黑色(叶子是NIL节点)。

性质4. 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

性质5. 从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这个树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例,这个在高度上的理论上限允许红黑树在最坏情况下都是高效的,而不同于普通的二叉查找树。

由于红黑树的复杂程度,建议不要自己实现,我们可以在java源码的TreeMap中看到很多关键代码的实现方法。

Rotate:
    /** From CLR **/
    private void rotateLeft(Entry<K,V> p) {
        Entry<K,V> r = p.right;
        p.right = r.left;
        if (r.left != null)
            r.left.parent = p;
        r.parent = p.parent;
        if (p.parent == null)
            root = r;
        else if (p.parent.left == p)
            p.parent.left = r;
        else
            p.parent.right = r;
        r.left = p;
        p.parent = r;
    }

    /** From CLR **/
    private void rotateRight(Entry<K,V> p) {
        Entry<K,V> l = p.left;
        p.left = l.right;
        if (l.right != null) l.right.parent = p;
        l.parent = p.parent;
        if (p.parent == null)
            root = l;
        else if (p.parent.right == p)
            p.parent.right = l;
        else p.parent.left = l;
        l.right = p;
        p.parent = l;
    }


插入方法:
我们首先以二叉查找树的方法增加节点并标记它为红色。(如果设为黑色,就会导致根到叶子的路径上有一条路上,多一个额外的黑节点,这个是很难调整的。但是设为红色节点后,可能会导致出现两个连续红色节点的冲突,那么可以通过颜色调换(color flips)和树旋转来调整。) 下面要进行什么操作取决于其他临近节点的颜色。同人类的家族树中一样,我们将使用术语叔父节点来指一个节点的父节点的兄弟节点。注意:

    * 性质1[1]和性质3[2]总是保持着。
    * 性质4[3]只在增加红色节点、重绘黑色节点为红色,或做旋转时受到威胁。
    * 性质5[4]只在增加黑色节点、重绘红色节点为黑色,或做旋转时受到威胁。

情形1: 新节点N位于树的根上,没有父节点。在这种情形下,我们把它重绘为黑色以满足性质2[5]。因为它在每个路径上对黑节点数目增加一,性质5[4]符合

情形2: 新节点的父节点P是黑色,所以性质4[3]没有失效(新节点是红色的)。在这种情形下,树仍是有效的。性质5[4]受到威胁,因为新节点N有两个黑色叶子儿子;但是由于新节点N是红色,通过它的每个子节点的路径就都有同通过它所取代的黑色的叶子的路径同样数目的黑色节点,所以这个性质依然满足。

情形3: 如果父节点P和叔父节点U二者都是红色,(此时新插入节点N做为P的左子节点或右子节点都属于情形 3,这里右图仅显示N做为P左子的情形)则我们可以将它们两个重绘为黑色并重绘祖父节点G为红色(用来保持性质5[4])。现在我们的新节点N有了一个黑色的父节点P。因为通过父节点P或叔父节点U的任何路径都必定通过祖父节点G,在这些路径上的黑节点数目没有改变。但是,红色的祖父节点G的父节点也有可能是红色的,这就违反了性质4[3]。为了解决这个问题,我们在祖父节点G上递归地进行情形1的整个过程。(把G当成是新加入的节点进行各种情况的检查)

情形4: 父节点P是红色而叔父节点U是黑色或缺少; 还有,新节点N是其父节点P的右子节点,而父节点P又是其父节点的左子节点。在这种情形下,我们进行一次左旋转调换新节点和其父节点的角色; 接着,我们按情形5处理以前的父节点P。这导致某些路径通过它们以前不通过的新节点N或父节点P中的一个,但是这两个节点都是红色的,所以性质5[4]没有失效。

情形5: 父节点P是红色而叔父节点U 是黑色或缺少,新节点N 是其父节点的左子节点,而父节点P又是其父节点G的左子节点。在这种情形下,我们进行针对祖父节点G 的一次右旋转; 在旋转产生的树中,以前的父节点P现在是新节点N和以前的祖父节点G 的父节点。我们知道以前的祖父节点G是黑色,否则父节点P就不可能是红色 (如果 P  和 G 都是紅色就違反了性質4,所以 G 必須是黑色)。我们切换以前的父节点P和祖父节点G的颜色,结果的树满足性质4[3]。性质5[4]也仍然保持满足,因为通过这三个节点中任何一个的所有路径以前都通过祖父节点G ,现在它们都通过以前的父节点P。在各自的情形下,这都是三个节点中唯一的黑色节点。

    public V put(K key, V value) {
        Entry<K,V> t = root;

        if (t == null) {
            incrementSize();
            root = new Entry<K,V>(key, value, null);
            return null;
       }

        while (true) {
            int cmp = compare(key, t.key);
            if (cmp == 0) {
                return t.setValue(value);
            } else if (cmp < 0) {
                if (t.left != null) {
                    t = t.left;
                } else {
                    incrementSize();
                    t.left = new Entry<K,V>(key, value, t);
                    fixAfterInsertion(t.left);
                    return null;
                }
            } else { // cmp > 0
                if (t.right != null) {
                    t = t.right;
                } else {
                    incrementSize();
                    t.right = new Entry<K,V>(key, value, t);
                    fixAfterInsertion(t.right);
                    return null;
                }
            }
        }
    }

    /** From CLR **/
    private void fixAfterInsertion(Entry<K,V> x) {
        x.color = RED;

        while (x != null && x != root && x.parent.color == RED) {
            if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
                Entry<K,V> y = rightOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == rightOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateLeft(x);
                    }
                    setColor(parentOf(x), BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    if (parentOf(parentOf(x)) != null)
                        rotateRight(parentOf(parentOf(x)));
                }
            } else {
                Entry<K,V> y = leftOf(parentOf(parentOf(x)));
                if (colorOf(y) == RED) {
                    setColor(parentOf(x), BLACK);
                    setColor(y, BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    x = parentOf(parentOf(x));
                } else {
                    if (x == leftOf(parentOf(x))) {
                        x = parentOf(x);
                        rotateRight(x);
                    }
                    setColor(parentOf(x),  BLACK);
                    setColor(parentOf(parentOf(x)), RED);
                    if (parentOf(parentOf(x)) != null)
                        rotateLeft(parentOf(parentOf(x)));
                }
            }
        }
        root.color = BLACK;
    }
分享到:
评论

相关推荐

    JDK源码剖析之红黑树TreeMap.pptx

    JDK源码剖析之红黑树TreeMap,偶然看见,传上来分享一下

    红黑树Java实现

    - Java集合框架:`TreeMap`和`TreeSet`是基于红黑树实现的,提供有序的元素存储和高效的查找、插入和删除操作。 - 数据库索引:数据库系统如MySQL的InnoDB存储引擎使用红黑树作为索引结构。 - C++标准模板库(STL)...

    红黑树实现源码

    红黑树因其高效性能在许多实际应用中得到采用,如C++标准模板库(STL)中的set和map容器,以及Java的TreeMap和TreeSet类。它们使用红黑树作为底层数据结构,提供快速的查找、插入和删除操作。 5. 红黑树的优势: - ...

    通过分析_JDK_源代码研究_TreeMap_红黑树算法实现.docx

    ### 通过分析JDK源代码研究TreeMap红黑树算法实现 #### 一、TreeMap与TreeSet的关系 TreeMap 和 TreeSet 是 Java 集合框架中的重要成员,它们提供了基于红黑树的数据结构实现。从给定部分源代码可以看到,TreeSet ...

    红黑树算法实现

    在TreeMap的实现中,每个键值对实际上都被存储为红黑树中的一个节点,键作为节点的关键字,值则被忽略,因为TreeMap只使用键来进行排序和查找。每个节点包含键、值、节点颜色(红色或黑色)、左子节点和右子节点。 ...

    红黑树的Java实现参考源码

    在Java实现中,红黑树的核心类是`java.util.TreeMap.Node`,这个类代表树中的一个节点,包含键值对以及颜色属性。插入操作会遵循以下步骤: 1. 首先,新插入的节点默认为红色,因为红色节点不会破坏红黑树的性质。 ...

    java实现的红黑树

    在Java中,红黑树被广泛应用于`java.util.TreeMap`、`java.util.TreeSet`以及`java.util.HashMap`的内部实现中。 1. **红黑树的基本性质** - 每个节点不是红色就是黑色。 - 根节点是黑色。 - 所有叶子节点(NIL...

    Java实现的红黑树

    - 集合框架:Java的`TreeMap`和`TreeSet`利用红黑树实现有序映射和有序集合。 - 其他:内存分配器、编译器符号表等。 总的来说,红黑树是一种重要的数据结构,它的平衡策略使其在各种场景下表现出高效性。通过...

    红黑树的java实现 (二叉树也有)

    在Java中,虽然没有直接提供红黑树的类,但`java.util.TreeMap`和`java.util.TreeSet`底层就是通过红黑树实现的。它们提供了高效的键值对存储和集合管理,支持有序操作,如按自然顺序或自定义比较器进行排序。 当...

    JAVA实现的红黑树

    在Java中,红黑树被广泛应用于集合框架中的`java.util.TreeMap`和`java.util.TreeSet`等类。 1. **红黑树的性质** - 每个节点要么是红色要么是黑色。 - 根节点是黑色。 - 所有叶子节点(NIL或空节点)都是黑色。...

    java 树的数据结构 红黑树的实现 学习路线

    Java集合框架中的`java.util.TreeMap`和`java.util.TreeSet`就是基于红黑树实现的。学习红黑树,你需要了解其插入和删除操作的细节,以及如何通过旋转和重新着色来保持树的平衡。 "一种新型的树以及相关分析"可能是...

    红黑树的插入-java实现

    在Java中,红黑树被广泛应用于`java.util.TreeMap`和`java.util.TreeSet`等数据结构中。 红黑树的核心特性有五条: 1. 每个节点不是红色就是黑色。 2. 根节点是黑色。 3. 所有叶子节点(NIL或空节点)是黑色。 4. ...

    红黑树学习文档

    同时,掌握Java中红黑树的具体应用,比如`TreeMap`的内部实现,有助于提升对数据结构和算法的理解和应用能力。通过深入学习红黑树,不仅可以提高编程技能,还能为解决实际问题提供有力的数据结构支持。

    从2-3树理解红黑树

    在实际应用中,红黑树被广泛应用于各种数据结构,如C++标准模板库(STL)中的map和set,以及Java中的TreeMap和 TreeSet。这些数据结构的底层实现都依赖于红黑树的高效性能。 总结来说,2-3树和红黑树是数据结构中的...

    红黑树-基于Java实现的红黑树数据结构.zip

    - Java标准库中的`java.util.TreeMap`和`java.util.TreeSet`类底层就是用红黑树实现的。 - 实现红黑树需要定义节点类,包含节点值、颜色、左子节点、右子节点以及父节点等属性,并实现插入、删除、旋转等方法。 6...

    红黑树学习参考资料集合

    4. **Java代码实现**:与C实现类似,但使用Java语言,适用于Java开发者,且Java中的`TreeMap`类就基于红黑树实现,提供键值对的有序存储。 5. **java中的TreeMap源文件**:通过查看源代码,我们可以更深入地了解`...

    treeMap实现分组数据树形结构

    在Java编程中,TreeMap是一种基于红黑树(Red-Black Tree)算法实现的有序映射数据结构。它按照键的自然顺序或者自定义比较器的顺序来存储元素。在这个场景下,`TreeMap`被用来实现数据的分组,并构建一个树形结构,...

    红黑树原理详解

    - Java集合框架中的`TreeMap`和`TreeSet`类使用红黑树作为底层数据结构,提供有序的键值存储和快速查找。 - C++标准模板库(STL)中的`std::map`和`std::set`也使用红黑树实现。 - 数据库系统,如MySQL的InnoDB存储...

    红黑树的设计和实现(插入,删除)

    理解并熟练掌握红黑树的原理和操作是提升算法能力的关键,通过实践实现红黑树的插入和删除功能,可以深入理解其内部机制。在学习过程中,可以通过分析代码,模拟节点的插入和删除过程,以及观察和调整树的平衡状态,...

    TreeMapSourceAnalysis:JDK原始数据剖析与实战之-红黑树TreeMap

    TreeMapSourceAnalysis JDK原始数据剖析与实战之-红黑树TreeMap B站视频地址: :

Global site tag (gtag.js) - Google Analytics