小菜鸟

java菜鸟号正在起航

0%

红黑树

发表于 更新于 分类于 阅读次数： Valine：
本文字数： 5.4k 阅读时长 ≈ 5 分钟

红黑树

要了解红黑树，首先要知道二叉查找树，因为红黑树是特殊的二叉查找树

二叉查找树

首先它是一颗二叉树

  • 若左子树不空，则左子树上所有节点的值均小于它的根节点的值；
  • 若右子树不空，则右子树上所有节点的值均大于它的根节点的值；
  • 左、右子树也分别为二叉排序树

来进行查找时，根据二分查找的思想，查找所需的最大次数等同于二叉查找树的高度，但是二叉查找树在极端情况下多次插入新节点会变成线性的链表，导致查找时需要遍历所有节点

根据二分查找树的特性来说，使用中序遍历可以得到一个由小到大的有序序列。

插入节点

  • 以根节点为当前节点开始搜索
  • 新节点的值与当前节点比较
  • 如果新节点大于当前节点，则以当前节点的右子节点作为新的当前节点；如果新节点小于当前节点，则以当前节点的左子节点作为新的当前节点
  • 重复上述操作，直到搜索到合适的叶子节点，将该新节点添加为叶子节点的左/右节点

删除节点

  • 如果删除的节点是叶子节点，只需将它从其父节点中删除
  • 如果不是叶子节点，且只有一个子节点，被删除的节点p只有左子树，将p的左子树pL添加为p的父节点的左子树；被删除的节点p只有右子树，将p的右子树pR添加为p的父节点的右子树
  • 如果被删除的p的左右节点都非空，有两种做法
    • 做法一：将pL设为p的父节点q的左或右子节点，将pR设为p节点的中序前驱结点s的右子节点(s是pL最右下节点)
    • 做法二：以p节点的中序前驱或后继替代p所指节点，然后再从原二叉查找树中删去中序前驱或后继节点(用大于p的最小节点或小于p的最大节点代替p节点)
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
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
static class TreeNode<E> {
    E data;
    TreeNode<E> parent;
    TreeNode<E> left;
    TreeNode<E> right;

    public TreeNode(E data) {
        this.data = data;
    }

    public TreeNode(E data, TreeNode<E> parent, TreeNode<E> left, TreeNode<E> right) {
        this.data = data;
        this.parent = parent;
        this.left = left;
        this.right = right;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        TreeNode<?> treeNode = (TreeNode<?>) o;

        if (!data.equals(treeNode.data)) return false;
        if (!parent.equals(treeNode.parent)) return false;
        if (!left.equals(treeNode.left)) return false;
        return right.equals(treeNode.right);
    }

    @Override
    public int hashCode() {
        int result = data.hashCode();
        result = 31 * result + parent.hashCode();
        result = 31 * result + left.hashCode();
        result = 31 * result + right.hashCode();
        return result;
    }
}

// 根节点
private TreeNode<E> root;

public LookBinTree(E root) {
    this.root = new TreeNode<>(root);
}

/**
 * 添加节点
 *
 * @param data
 * @return
 */
public void add(E data) {
    // 根节点为空，则为根节点
    if (root == null) {
        root = new TreeNode<>(data);
    } else {
        TreeNode<E> current = root;
        TreeNode<E> parent = null;
        // 从根节点往下搜索,找到合适的叶子节点
        int cmp = 0;
        do {
            parent = current;
            cmp = data.compareTo(parent.data);
            if (cmp > 0) { // 新节点大于当前节点
                current = current.right;
            } else { // 新节点小于当前节点
                current = current.left;
            }
        } while (current != null);
        // 创建新节点
        TreeNode<E> newNode = new TreeNode<>(data, parent, null, null);
        if (cmp > 0) {
            parent.right = newNode;
        } else {
            parent.left = newNode;
        }

    }
}

/**
 * 删除节点
 *
 * @param data
 */
public void remove(E data) {
    TreeNode<E> node = getNode(data);
    if (node == null) { // 没有该元素
        return;
    }

    if (node.left == null && node.right == null) { // 左右子树都是空的
        if (node == root) { // 如果是根节点
            root = null;
        } else {
            if (node.parent.left == node) {
                node.parent.left = null;
            } else {
                node.parent.right = null;
            }
            node.parent = null;
        }

    } else if (node.left == null && node.right != null) { // 左子树为空，右子树不为空
        if (node == root) { // 如果是根节点
            root = node.right;
        } else {
            // 被删除的节点是父节点的左子节点
            if (node.parent.left == node) {
                node.parent.left = node.right;
            } else { // 被删除的节点是父节点的右子节点
                node.parent.right = node.right;
            }
            node.right.parent = node.parent;
        }

    } else if (node.left != null && node.right == null) { // 左子树不为空，右子树为空
        if (node == root) { // 如果是根节点
            root = node.left;
        } else {
            // 被删除的节点是父节点的左子节点
            if (node.parent.left == node) {
                node.parent.left = node.left;
            } else { // 被删除的节点是父节点的右子节点
                node.parent.right = node.left;
            }
            node.left.parent = node.parent;
        }

    } else { // 左右子树都不为空
        TreeNode<E> leftMaxNode = node.left;
        // 找到左子树的最大值
        while (leftMaxNode.right != null) {
            leftMaxNode = leftMaxNode.right;
        }
        leftMaxNode.parent.right = null;
        leftMaxNode.parent = node.parent;
        if(node == node.parent.left){ // 被删除的是父节点的左子树
            node.parent.left = leftMaxNode;
        } else {
            node.parent.right = leftMaxNode;
        }

        leftMaxNode.left = node.left;
        leftMaxNode.right = node.right;
        node.parent = node.left = node.right = null;

    }
}

public TreeNode<E> getNode(E data) {
    // 从根节点往后搜索
    TreeNode<E> current = root;
    while (current != null) {
        int cmp = data.compareTo(current.data);
        if (cmp > 0) {
            current = current.right;
        } else if (cmp < 0) {
            current = current.left;
        } else {
            return current;
        }
    }
    return null;
}

红黑树

由于二叉查找树在极端情况下会变成链表，为了弥补二叉查找树的不足，发明了红黑树，红黑树是一种自平衡的二叉查找树，可在O(logN)时间内完成查找、增加、删除等操作。除了符合二叉查找树的特性外，还符合以下特性

TreeMap就是用红黑树实现的

  • 每个节点要么是黑色要么是红色
  • 根节点永远是黑色
  • 所有叶子节点都是黑色的空节点
  • 如果一个节点是红色的，则它的子节点必须是黑色的(不会有两个连续的红色节点) 【保证了从根节点到叶子节点的最长路径长度不会超过其他路径的2倍】
  • 从任一节点到其每个叶子节点的所有路径中，黑色元素的数量必须相同 (从根节点到叶子节点的路径中包含的黑色节点数被称为树的 黑色高度)

对于黑色高度为N的红黑树，从根节点到叶子节点的最短路径长度为N-1，最长路径长度为2*(N-1)

红黑树

如果在插入和删除节点时导致不符合以上规则时，就会进行调整，调整分为变色和旋转

变色

变色就是尝试把红色节点变成黑色，或者把黑色变成红色

旋转

左旋

逆时针旋转红黑树的两个节点，使得父节点被自己的右孩子节点取代，自己成为自己的左孩子节点，也就是说左旋是将某个节点旋转为其右孩子的左孩子

单向左旋

右旋

顺时针旋转红黑树的两个节点，使得父节点被自己的左孩子取代，而自己称为自己的右孩子，也就是说右旋是将某个节点旋转为其左孩子的右孩子

单向右旋

插入

  • 插入的时候节点首先是红色的(如果设为黑色，就会导致根节点到叶子节点的路径上多了一个额外的黑色节点，很难调整。而设为红色，出现连续两个的红色节点，可以通过变色和旋转来调整)

  • 变色和旋转，分为多种情况

    • 情况1 新节点是树的根节点，没有父节点

      这时直接将该节点颜色改为黑色即可

    • 情况2 该节点的父节点P是黑色

      新插入的节点是红色，不需要变色

    • 情况3 父节点P和父节点的兄弟节点U都是红色

      此时，需要将P和U都设为黑色，并将P的父节点G设为红色。(从G向下的路径此时是满足红黑树的性质了)，但是G的向上的路径不确定是否满足，对G继续向上递归该操作

    • 情况4 父节点P是红色，兄弟节点U是黑色或没有兄弟节点

      根据节点位置不同有不同的处理方式

      • 此时如果新节点是父节点P的右子节点，而父节点P又是其父节点G的右子节点。通过对新节点和其父节点进行一次左旋转，P和G进行颜色互换
      • 此时如果新节点是父节点P的右子节点，而父节点P又是其父节点G的左子节点。通过对新节点和其父节点进行一次右旋转，这样就变成上一种情形了，继续进行左旋，变色
      • 此时如果新节点是父节点P的左子节点，而父节点P又是其父节点G的左子节点。通过对节点G进行一次右旋转，P和G进行颜色互换
      • 此时如果新节点是父节点P的左子节点，而父节点P又是其父节点G的右子节点。通过对节点P进行一次左旋转，这样就变成上一种情形了，继续进行右旋，变色
相关文章

欢迎关注我的其它发布渠道