Data Structure_树

作者: 冒绿光的盒子 | 来源:发表于2018-12-08 00:27 被阅读18次

    线段树Segment Tree

    对于有一类问题,时常关注的是一个区间或者是一个线段,那么就可以使用线段树来解决。比较经典的问题,就是区间染色问题:有一面墙,长度为n,每次选择一段墙来染色,一开始4-6绘制成黄色,然后1-10绘制蓝色,2-7绘制红色,若干次绘色之后能看见多少种颜色,或者是在区间「i,j」区间里面可以看到多少种颜色。所以主要有两个操作,染色操作和查询操作。使用数组操作其实是可以的,染色就只需要把对应下标的内容,修改就好了;查找只需要遍历,这样复杂度就都是O(n),这样很明显效率是不够的。
    实质的应用就是区间查询,比如统计2017年的消费最高的用户,或者是某一个太空区间天体的总量。使用线段树的之后:

    使用数组实现 使用线段树实现
    更新 O(n) O(logn)
    查询 O(n) O(logn)

    线段树大致的样子。可以看到线段树不是完全二叉树,因为如果是十个元素,是不一定都集中在左边的,这时候就不一定是完全二叉树了,但是一定是平衡二叉树。平衡二叉树的定义是,最短深度和最大深度的差只能为1,也就是不能超过1。虽然不是完全二叉树,但是依然可以用数组来表示,将下面的空节点全部补全,这样这棵树就变成满二叉树了。如果区间有n个元素,而

    这道题目其实就可以用刚刚的线段树解决,使用上面的线段树就可以直接解决。但其实这并不是最好的解决方法,因为这个题目在前面是要求有一个构造函数的,联想到在ACM这些题目中有一种方法就是打表法,打表时间是不计入时间的,使用这个时候就可以在构造函数的时候计算迭代元素的和即可,比如存到了第4个元素,那么第四个元素这个空就不存第四个元素,而是存第四个元素前面的和,包括了第四个元素,也就是[0,4]的和,这样计算的时候只需要一次减法即可。但是这里学到了SegmentTree就直接用了

    public class NumArray {
        private SegementTree segementTree;
    
        public NumArray(int[] nums) {
            segementTree = new SegementTree(nums);
        }
    
        public int sumRange(int i, int j) {
            if (segementTree == null){
                return 0;
            }
            return segementTree.query(i, j);
        }
    
        public static void main(String[] args) {
            int[] nums = {-2, 0, 3, -5, 2, -1};
            NumArray numArray = new NumArray(nums);
           // System.out.println(numArray.sumRange(0, 2));
        }
    }
    

    Update

    再来看一道题目:


    这个题目和上一个题目是有相似之处的,但是不同的是它是要求可变的,也就是涉及到了线段树的可变操作。
    线段树的更新其实最简单的。首先参数肯定是更新的索引和变量,递归寻找索引所存在的树,找到之后不论左右子树有没有改变,全部重新相加即可。更新还是查找复杂度都会是

    线段树只是一种设计思想,三维就分成八个,也是一样的。另外,这里的线段树区分是使用平均操作,但是有时候在某一个区间访问很少,再某一个区间很多,这样就可以不均分,也叫动态线段树。

    字典树Trie

    之前所讨论的树都是二叉树,无论是搜索时还是线段树,或者是后面要讲的红黑树都是二叉树,而字典树是多叉树。通常字典树是用来处理字符串。比如有20万个字符,要进行查询,如果是用树结构基本就是O(logn),但是如果用字典树,这复杂度和数量没有关系了,只和你查询的这个字符串的长度有关。


    当遍历到叶子,那么就遍历出了一个单词。在设计节点的时候,按照常规操作,还是要存储节点内容,和指向下一个节点的指针。但是要注意,在查询的时候,我们是直接知道了下一个字符,也就是在查找之前就已经知道下一个字母了,和查字典一样,所以是并不需要当前节点的内容。如果一个单词是另一个单词的结尾,那么有可能就不是叶子节点了,所以还需要一个标识来标识这个是不是单词结尾。

    Create

    创建字典树就比较简单了,之前提到,需要标识和指向下一个节点,由于这个节点数量是不知道的,所以用映射来替代。

    public class Trie {
        private class Node {
            public boolean isWord;
            public TreeMap<Character, Node> next;
    
            public Node(boolean isWord) {
                this.isWord = isWord;
                next = new TreeMap<>();
            }
    
            public Node() {
                this(false);
            }
        }
    
        private Node root;
        private int size;
    
        public Trie() {
            root = new Node();
            this.size = 0;
        }
    
    

    add

    添加元素也很简单,添加的时候遍历字符串下一个字符,通过这个字符找到下一个节点,如果到了最后一个,那么就要设置标识,表示这个是一个单词。但是这里有一个小陷阱,有可能有插入重复单词,这个时候就需要判断标识来维护size了。

        public void add(String word) {
            Node cur = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (cur.next.get(c) == null) {
                    cur.next.put(c, new Node());
                }
                cur = cur.next.get(c);
            }
            if (!cur.isWord) {
                cur.isWord = true;
                size++;
            }
        }
    
    

    Selection

    查找方法其实也很简单,首先看看当前next的映射里面有没有当前要查找的字符,如果没有,直接就返回false,如果有就留下。当遍历到最后一个的时候不能直接返回true,因为如果标识不是true,那么只能说明是恰好有这个单词在,而不是有这个单词,这个单词可能是刚刚好是某一个单词的前缀而已。

        public boolean contains(String word) {
            Node cur = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (cur.next.get(c) != null){
                    cur = cur.next.get(c);
                }else {
                    return false;
                }
            }
            return cur.isWord;
        }
    

    前缀搜索

    电话本的搜索如果你打入一个字母,就可以出现前面单词是这个字母的所有人,这个就是前缀搜索,数据库也有这样的搜索。
    其实和之前的搜索没有什么差别:

    
        public boolean isPrefix(String word){
            Node cur = root;
            for (int i = 0; i < word.length(); i++) {
                char c = word.charAt(i);
                if (cur.next.get(c) == null){
                    return false;
                }
                cur = cur.next.get(c);
            }
            return true;
        }
    
    

    Leecode208

    Leecode里面有一道这样的题目,就是实现字典树:



    和之前所实现的完全一样,直接替换一下即可。

    Leecode211


    和以往的不同,这个题目添加了类似于正则表达式的匹配,点代表任何字符。其他都差不多,就是搜索不一样。遇到点自然就是要遍历所有的可能了。使用递归实现比较简单,首先是判断边界条件,如果要比较的索引已经是最后一个字符了,那就直接返回标识。标识有的才能算有。如果不是,那就要递归访问了,是具体字符,就和之前的查找一样,如果是".",遍历所有下一个节点的字符,只要有一个符合那就可以继续,如果都没有或者是空,那么久可以返回false了。

      
        private boolean match(Node node, String word, int index) {
            if (index == word.length()) {
                return node.isWord;
            }
            char c = word.charAt(index);
            if (c != '.') {
                if (node.next.get(c) == null) {
                    return false;
                } else {
                    return match(node.next.get(c), word, index + 1);
                }
            } else {
                for (char key : node.next.keySet()) {
                    if (match(node.next.get(key), word, index + 1)) {
                        return true;
                    }
                }
                return false;
            }
        }
    
    

    Trie作为map使用


    这个题目要求计算包含前缀的单词的权值相加是多少。用递归很容易可以解答。首先要确认前缀在这个字典树里面有的,然后再前缀的基础上把后面的单词全部加起来即可。因为我们关注的是value值而不是单词,所以不需要Word,也就是标识,有没有都无所谓,value为0就没有单词,也可以替代的。

    public int sum(String prefix) {
            Node cur = root;
            for (int i = 0; i < prefix.length(); i++) {
                char c = prefix.charAt(i);
                if (cur.next.get(c) == null){
                    return 0;
                }
                cur = cur.next.get(c);
            }
            return sum(cur);
        }
    
        private int sum(Node cur){
            int res = cur.value;
            for (char key : cur.next.keySet()){
                res += sum(cur.next.get(key));
            }
            return res;
        }
    }
    

    最后的递归看起来好像没有判断递归到底的条件,但是实际上已经包含了,当节点的下一个是空的时候,就不经过for循环了,就可以直接返回。

    AVL树

    对于二叉树,有时候会存在一些比较极端的情况,如果按照顺序插入,就会变成类似链表那种情况,这个时候就复杂度就会回到n了,没有体现出树的优势。所以在插入的时候,我们需要维持树的结构。比较经典的平衡二叉树之一就是AVL树了。

    平衡二叉树

    首先声明是平衡二叉树,首先满的二叉树肯定是一棵平衡二叉树,平衡二叉树可以使得树的高度可以达到一个最低的高度。线段树也是一个平衡二叉树。在AVL里面,任意一个节点左右节点高度差不不能超过1。所以需要标注每一个节点的高度,高度可以从底层开始计算,有了高度,那么就可以计算平衡因子,平衡因子其实就是两棵左右子树的高度差,如果高度差没有超过1那么就算是平衡了。

    添加操作

    出现不平横的时候只有两种情况,一个就是添加的时候,另一个就是删除的时候。插入的时候,需要向上维护平衡性。
    1.插入的元素是在不平衡节点的左侧的左侧。也就是一直向左侧插入元素。

    这也是最简单的一种情况,插入的时候左孩子比较深,补全:

    可以看到,这种情况下首先当前节点的平衡因子一定大于0,其次左侧孩子的平衡因子是大于等于0。第一个条件很好理解,二叉树不平衡的条件,第二个条件是因为,既然是左侧多添加了一个节点,左边肯定比右边高,而平衡因子在这里计算的是左边减去右边,所以肯定是大于等于0的了。事实上应该只有大于0,因为等于0的话,那就意味着左边子树单独拿出来是平衡的,但是如果是平衡又要比右边子树多的话,那就意味着要比右边多数两个,但是多出一个的时候就已经需要改变的了,所以应该只是大于0,然而,这只是在添加的情况下有,删除就不一定了,比如上面情况,右边子树的有一个右子树,删除的时候刚刚高把那个右子树删了,而左边恰好等于0,那么还是需要换的。另外,还有一个更重要的原因,当左子树等于0的时候,或者是右子树等于0的时候,进行的旋转只能是左旋转,或者右旋转,当然对应的前提条件是当前节点是左边导致的不平衡或者是右边。**这个时候一个要进行右旋转。 **
    右旋转

    5对应的右节点接到7的左节点上,旋转完之后还需要更改高度,先更改子树的高度再更改节点高度。

    2.插入的元素是右子树的右子树,也就是一直向右侧插入元素。
    这个时候就应该是右侧子树导致的,一直向右侧插入元素,那么右子树的右边肯定也多出来了。所以就需要左旋转。

    左旋转

    3.如果是往左子树的右子树插入了导致不平衡,那么一次旋转是不可以的了。这种情况下只能回到我们之前解决过的情况处理,可以通过先把当前节点的左节点进行左旋转变成情况一,再对当前节点进行右旋转即可。所以就是先对左子树进行左旋转,再对当前节点进行右旋转。
    4.如果是往右子树的左节点添加导致了不平衡,那么就需要先右旋转再进行左旋转即可。和上面的情况其实是两两对应的。

        public Node add(Node node, K key, V value) {
            if (node == null) {
                size++;
                return new Node(key, value);
            }
            if (key.compareTo(node.key) > 0) {
                node.right = add(node.right, key, value);
            } else if (key.compareTo(node.key) < 0) {
                node.left = add(node.left, key, value);
            } else {
                node.value = value;
            }
            node.height = 1 + Math.max(getHeight(node.left), getHeight(node.right));
            int balanceFactor = getBalanceFactor(node);
            if (balanceFactor > 1 && getBalanceFactor(node.left) >= 0) {
                return rightRotate(node);
            }
            if (balanceFactor < -1 && getBalanceFactor(node.right) <= 0) {
                return leftRotate(node);
            }
            if (balanceFactor > 1 && getBalanceFactor(node.left) < 0) {
                node.left = leftRotate(node.left);
                return rightRotate(node);
            }
            if (balanceFactor < -1 && getBalanceFactor(node.right) > 0) {
                node.right = rightRotate(node.right);
                return leftRotate(node);
            }
            return node;
        }
    

    先添加元素,添加完之后再依照上面的情况进行调整。

    删除操作

    删除的时候,维护其实是一样的。 上面实际上已经列举了所有的不平衡的情况,所有这里只需要在删除的时候添加葛总不平衡的情况即可。

    总结

    在AVL树中还可以进行优化,每一次查询和删除都是达到了logn的时间复杂度。但是每一次更新都需要维护高度,如果当前节点是没有改变高度的话,其实是不需要维护上层节点的高度的了。因为从祖先节点来看,子树高度是没有变化的。AVL树还有一种优化结构,就是红黑树这种数据结构。

    红黑树

    树的平衡

    树的平衡是指树的每一个节点的左右子节点的数目大致一样。两边都相等是最好的,当然这种情况很少见,一般都是两边大致相等。比如在二叉搜索树的时候,如果插入的数字是有顺序的,那么就容易退化成极其不平衡的链表,搜索复杂度就会变成O(n)了。所以对于插入顺序不是平衡的时候,之前所学过的二叉树就不再是一种好的数据结构了。这个时候就要使用红黑树了,红黑树其实也是一种二叉树,只不过是增加了某种特性的二叉树。如果在插入或删除的时候如果出现了不平衡的状态,那么就要进行调整,保持树的平衡。

    红黑树的特征

    首先每一个节点都有颜色,在删除和添加的过程中是需要保持这些颜色的排列规律。从2-3树来看。2-3树是满足二分搜索树的基本性质的。但是2-3树不是二叉树,节点可以存放一个元素或者是两个元素。

    可以看到,如果只有一个元素,那么只能伸出两个节点;但是如果存放了2个节点,那么就可以存放三个节点。那么如果要满足二分搜索树的性质,如果是一个节点的时候,左小右大,两个节点的时候就需要左小中右大,中间的要夹在bc中间。 总体的树结构。二三树一颗绝对平衡的树,从根节点到叶子节点经过的节点数是一致的。对于AVL树,它的平衡条件没有太严格。

    那么2-3树是如何维持绝对平衡的?

    首先添加一个节点42,如果是空节点,那么就直接添加作为根节点,这个时候只有一个节点的树是一个平衡树。再添加一个37节点,按照二叉树的常规操作,应该和当前节点比较,看看添加到哪里合适,但是对于2-3树不是,它永远不会添加到一个空的节点,会添加到最后一个叶子节点上,现在只有一个根节点,所以就需要和42融合,形成了一个[37,42]的节点。再添加一个12,12比他们都要小,所以应该添加到左子树去,永远不会去空的位置,所以还得需要融合,虽然这个融合不符合规矩,但是先进行融合等等处理,这个时候就出现了4节点[12,37,42]。由于不符合规矩,所以可以很容易的就分裂成三个节点。中间节点是37,左右两边分别是12和42。再次添加一个18节点,应当添加在左边,所以自然就添加在了12这个叶子节点上面,满三个自然就分裂。当添加到第二层的时候再分裂就是这个样子: 但是可以看到,其实不是绝对平衡的。如果一个叶子节点本来就是三节点,添加到一个新的节点变成四节点在进行拆解的时候,就需要和它的父亲节点融合。 所以在整一个添加过程中,2-3树的结构是绝对平衡的。然而还有一种情况: 按照常规操作,上浮融合,自然根节点也要进行融合分裂:

    很明显还是一个平衡的,所以在整一个添加过程中是绝对平衡的。 在叶子节点达到四节点的时候就需要一步一步往上堆,一直到根节点。

    红黑树的规则

    1.每一个节点不是红色就是黑色。
    2.根节点总是黑色。
    3.如果节点是红色,那么子节点一定是黑色。但是黑色节点下面的子节点可以是红色也可以是黑色。
    4.每一个叶子节点,这里的叶子节点不是指有数值的叶子节点,而是指最后的空节点叫做叶子节点,也就是null节点是黑色的。
    5.从任意一个节点到叶子节点经过的黑色节点是一样的。


    这些规则直接提出来不好理解,来看看对应于2-3树是怎么理解的。首先看看红黑树颜色在2-3树中是代表了什么意义,如果叶子节点是红色,那么就代表这个节点和根节点是融合在一起的,黑色就是分开,这个性质很重要。在红黑树中根节点一定是黑色,那么一开始添加的42就是黑色的,然后添加了一个37,这样这两个节点就对应了2-3树的三节点,来了12后红黑树的形状: 可以看到,叶子节点是红色的,按照刚刚的表述,其实是和父节点融合的,分裂后只需要改变颜色就好了,所以把两个叶子节点变成黑色即可。 如果这个节点是叶子节点,这个根节点要继续向上融合,所以这个节点要变成红色才代表向上融合。 这个就对应了在三节点上添加元素的操作。
    这是一种情况,第二种情况就是再添加的时候节点是合并在了叶子节点上:
    这个时候就需要右旋转了,然后再做颜色翻转即可。但是做了颜色翻转之后需要以当前红色的根节点做向上的判断,因为根节点变成了红色,可能会出现两个连续红色节点的情况,因为红色节点的叶子节点一定要黑色。这种情况其实对应的就是添加之后节点分裂的情况。上面第一种情况也是需要分裂,但是不一样的是添加的顺序不一样导致了分裂不一样。还有一种情况就是插入了左节点的右子树,这种情况也是融合,但是处理方式有所不一样。事实上用2-3-4树来理解也是可以的。

    再回到上面的几个规则,如果一个根节点是黑色,叶子节点一定是红色,这是因为只有红色才代表了融合,这个时候就是一个三节点了。最后一个经过同等数量的黑色节点,其实就是经过了2-3树的节点,因为二三树是绝对平衡的,所以红黑树也有这个性质。至于为什么每一次添加都是红色节点,是因为2-3树永远不会添加到空节点,会产生融合,所以添加红色节点代表融合。

    添加操作

    添加的时候,添加的节点将是红色的,从2-3树的角度来理解,因为加入的叶子节点是不能插入到空节点的,所以自然是红色代表融合了。从红黑树本身的增删功能来看,添加红色是最保险的方法,因为红黑树是看黑色节点的数量来保持平衡的,直接添加黑色一定会导致不平衡,因为会有一条路多了一个黑色,本来是平衡的,加了一个另外的势必不平衡。所以设置成红色是影响最小的。
    红黑树的修正手段也就几种,首先就是改变颜色了,然后就是执行旋转操作。

    旋转其实也很容易理解,左旋转的时候,beta这个节点接上了x没有位置放了,所以只能接在x上,右旋转也是一样的意思。所以红黑树的插入算法就需要做出改变,插入的时候前面的步骤是一样的,从根节点向下查找要插入父节点的位置,插入节点之后,后面就需要添加检测树的操作,检测这个树是否是红黑树了,如果不是,那么就要进行修正。
    添加修正的情况有三种,其实对应的就是上面提到的三个情况了:
    ①插入的是根节点,那么直接就可以把当前节点变成黑色了,对照规则一,根节点为黑色。同时在2-3树中黑色代表单个节点,这是自然的了。
    ②父节点是黑色,这种情况下是没有违反任何规则,完美度过。
    ③当父节点是红色,叔叔节点也是红色的时候,就需要处理了,添加的节点本身就是红色,父亲又是红色,这就违反了性质4。
    由于是连续的两个黑色,那么只需要把父节点设置成黑色就好了,但是设置黑色会违反性质5,所以是行不通的。 左边红色的点就是插入的。这里要注意的是,祖父节点一定是黑色,红色不可能,红色节点叶子节点一定是黑色。当把父亲节点设置成黑色之后,问题来了,插入节点这边多了一个黑色,所以把叔叔节点也设置成黑色,这样的话这整一个分支就变多了一个黑色节点了。所以把祖父节点变成红色即可: 其实上面的步骤是可以看做是一个2-3树的分裂添加过程,一开始可以看到祖父节点的两个节点是红色,所以祖父是一个三节点,暂时的三节点,还没有分裂而已,再添加一个的时候需要分裂,所以分出来的那两个节点是黑色,2-3树分裂的时候如果不是根节点是要和上头合并的,所以祖父节点就是红色了,插入就常规插入到叶子节点合并。在这里不一定是看成是2-3树,看成2-3-4树也是可以的。
    ④当父节点是红色,叔叔节点为黑色,插入的节点是父节点的左孩子。
    违反了4的规则,如果把左边的一个节点变成黑色就可以了,但是这样右违反了5,所以需要祖父的两个分支增加一个黑色的,祖父节点变成红色的来处理,可以把父节点变成黑色,祖父节点变成红色,右旋转即可。这个情况其实就是刚刚2-3树模拟的时候的第二种情况了,分裂的时候。
    ⑤当父节点是红色色,叔叔节点是黑色,插入为右孩子。 这个情况和上面的情况很相似,左旋转就回到了上面的情况,按照上面情况处理即可。
    总的来说,就是对应着2-3树的分裂过程,只不过对应的结构不同可能有所差异。

    删除操作

    这个操作,有有点复杂了。
    ①删除的就是本身的根节点,而且根节点左右子树是空的。直接删就好了,没有上面好讲的。
    ②如果删除的节点是红色的,那么它的父亲节点就一定是黑色的。因为是红色的,直接拿孩子节点补充就好了,因为是没有影响的。
    ③如果删除节点是黑色的,而且兄弟节点是红色的,兄弟节点的孩子节点是黑色,删除节点的父亲节点也是黑色的。

    互换兄弟节点和父节点的颜色,然后对父节点做左旋转。这样还没结束,这样的结果就可以使得变成下面的情况处理了,,这个时候左子树就可以作为5处理了。
    ④如果删除节点是黑色,父节点和兄弟节点以及兄弟节点的孩子都是黑色。 左边少了一个黑色的节点,那么就需要右边也少一个,所以把兄弟节点变成红色即可。这个时候这整一颗树就都少一个黑色节点了,问题是,这整一颗树有可能只是一小部分,所以还需要回到情况1讨论,这里处理之后回到情况1判断。
    ⑤删除的节点为黑色,父亲节点为红色,兄弟节点和兄弟节点的孩子为黑色 这个情况下就只需要互换颜色即可,左边少了一个黑色节点,这个时候只需要把父节点和兄弟节点交换即可,因为因为交换之后两个子树都会经过这个父节点,而整个子树黑色高度没有变化。这个情况就是真正完成的。
    ⑥删除的节点是黑色,兄弟节点也是黑色,兄弟孩子的左节点是红色,兄弟节点的右子树为黑色,父亲节点随便颜色。 这个时候就要对兄弟节点做右旋转,然后对调兄弟节点和兄弟左孩子节点,那么情况就转移到情况7处理了。
    ⑦删除的节点是黑色,兄弟节点也是黑色,兄弟节点的右孩子为红色,父亲节点和兄弟节点左孩子随便颜色。 这种情况下,先互换父节点和兄弟节点的颜色,再对父节点进行左旋转操作,那么左边,也就是删除了节点的这边删除前和删除后是没有变化的,有变化的主要是右边。 图错了,兄弟节点的右子树是红色,我懒的改了。 上图所指示的标签都是根据原树结构标注。没有经过父节点孩子的右两条路,一条是左子树-》右,一条是-》右。左子树那条是兄弟节点-》父节点-》兄弟节点的孩子节点,这是更新之后的,没有更新之前的是右子树-》左子树,也就是父节点-》兄弟节点,-》兄弟·节点孩子节点,可以看到只是换了一个顺序而已,既然之前是平衡树,换个顺序肯定黑色节点的数量不会变吧,况且只是交换了颜色而已。
    那么只是有一条路要跟新了,也就是经过兄弟节点的右子树那条,红色那条。之前是经过了父节点-》兄弟节点-》兄弟节点的右节点,现在只是经过了兄弟节点和右节点,明显是少了一个黑色节点,很显然,该黑色就OK了,所以上图是最终改完的结果,之所以说错了只是还没到说到那一步。
    要注意的是,在很多的博客文章中,删除情况有所区别,有五种的也有四种的,这里是五种的,四种的是因为把第四和第五中情况和起来了。四种的话应该是这么写,兄弟节点和孩子全是黑色,把兄弟节点变成红色,当前节点切换到父节点重新向上判断。这里只是把父节点分开了。本质是完全一样的。

    红黑树的实现

    代码不太好,实现起来有点复杂,哎!

        private class Node<T extends Comparable<T>> {
            public boolean color;
            public T key;
            Node<T> left;
            Node<T> right;
            Node<T> parent;
    
            public Node(T key, boolean color, Node<T> parent, Node<T> left, Node<T> right) {
                this.key = key;
                this.color = color;
                this.parent = parent;
                this.left = left;
                this.right = right;
            }
    
            public T getKey() {
                return key;
            }
    
            @Override
            public String toString() {
                String s = "" + key + (this.color == RED ? "R" : "B");
                if (this.left != null) {
                    s += ("  " + left.key);
                }
                if (this.right != null) {
                    s += ("  " + right.key);
                }
                return s;
            }
        }
    
    

    由于带上了父母节点,用递归实现带父母节点的维护,就有点难度了。
    首先添加操作的更新,添加操作使用的是迭代实现,篇幅较大,不贴了。

        private void insertFixUp(Node<T> node) {
            Node<T> parent, grandParent;
            while ((parent = parentOf(node)) != null && isRed(parent)) {
                grandParent = parentOf(parent);
                if (parent == grandParent.left) {
                    //third condition,the uncle is red
                    Node<T> uncle = grandParent.right;
                    if (uncle != null && isRed(uncle)) {
                        setBlack(uncle);
                        setBlack(parent);
                        setRed(grandParent);
                        node = grandParent;
                        continue;
                    }
                    //fifth condition,the uncle is black and left child of the current node
                    if (parent.right == node) {
                        Node<T> temp;
                        leftRotate(parent);
                        temp = parent;
                        parent = node;
                        node = temp;
                    }
                    //fourth condiction,same as above but the right child of the current node.
                    setBlack(parent);
                    setRed(grandParent);
                    rightRotate(grandParent);
                } else {
                    //third condition,the uncle is red.
                    Node<T> uncle = grandParent.left;
                    if (uncle != null && isRed(uncle)) {
                        setBlack(uncle);
                        setBlack(parent);
                        setRed(grandParent);
                        node = grandParent;
                        continue;
                    }
                    //fifth condition,the uncle is black,left child
                    if (parent.left == node) {
                        Node<T> temp;
                        rightRotate(parent);
                        temp = parent;
                        parent = node;
                        node = temp;
                    }
                    //fourth condition,the uncle is black,right child
                    setBlack(parent);
                    setRed(grandParent);
                    leftRotate(grandParent);
                }
            }
            setBlack(root);
        }
    
    

    每一次处理完一种情况之后要记得更新当前节点node的信息,因为处理完后不一定就结束了,可能是更新到了一种新的情况。
    删除操作的更新,这个有点复杂。

        private void removeFixUp(Node<T> node, Node<T> par) {
            Node<T> uncle;
            Node<T> parent;
            parent = node == null ? par : node.parent;
            while ((node == null || isBlack(node)) && node != root) {
                if (parent.left == node) {
                    uncle = parent.right;
                    //the uncle is red, condition three
                    if (isRed(uncle)) {
                        setBlack(uncle);
                        setRed(parent);
                        leftRotate(parent);
                        uncle = parent.right;
                    }
                    //the uncle and his child are all black
                    if ((uncle.left == null || isBlack(uncle.left)) &&
                            (uncle.right == null || isBlack(uncle.right))) {
                        setRed(uncle);
                        node = parent;
                        parent = parentOf(node);
                    } else {
                        //the uncle is black and red of his child on the left
                        if (uncle.right == null || isBlack(uncle.right)) {
                            setBlack(uncle.left);
                            setRed(uncle);
                            rightRotate(uncle);
                            uncle = parent.right;
                        }
                        setColor(uncle, colorOf(parent));
                        setBlack(parent);
                        setBlack(uncle.right);
                        leftRotate(parent);
                        node = this.root;
                        break;
                    }
                } else {
                    uncle = parent.left;
                    if (isRed(uncle)) {
                        setBlack(uncle);
                        setRed(parent);
                        rightRotate(parent);
                        uncle = parent.left;
                    }
                    if ((uncle.left == null || isBlack(uncle.left)) &&
                            (uncle.right == null || isBlack(uncle.right))) {
                        setRed(uncle);
                        node = parent;
                        parent = parentOf(node);
                    } else {
                        if (uncle.left == null || isBlack(uncle.left)) {
                            setBlack(uncle.right);
                            setRed(uncle);
                            leftRotate(uncle);
                            uncle = parent.left;
                        }
                        setColor(uncle, colorOf(parent));
                        setBlack(parent);
                        setBlack(uncle.left);
                        rightRotate(parent);
                        node = this.root;
                        break;
                    }
                }
            }
            if (node != null) {
                setBlack(node);
            }
        }
    
    

    每次处理完后也要记得更新节点的信息,第一种情况更新完的时候,uncle节点不再是原来的了,所以要进行更新。第二种情况也是,由于处理节点已经切换到了父亲节点,于是要对父亲节点切换,第三种情况uncle节点也发生了改变,同样要切换。第四种情况直接结束。

    最后附上GitHub及其代码:https://github.com/GreenArrow2017/DataStructure_Java/tree/master/out/production/DataStructure_Java/Tree

    相关文章

      网友评论

        本文标题:Data Structure_树

        本文链接:https://www.haomeiwen.com/subject/hjaocqtx.html