大学IT网 - 最懂大学生的IT学习网站! QQ资料交流群:367606806
当前位置:大学IT网 > Java技巧 > 浅谈Java TreeMap

浅谈Java TreeMap(3)

关键词:JavaTreeMap  阅读(2187) 赞(12)

[摘要]本文是对Java提高篇(二七)-----TreeMap的讲解,对学习Java编程技术有所帮助,与大家分享。

3、每个叶节点(NIL节点,空节点)是黑色的。

4、假如一个结点是红的,则它两个子节点都是黑的。也就是说在一条途径上不能呈现相邻的两个白色结点。

5、从任一节点到其每个叶子的一切途径都包括相反数目的黑色节点。

(注:曾经讲三遍了,再不记住我就疑心你能否合适搞IT了 O(∩_∩)O~)

固然,既然删除节点比拟复杂,那么在这里我们就商定一下规则:

1、上面要解说的删除节点一定是实践要删除节点的后继节点(N),如后面提到的C。

2、上面提到的删除节点的树都是如下构造,该构造所选取的节点是待删除节点的右树的最右边子节点。这里我们规则真实删除节点为N、父节点为P、兄弟节点为W兄弟节点的两个子节点为X1、X2。如下图(2.1)。

  • 20140517000013

    如今我们就下面提到的三种状况停止剖析、处置。

    状况一、无子节点(白色节点)

    这种状况对该节点直接删除即可,不会影响树的构造。由于该节点为叶子节点它不能够存在子节点-----如子节点为黑,则违背黑节点数准绳(规则5),为红,则违背“颜色”准绳(规则4)。 如上图(2.2)。

    状况二、有一个子节点

    这种状况处置也是十分复杂的,用子节点替代待删除节点,然后删除子节点即可。如上图(2.3)

    状况三、有两个子节点

    这种状况能够会略微有点儿复杂。它需求找到一个替代待删除节点(N)来替代它,然后删除N即可。它次要分为四种状况。

    1、N的兄弟节点W为白色

    2、N的兄弟w是黑色的,且w的俩个孩子都是黑色的。

    3、N的兄弟w是黑色的,w的左孩子是白色,w的右孩子是黑色。

    4、N的兄弟w是黑色的,且w的右孩子时白色的。

    状况3.1、N的兄弟节点W为白色

    W为白色,那么其子节点X1、X2肯定全部为黑色,父节点P也为黑色。处置战略是:改动W、P的颜色,然后停止一次左旋转。这样处置就可以使得红黑性质得以持续坚持。N的新兄弟new w是旋转之前w的某个孩子,为黑色。这样处置后将状况3.1、转变为3.2、3.3、3.4中的一种。如下:

    20140517000014

  • 状况3.2、N的兄弟w是黑色的,且w的俩个孩子都是黑色的。

  • 这种状况其父节点可红可黑,由于W为黑色,这样招致N子树绝对于其兄弟W子树少一个黑色节点,这时我们可以将W置为白色。这样,N子树与W子树黑色节点分歧,坚持了均衡。如下

  • 20140517000015

    将W由黑转变为红,这样就会招致新节点new N绝对于它的兄弟节点会少一个黑色节点。但是假如new x为白色,我们直接将new x转变为黑色,坚持整棵树的均衡。否则状况3.2 会转变为状况3.1、3.3、3.4中的一种。

  • 状况3.3、N的兄弟w是黑色的,w的左孩子是白色,w的右孩子是黑色。

  • 针对这种状况是将节点W和其左子节点停止颜色交流,然后对W停止右旋转处置。

  • 20140517000016

  • 此时N的新兄弟X1(new w)是一个有白色右孩子的黑结点,于是将状况3转化为状况4.

  • 状况3.4、N的兄弟w是黑色的,且w的右孩子时白色的。

  • 交流W和父节点P的颜色,同时对P停止左旋转操作。这样就把右边缺失的黑色节点给补回来了。同时将W的右子节点X2置黑。这样左右都到达了均衡。

  • 20140517000017

  • 总结

  • 团体以为这四种状况比拟难了解,首先他们都不是单一的某种状况,他们之间是可以停止互转的。绝对于其他的几种状况,状况3.2比拟好了解,仅仅只是一个颜色的转变,经过增加右子树的一个黑色节点使之坚持均衡,同时将不均衡点上移至N与W的父节点,然后停止下一轮迭代。状况3.1,是将W旋转将其转成状况2、3、4状况停止处置。而状况3.3经过转变后可以化成状况3.4来停止处置,从这里可以看出状况3.4应该最终结。状况3.4、右子节点为白色节点,那么将缺失的黑色节点交由给右子节点,经过旋转到达均衡。

  • 经过下面的剖析,我们曾经初步理解了红黑树的删除节点状况,绝对于添加节点而言它的确是选的较为复杂。上面我将看到在Java TreeMap中是如何完成红黑树删除的。

  • TreeMap deleteEntry()办法完成剖析

  • 经过下面的剖析我们确认删除节点的步骤是:找到一个替代子节点C来替代P,然后直接删除C,最初调整这棵红黑树。上面代码是寻觅替代节点、删除替代节点。

  • private void deleteEntry(Entry<K,V> p) {
            modCount++;      //修正次数 +1
            size--;          //元素个数 -1
    
            /*
             * 被删除节点的左子树和右子树都不为空,那么就用 p节点的中序后继节点替代 p 节点
             * successor(P)办法为寻觅P的替代节点。规则是右分支最右边,或许 左分支最左边的节点
             * ---------------------(1)
             */
            if (p.left != null && p.right != null) {  
                Entry<K,V> s = successor(p);
                p.key = s.key;
                p.value = s.value;
                p = s;
            }
    
            //replacement为替代节点,假如P的左子树存在那么就用左子树替代,否则用右子树替代
            Entry<K,V> replacement = (p.left != null ? p.left : p.right);
    
            /*
             * 删除节点,分为下面提到的三种状况
             * -----------------------(2)
             */
            //假如替代节点不为空
            if (replacement != null) {
                replacement.parent = p.parent;
                /*
                 *replacement来替代P节点
                 */
                //若P没有父节点,则跟节点直接变成replacement
                if (p.parent == null)
                    root = replacement;
                //假如P为左节点,则用replacement来替代为左节点
                else if (p == p.parent.left)
                    p.parent.left  = replacement;
              //假如P为右节点,则用replacement来替代为右节点
                else
                    p.parent.right = replacement;
    
                //同时将P节点从这棵树中剔除掉
                p.left = p.right = p.parent = null;
    
                /*
                 * 若P为白色直接删除,红黑树坚持均衡
                 * 但是若P为黑色,则需求调整红黑树使其坚持均衡
                 */
                if (p.color == BLACK)
                    fixAfterDeletion(replacement);
            } else if (p.parent == null) {     //p没有父节点,表示为P根节点,直接删除即可
                root = null;
            } else {      //P节点不存在子节点,直接删除即可
                if (p.color == BLACK)         //假如P节点的颜色为黑色,对红黑树停止调整
                    fixAfterDeletion(p);
    
                //删除P节点
                if (p.parent != null) {
                    if (p == p.parent.left)
                        p.parent.left = null;
                    else if (p == p.parent.right)
                        p.parent.right = null;
                    p.parent = null;
                }
            }
        }

    (1)除是寻觅替代节点replacement,其完成办法为successor()。如下:

    static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {
            if (t == null)
                return null;
            /*
             * 寻觅右子树的最左子树
             */
            else if (t.right != null) {
                Entry<K,V> p = t.right;
                while (p.left != null)
                    p = p.left;
                return p;
            } 
            /*
             * 选择左子树的最右子树
             */
            else {
                Entry<K,V> p = t.parent;
                Entry<K,V> ch = t;
                while (p != null && ch == p.right) {
                    ch = p;
                    p = p.parent;
                }
                return p;
            }
        }

    (2)处是删除该节点进程。它次要分为下面提到的三种状况,它与下面的if…else if… else逐个对应 。如下:

    1、有两个儿子。这种状况比拟复杂,但还是比拟复杂。下面提到过用子节点C替代替代待删除节点D,然后删除子节点C即可。

    2、没有儿子,即为叶结点。直接把父结点的对应儿子指针设为NULL,删除儿子结点就OK了。

    3、只要一个儿子。那么把父结点的相应儿子指针指向儿子的独生子,删除儿子结点也OK了。



    相关评论