Java 8 HashMap（五）——TreeNode的介绍_java treenode

一、红黑树的特性

（1）每个节点或者是黑色，或者是红色。
（2）根节点是黑色。
（3）每个叶子节点（NIL）是黑色。 [注意：这里叶子节点，是指为空(NIL或NULL)的叶子节点！]
（4）如果一个节点是红色的，则它的子节点必须是黑色的。
（5）从一个节点到该节点的子孙节点的所有路径上包含相同数目的黑节点

二、TreeNode和一些方法

static final class TreeNode<K, V> extends LinkedHashMap.Entry<K, V> {

    TreeNode<K, V> parent;//父节点
    TreeNode<K, V> left;//左子节点
    TreeNode<K, V> right;//右子节点
    TreeNode<K, V> prev;//前方节点

    boolean red;//是否是红色

    TreeNode(int hash, K key, V value, Node<K, V> next) {
        super(hash, key, value, next);
    }
    /*
     * @return 返回当前红黑树的根节点
     */

    final TreeNode<K, V> root() {
        for (TreeNode<K, V> r = this, p; ; ) {
            if ((p = r.parent) == null) {
                return r;
            }
            r = p;
        }
    }
    /**
     * 使给定节点成为当前红黑树的根节点
     */
    static <K, V> void moveRootToFront(Node<K, V>[] tab, TreeNode<K, V> root) {
        //获得当前数组容量
        int n = tab.length;
        if (root != null && tab != null && n > 0) {
            //root不为空，数组不为空，数组容量大于0
            //计算root的位置
            int index = (n - 1) & root.hash;
            //获得当前位置的TreeNode
            TreeNode<K, V> first = (TreeNode<K, V>) tab[index];
            if (root != first) {
                //当前TreeNode不是root
                //将root放到当前位置
                tab[index] = root;
                //获得root的前节点和后节点
                TreeNode<K, V> rp = root.prev;
                Node<K, V> rn = root.next;
                if (rn != null) {
                    //如果前节点不为空
                    //前节点的后节点指向root的后节点
                    ((TreeNode<K, V>) rn).prev = rp;
                }
                if (rp != null) {
                    //如果后节点不为空
                    //后节点的前节点指向root的前节点
                    rp.next = rn;
                }
                if (first != null) {
                    //如果当前TreeNode不为空
                    //当前TreeNode的前节点指向root
                    first.prev = root;
                }
                //root的后节点指向当前TreeNode
                root.next = first;
                //root的前节点指向null
                root.prev = null;
            }
            //检查红黑树结构是否正确
            assert checkInvariants(root);
        }
    }
    /**
     * 检查红黑树的结构是否正确
     *
     * @return true结构正确，false结果错误
     */
    static <K, V> boolean checkInvariants(TreeNode<K, V> t) {
        //获得t节点的父节点，左子节点，右子节点，前节点和后节点
        TreeNode<K, V> tp = t.parent, tl = t.left, tr = t.right,
                tb = t.prev, tn = (TreeNode<K, V>) t.next;
        if (tb != null && tb.next != t) {
            //如果前节点不为空，且前节点的后节点不为t，返回false
            return false;
        }
        if (tn != null && tn.prev != t) {
            //如果后节点不为空，且后节点的前节点不为t，返回false
            return false;
        }
        if (tp != null && t != tp.left && t != tp.right) {
            //如果父节点不为空，且t节点不为父节点的左右子节点，返回false
            return false;
        }
        if (tl != null && (tl.parent != t || tl.hash > t.hash)) {
            //如果左子节点不为空，且左子节点的父节点不为t或者左子节点的hash值大于t节点的hash值，返回false
            return false;
        }
        if (tr != null && (tr.parent != t || tr.hash < t.hash)) {
            //如果右子节点不为空，且右子节点的父节点不为t或者右子节点的hash值小于t节点的hash值，返回false
            return false;
        }
        if (t.red && tl != null && tl.red && tr != null && tr.red) {
            //如果t节点和他的左右子节点都为红色，返回false
            return false;
        }
        if (tl != null && checkInvariants(tl)) {
            //递归检查左子节点
            return false;
        }
        if (tr != null && checkInvariants(tr)) {
            //递归检查右子节点
            return false;
        }
        //通过上述检查返回true
        return true;
    }

    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113