0%

自平衡二叉搜索树

自平衡二叉搜索树问题

  • 节点代码

    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
    public class Node <T extends Comparable<T>> implements Comparable<Node<T>>{

    public Node(T value) {
    this.value = value;
    }

    public T getValue() {
    return value;
    }

    public void setValue(T value) {
    this.value = value;
    }

    public Node<T> getParent() {
    return parent;
    }

    public void setParent(Node<T> parent) {
    if (this.parent != null) {
    if (this.parent.left == this) {
    this.parent.left = null;
    }
    if (this.parent.right == this) {
    this.parent.right = null;
    }
    }
    this.parent = parent;
    }

    public Node<T> getLeft() {
    return left;
    }

    public void setLeft(Node<T> left) {
    if (this.left != null) {
    this.left.parent = null;
    }
    if (left != null) {
    if (left.parent != null) {
    if (left == left.parent.left) {
    left.parent.left = null;
    } else {
    left.parent.right = null;
    }
    }
    this.left = left;
    this.left.parent = this;
    } else {
    this.left = null;
    }
    }

    public Node<T> getRight() {
    return right;
    }

    public void setRight(Node<T> right) {
    if (this.right != null) {
    this.right.parent = null;
    }
    if (right != null) {
    if (right.parent != null) {
    if (right == right.parent.left) {
    right.parent.left = null;
    } else {
    right.parent.right = null;
    }
    }
    this.right = right;
    this.right.parent = this;
    } else {
    this.right = null;
    }
    }

    public void setRightAssist(Node<T> right) {
    this.right = right;
    }

    protected T value;
    protected Node<T> parent;
    protected Node<T> left;
    protected Node<T> right;

    @Override
    public int compareTo(Node<T> node) {
    if (node == null) {
    return 1;
    }
    if (this.getValue() == null && node.getValue() == null) {
    return 0;
    }
    if (this.getValue() == null) {
    return -1;
    }
    return this.getValue().compareTo(node.getValue());
    }
    }
  • 搜索二叉树接口代码

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    public interface IBinarySearchTree<T extends Comparable<T>> {
    boolean insert(T value);
    boolean remove(T value);
    boolean contain(T value);
    boolean empty();
    int size();
    Node<T> find(T value);
    int getLength();
    int getLength(Node<T> node);
    void DLREach(IForeachOperator<T> operator);
    void LDREach(IForeachOperator<T> operator);
    void LRDEach(IForeachOperator<T> operator);
    void levelEach(IForeachOperator<T> operator);
    }
  • 遍历辅助操作值的函数式接口

    1
    2
    3
    4
    @FunctionalInterface
    public interface IForeachOperator<T extends Comparable<T>> {
    void operator(T value);
    }
  • 普通的二叉搜索树代码

    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
    168
    169
    170
    171
    172
    173
    174
    175
    176
    177
    178
    179
    180
    181
    182
    183
    184
    185
    186
    187
    188
    189
    190
    191
    192
    193
    194
    195
    196
    197
    198
    199
    200
    201
    202
    203
    204
    205
    206
    207
    208
    209
    210
    211
    212
    213
    214
    215
    216
    217
    218
    219
    220
    221
    222
    223
    224
    225
    226
    227
    228
    229
    230
    231
    232
    233
    234
    235
    236
    237
    238
    239
    240
    241
    242
    243
    244
    245
    246
    247
    248
    249
    250
    251
    252
    253
    254
    255
    256
    257
    import java.util.LinkedList;
    import java.util.Queue;
    import java.util.Stack;

    public class BinaryTree<T extends Comparable<T>> implements IBinarySearchTree<T> {
    @Override
    public boolean insert(T value) {
    if (value == null || this.contain(value)) {
    return false;
    }
    if (this.root == null) {
    this.root = new Node<>(value);
    this.size++;
    return true;
    }
    Node<T> tmp = this.root;
    while (tmp != null)
    {
    if (tmp.getValue().compareTo(value) > 0) {
    if (tmp.getLeft() == null) {
    tmp.setLeft(new Node<>(value));
    this.size++;
    return true;
    } else {
    tmp = tmp.getLeft();
    }
    } else {
    if (tmp.getRight() == null) {
    tmp.setRight(new Node<>(value));
    this.size++;
    return true;
    } else {
    tmp = tmp.getRight();
    }
    }
    }
    return false;
    }

    @Override
    public boolean remove(T value) {
    if (value == null || !this.contain(value)) {
    return false;
    }
    if (this.size == 1) {
    this.size = 0;
    this.root = null;
    return true;
    }
    Node<T> removeNode = this.find(value);
    if (removeNode.getLeft() == null) {
    if (removeNode.getParent() == null) {
    this.root = removeNode.getRight();
    } else {
    if (removeNode == removeNode.getParent().getLeft()) {
    removeNode.getParent().setLeft(removeNode.getRight());
    } else {
    removeNode.getParent().setRight(removeNode.getRight());
    }
    }
    this.size--;
    return true;
    }
    if (removeNode.getRight() == null) {
    if (removeNode.getParent() == null) {
    this.root = removeNode.getRight();
    } else {
    if (removeNode == removeNode.getParent().getLeft()) {
    removeNode.getParent().setLeft(removeNode.getLeft());
    } else {
    removeNode.getParent().setRight(removeNode.getLeft());
    }
    }
    this.size--;
    return true;
    }
    Node<T> rightNodeMostLeft = removeNode.getRight();
    while (rightNodeMostLeft.getLeft() != null) {
    rightNodeMostLeft = rightNodeMostLeft.getLeft();
    }
    removeNode.setValue(rightNodeMostLeft.getValue());
    if (rightNodeMostLeft == removeNode.getRight()) {
    removeNode.setRight(rightNodeMostLeft.getRight());
    } else {
    rightNodeMostLeft.getParent().setLeft(rightNodeMostLeft.getRight());
    }
    this.size--;
    return true;
    }

    @Override
    public boolean contain(T value) {
    if (value == null) {
    return false;
    }
    Node<T> tmp = this.root;
    while (tmp != null) {
    if (tmp.getValue().compareTo(value) == 0) {
    return true;
    } else if (tmp.getValue().compareTo(value) > 0) {
    tmp = tmp.getLeft();
    } else {
    tmp = tmp.getRight();
    }
    }
    return false;
    }

    @Override
    public boolean empty() {
    return this.size == 0;
    }

    @Override
    public int size() {
    return this.size;
    }

    @Override
    public Node<T> find(T value) {
    if (value == null || !this.contain(value)) {
    return null;
    }
    Node<T> tmp = this.root;
    while (tmp != null) {
    if (tmp.getValue().compareTo(value) == 0) {
    return tmp;
    } else if (tmp.getValue().compareTo(value) > 0) {
    tmp = tmp.getLeft();
    } else {
    tmp = tmp.getRight();
    }
    }
    return null;
    }

    @Override
    public int getLength() {
    return this.getLength(this.root);
    }

    @Override
    public int getLength(Node<T> node) {
    if (node == null) {
    return 0;
    }
    if (node.getLeft() == null && node.getRight() == null) {
    return 1;
    }
    return 1 + Math.max(this.getLength(node.getLeft()), this.getLength(node.getRight()));
    }

    @Override
    public void DLREach(IForeachOperator<T> operator) {
    if (!this.empty()) {
    DLREach(operator, this.root);
    }
    }

    private void DLREach(IForeachOperator<T> operator, Node<T> node) {
    if (node != null) {
    operator.operator(node.getValue());
    DLREach(operator, node.getLeft());
    DLREach(operator, node.getRight());
    }
    }

    @Override
    public void LDREach(IForeachOperator<T> operator) {
    if (!this.empty()) {
    Stack<Node<T>> stack = new Stack<>();
    Node<T> node = this.root;
    while (!stack.empty() || node != null) {
    if (node != null) {
    stack.push(node);
    node = node.getLeft();
    } else {
    node = stack.pop();
    operator.operator(node.getValue());
    node = node.getRight();
    }
    }
    }
    }

    @Override
    public void LRDEach(IForeachOperator<T> operator) {
    if (!this.empty()) {
    Node<T> node = this.root;
    while (node != null) {
    Node<T> leftNodeMostRight = node.getLeft();
    if (leftNodeMostRight != null) {
    while (leftNodeMostRight.getRight() != null && leftNodeMostRight.getRight() != node) {
    leftNodeMostRight = leftNodeMostRight.getRight();
    }
    if (leftNodeMostRight.getRight() == null) {
    leftNodeMostRight.setRightAssist(node);
    node = node.getLeft();
    } else {
    leftNodeMostRight.setRightAssist(null);
    operatorEdge(operator, node.getLeft());
    node = node.getRight();
    }
    } else {
    node = node.getRight();
    }
    }
    operatorEdge(operator, this.root);
    }
    }

    private void operatorEdge(IForeachOperator<T> operator, Node<T> node) {
    if (node != null) {
    Node<T> tmp1 = node, tmp2 = null;
    while (tmp1 != null) {
    Node<T> tmp3 = tmp1.getRight();
    tmp1.setRightAssist(tmp2);
    tmp2 = tmp1;
    tmp1 = tmp3;
    }
    tmp1 = tmp2;
    while (tmp1 != null) {
    operator.operator(tmp1.getValue());
    tmp1 = tmp1.getRight();
    }
    while (tmp2 != null) {
    Node<T> tmp3 = tmp2.getRight();
    tmp2.setRightAssist(tmp1);
    tmp1 = tmp2;
    tmp2 = tmp3;
    }
    }
    }

    @Override
    public void levelEach(IForeachOperator<T> operator) {
    if (this.empty()) {
    return;
    }
    Queue<Node<T>> queue = new LinkedList<>();
    queue.add(this.root);
    while (!queue.isEmpty()) {
    Node<T> node = queue.poll();
    operator.operator(node.getValue());
    if (node.getLeft() != null) {
    queue.add(node.getLeft());
    }
    if (node.getRight() != null) {
    queue.add(node.getRight());
    }
    }
    }

    protected int size;
    protected Node<T> root;

    }
  • 自平衡二叉搜索树的抽象类代码

    1
    2
    3
    4
    5
    6
    7
    public abstract class CanReBalanceBinarySearchTree<T extends Comparable<T>> extends BinaryTree<T> {

    protected abstract void reBalance(Node<T> node);
    protected abstract void LeftRotate(Node<T> node);
    protected abstract void RightRotate(Node<T> node);

    }

    AVLTree

定义:

  1. AVL树是二叉搜索树, 即AVL树的所有节点的左子树的值小于根节点的值小于右子树的值
  2. AVL树的所有节点的左右子树高度差不超过1

代码:

  • 节点代码

    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
    public class AVLNode<T extends Comparable<T>> extends Node<T> {

    public AVLNode(T value) {
    super(value);
    }

    public int getLevel() {
    return level;
    }

    public void setLevel(int level) {
    this.level = level;
    }

    public boolean isBalance() {
    int left = 0, right = 0;
    if (super.left != null) {
    left = ((AVLNode<T>)super.left).level;
    }
    if (super.right != null) {
    right = ((AVLNode<T>)super.right).level;
    }
    return Math.abs(left - right) <= 1;
    }

    private int level;
    }
  • AVL树代码

    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
    168
    public class AVLTree<T extends Comparable<T>> extends CanReBalanceBinarySearchTree<T> {

    @Override
    public boolean insert(T value) {
    if (super.contain(value)) {
    return false;
    }
    AVLNode<T> insertNode = new AVLNode<>(value);
    insertNode.setLevel(1);
    if (super.empty()) {
    super.root = insertNode;
    super.size++;
    return true;
    } else {
    AVLNode<T> node = (AVLNode<T>) super.root;
    while (node != null) {
    if (node.compareTo(insertNode) > 0) {
    if (node.getLeft() == null) {
    node.setLeft(insertNode);
    break;
    } else {
    node = (AVLNode<T>) node.getLeft();
    }
    } else {
    if (node.getRight() == null) {
    node.setRight(insertNode);
    break;
    } else {
    node = (AVLNode<T>) node.getRight();
    }
    }
    }
    AVLNode<T> tmp = insertNode;
    while (tmp != null) {
    resetLevel(tmp);
    tmp = (AVLNode<T>) tmp.getParent();
    }
    reBalance(insertNode);
    this.size++;
    return true;
    }
    }

    @Override
    public boolean remove(T value) {
    if (!super.contain(value) || super.empty()) {
    return false;
    }
    if (super.size == 1) {
    super.size = 0;
    super.root = null;
    return true;
    }
    AVLNode<T> removeNode = (AVLNode<T>) super.find(value);
    AVLNode<T> parent = (AVLNode<T>) removeNode.getParent();
    if (removeNode.getLeft() == null || removeNode.getRight() == null) {
    if (removeNode.getLeft() == null){
    if (parent == null) {
    super.root = removeNode.getRight();
    } else {
    if (removeNode == parent.getLeft()) {
    parent.setLeft(removeNode.getRight());
    } else {
    parent.setRight(removeNode.getRight());
    }
    }
    } else {
    if (parent == null) {
    super.root = removeNode.getLeft();
    } else {
    if (removeNode == parent.getLeft()) {
    parent.setLeft(removeNode.getLeft());
    } else {
    parent.setRight(removeNode.getLeft());
    }
    }
    }
    this.size--;
    AVLNode<T> tmp = parent;
    while (tmp != null) {
    resetLevel(tmp);
    tmp = (AVLNode<T>) tmp.getParent();
    }
    reBalance(parent);
    return true;
    }
    AVLNode<T> rightNodeMostLeft = (AVLNode<T>) removeNode.getRight();
    if (rightNodeMostLeft.getLeft() != null) {
    rightNodeMostLeft = (AVLNode<T>) rightNodeMostLeft.getLeft();
    }
    removeNode.setValue(rightNodeMostLeft.getValue());
    parent = (AVLNode<T>) rightNodeMostLeft.getParent();
    if (rightNodeMostLeft == removeNode.getRight()) {
    removeNode.setRight(rightNodeMostLeft.getRight());
    } else {
    parent.setLeft(rightNodeMostLeft.getRight());
    }
    this.size--;
    reBalance(parent);
    return false;
    }

    @Override
    protected void reBalance(Node<T> node) {
    while (node != null) {
    AVLNode<T> parent= (AVLNode<T>) node.getParent();
    if (!((AVLNode<T>)node).isBalance()) {
    int left = node.getLeft() == null ? 0 : ((AVLNode<T>)node.getLeft()).getLevel();
    int right = node.getRight() == null ? 0 : ((AVLNode<T>)node.getRight()).getLevel();
    if (left > right) {
    if (node.getLeft().getLeft() != null) {
    RightRotate(node);
    } else {
    LeftRotate((AVLNode<T>) node.getLeft());
    RightRotate(node);
    }
    } else {
    if (node.getRight().getRight() != null) {
    LeftRotate(node);
    } else {
    RightRotate((AVLNode<T>) node.getRight());
    LeftRotate(node);
    }
    }
    }
    node = parent;
    }
    }

    private void resetLevel(AVLNode<T> node) {
    node.setLevel(Math.max(node.getLeft() == null ? 0 : ((AVLNode<T>)node.getLeft()).getLevel(), node.getRight() == null ? 0 : ((AVLNode<T>)node.getRight()).getLevel()) + 1);
    }

    private void reset(AVLNode<T> node, AVLNode<T> parent, boolean isLeft, AVLNode<T> child) {
    resetLevel(node);
    resetLevel(child);
    if (isLeft) {
    parent.setLeft(child);
    } else {
    parent.setRight(child);
    }
    parent = (AVLNode<T>) child.getParent();
    while (parent != null) {
    resetLevel(parent);
    parent = (AVLNode<T>) parent.getParent();
    }
    }

    @Override
    protected void LeftRotate(Node<T> node) {
    AVLNode<T> parent = (AVLNode<T>) node.getParent();
    boolean isLeft = parent.getLeft() == node;
    AVLNode<T> rightNode = (AVLNode<T>) node.getRight();
    node.setRight(rightNode.getLeft());
    rightNode.setLeft(node);
    reset((AVLNode<T>) node, (AVLNode<T>) parent, isLeft, (AVLNode<T>) rightNode);
    }

    @Override
    protected void RightRotate(Node<T> node) {
    AVLNode<T> parent = (AVLNode<T>) node.getParent();
    boolean isLeft = parent.getLeft() == node;
    AVLNode<T> leftNode = (AVLNode<T>) node.getLeft();
    node.setLeft(leftNode.getRight());
    leftNode.setRight(node);
    reset((AVLNode<T>) node, (AVLNode<T>) parent, isLeft, (AVLNode<T>) leftNode);
    }
    }

RBTree

定义:

  1. 红黑树是二叉搜索树, 即红黑树的所有节点的左子树的值小于根节点的值小于右子树的值
  2. 红黑树的所有节点的左右子树的高度差不超过一倍
  3. 每个节点都有红色和黑色两种颜色
  4. 根节点和叶子节点的颜色是黑色
  5. 每条路径上的黑色节点个数相同
  6. 红色节点的子节点不能是红色

代码:

  • 节点代码

    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
    public class RBNode<T extends Comparable<T>> extends Node<T> {

    public RBNode(T value) {
    super(value);
    }

    public RBNode<T> getGrandParent() {
    return super.getParent() == null ? null : (RBNode<T>) super.getParent().getParent();
    }

    public RBNode<T> getUncle() {
    if (super.getParent() == null || super.getParent().getParent() == null) {
    return null;
    }
    if (super.getParent() == this.getGrandParent().getLeft()) {
    return (RBNode<T>) this.getGrandParent().getRight();
    } else {
    return (RBNode<T>) this.getGrandParent().getLeft();
    }
    }

    public boolean isRed() {
    return red;
    }

    public void setRed(boolean red) {
    this.red = red;
    }

    private boolean red;

    }
  • RB树代码

    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
    public class RBTree<T extends Comparable<T>> extends CanReBalanceBinarySearchTree<T> {

    @Override
    public boolean insert(T value) {
    if (super.contain(value)) {
    return false;
    }
    RBNode<T> insertNode = new RBNode<>(value);
    if (super.root == null) {
    insertNode.setRed(false);
    super.root = insertNode;
    super.size++;
    return true;
    }
    insertNode.setRed(true);
    RBNode<T> node = (RBNode<T>) super.root;
    while (node != null) {
    if (node.compareTo(insertNode) > 0) {
    if (node.getLeft() == null) {
    node.setLeft(insertNode);
    this.size++;
    reBalance(insertNode);
    return true;
    } else {
    node = (RBNode<T>) node.getLeft();
    }
    } else {
    if (node.getRight() == null) {
    node.setRight(insertNode);
    this.size++;
    reBalance(insertNode);
    return true;
    } else {
    node = (RBNode<T>) node.getRight();
    }
    }
    }
    return false;
    }

    @Override
    public boolean remove(T value) {
    if (!super.contain(value)) {
    return false;
    }
    if (super.size == 1) {
    super.size = 0;
    super.root = null;
    return true;
    }
    RBNode<T> removeNode = (RBNode<T>) super.find(value);
    RBNode<T> parent = (RBNode<T>) removeNode.getParent();
    if (removeNode.getLeft() == null) {
    if (parent == null) {
    this.root = removeNode.getRight();
    } else {
    if (removeNode == parent.getLeft()) {
    parent.setLeft(removeNode.getRight());
    } else {
    parent.setRight(removeNode.getRight());
    }
    }
    } else if (removeNode.getRight() == null) {
    if (parent == null) {
    this.root = removeNode.getLeft();
    } else {
    if (removeNode == parent.getLeft()) {
    parent.setLeft(removeNode.getLeft());
    } else {
    parent.setRight(removeNode.getLeft());
    }
    }
    } else {
    RBNode<T> rightNodeMostLeft = (RBNode<T>) removeNode.getRight();
    while (rightNodeMostLeft.getLeft() != null) {
    rightNodeMostLeft = (RBNode<T>) rightNodeMostLeft.getLeft();
    }
    removeNode.setValue(rightNodeMostLeft.getValue());
    if (rightNodeMostLeft == removeNode.getRight()) {
    removeNode.setRight(rightNodeMostLeft.getRight());
    }

    }

    throw new RuntimeException();
    }

    @Override
    protected void reBalance(Node<T> node) {
    RBNode<T> operatorNode = (RBNode<T>) node;
    while (operatorNode != null) {
    if (operatorNode.getParent() == null) {
    operatorNode.setRed(false);
    return;
    }
    if (((RBNode<T>)operatorNode.getParent()).isRed()) {
    RBNode<T> uncleNode = operatorNode.getUncle();
    if (uncleNode != null && uncleNode.isRed()) {
    ((RBNode<T>)operatorNode.getParent()).setRed(false);
    uncleNode.setRed(false);
    operatorNode.getGrandParent().setRed(true);
    operatorNode = operatorNode.getGrandParent();
    } else {
    if (operatorNode == operatorNode.getParent().getRight()) {
    operatorNode = (RBNode<T>) operatorNode.getParent();
    LeftRotate(operatorNode);
    } else {
    ((RBNode<T>) operatorNode.getParent()).setRed(false);
    operatorNode.getGrandParent().setRed(true);
    RBNode<T> tmp = operatorNode.getUncle();
    if (operatorNode.getGrandParent().getLeft() != null) {
    RightRotate(operatorNode.getGrandParent());
    operatorNode = tmp;
    } else {
    operatorNode = operatorNode.getGrandParent();
    }
    }
    }
    } else {
    break;
    }
    }
    }

    @Override
    protected void LeftRotate(Node<T> node) {
    RBNode<T> parent = (RBNode<T>) node.getParent();
    boolean isLeft = parent.getLeft() == node;
    RBNode<T> rightNode = (RBNode<T>) node.getRight();
    node.setRight(rightNode.getLeft());
    rightNode.setLeft(node);
    if (isLeft) {
    parent.setLeft(rightNode);
    } else {
    parent.setRight(rightNode);
    }
    }

    @Override
    protected void RightRotate(Node<T> node) {
    RBNode<T> parent = (RBNode<T>) node.getParent();
    boolean isLeft = parent.getLeft() == node;
    RBNode<T> leftNode = (RBNode<T>) node.getLeft();
    node.setLeft(leftNode.getRight());
    leftNode.setRight(node);
    if (isLeft) {
    parent.setLeft(leftNode);
    } else {
    parent.setRight(leftNode);
    }
    }
    }

SBTree

定义:

  1. SB树是二叉搜索树, 即SB树的所有节点的左子树的值小于根节点的值小于右子树的值
  2. SB树要求每棵子树的节点数量不能多余其节点叔叔所在树的节点数量

补充:

  1. AVL树是最平衡的二叉搜索树
  2. AVL树因为在每次插入或者删除节点时, 都可能调整平衡, 代价太大
  3. 红黑树和SB树都是在阉割AVL树的平衡性来达到降低调整频率的

操作:

  • 所有平衡二叉树的操作都是基于两种最基本的旋转的
  1. 左旋: 根节点变为右子节点的左子节点
    1
    2
    3
    4
    5
    6
    7
             [A]                                       [C]
    / \ / \
    [B] [C] ------> [A] [G]
    / \ / \ / \
    [D] [E] [F] [G] [B] [F]
    / \
    [D] [E]
  2. 右旋: 根节点变为左子节点的右子节点
    1
    2
    3
    4
    5
    6
    7
             [A]                                       [B]
    / \ / \
    [B] [C] ------> [D] [A]
    / \ / \ / \
    [D] [E] [F] [G] [E] [C]
    / \
    [F] [G]

插入

  1. AVL树在插入新节点的时候, 都会记录该节点属于哪一层, 通过这个层数来确定左右子树的高度差.
  2. 红黑树都会拥有自己父节点的指针, 以便旋转和染色的时候方便回溯.

删除

  1. 删除时, 可以使用左子树的最右节点代替待删除节点
  2. 删除时, 可以使用右子树的最左节点代替待删除节点
  • 本质上就是寻找中序遍历的待删除节点的前驱或后继来代替待删除节点