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
| package com;
public class RedBlackTree<Key extends Comparable<Key>, Value> {
private class Node {
public Key key;
public Value value;
public Node left;
public Node right;
public boolean color;
public Node(Key key, Value value, Node left, Node right, boolean color) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
this.color = color;
}
}
private Node root;
private int redBlackTreeLength;
private static final boolean RED = true;
private static final boolean Black = false;
RedBlackTree() {
}
// 获取树中元素的个数
public int size() {
return redBlackTreeLength;
}
// 判断当前结点的父结点指向是否为红色
private boolean isRed(Node node) {
if (node==null) {
return false;
}
return node.color==RED;
}
// 左旋调整
private Node rotateLeft(Node head) {
// 获取右子结点为son
Node son = head.right;
// 把head的右子结点改为son的左子结点
head.right = son.left;
// 把son的左子结点改为head
son.left = head;
// 把son的颜色改为head以前的颜色
son.color = head.color;
// 把head的颜色改为红色
head.color = RED;
return son;
}
// 右旋调整
private Node rotateRight(Node head) {
// 获取做子结点为son
Node son = head.left;
// 把head的左子结点改为son的右子结点
head.left = son.right;
// 把son的右子结点改为head
son.right = head;
// 把son的颜色改为head以前的颜色
son.color = head.color;
// 把head的颜色改为红色
head.color = RED;
return son;
}
// 颜色反转（完全拆分4- 结点）
private void flipColors(Node head) {
head.right.color = Black;
head.left.color = Black;
head.color = RED;
}
// 在整个树上插入一个元素
public void put(Key key, Value value) {
root = put(root, key, value);
// 跟结点的颜色总是黑色
root.color = Black;
}
// 在指定子树上插入一个元素
private Node put(Node node, Key key, Value value) {
// 判断node是否为空，如果为空，就直接返回一个新的红色结点
if (node == null) {
redBlackTreeLength++;
return new Node(key, value, null, null, RED);
}
// 比较node结点的ke的大小
int cmp = key.compareTo(node.key);
if (cmp<0) {
// 继续往左
node.left = put(node.left, key, value);
} else if (cmp>0) {
// 继续往右
node.right = put(node.right, key, value);
} else {
// 发生值的替换
node.value = value;
}
// 进行左旋：当前结点的左子结点为黑色，右子结点为红色时，需要进行左旋
if (!isRed(node.left) && isRed(node.right)) {
node = rotateLeft(node);
}
// 进行右旋：当前结点的左子结点为红色，当前结点的左子结点的左子结点也为红色时，需要进行右旋
if (isRed(node.left) && isRed(node.left.left)) {
node = rotateRight(node);
}
// 进行颜色反转：当前结点的左子结点为红色，当前结点的右子结点也为红色时，需要进行颜色反转
if (isRed(node.left) && isRed(node.right)) {
flipColors(node);
}
return node;
}
// 在整个树中，通过键获取值
public Value get(Key key) {
return get(root, key);
}
// 在指定树中，通过键获取值
private Value get(Node node, Key key) {
if (node==null) {
return null;
}
// 比较键的大小
int cmp = key.compareTo(node.key);
if (cmp<0) {
// 继续向左查找
return get(node.left.key);
} else if (cmp>0) {
// 继续向右查找
return get(node.right.key);
} else {
return node.value;
}
}
}
|