-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathRedBlackTree.java
More file actions
124 lines (99 loc) · 2.75 KB
/
RedBlackTree.java
File metadata and controls
124 lines (99 loc) · 2.75 KB
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
/**
* Learn from 《Algorithms 4th edition》
* @param <Key>
* @param <Value>
*/
public class RedBlackTree<Key extends Comparable<Key>, Value> {
private static final boolean RED = true;
private static final boolean BLACK = false;
private Node root;
public void put(Key key, Value val)
{ // Search for key. Update value if found; grow table if new.
root = put(root, key, val);
root.color = BLACK;
}
private Node put(Node h, Key key, Value val)
{
if (h == null) {
// Do standard insert, with red link to parent.
return new Node(key, val, 1, RED);
}
int cmp = key.compareTo(h.key);
if (cmp < 0) {
h.left = put(h.left, key, val);
} else if (cmp > 0) {
h.right = put(h.right, key, val);
} else {
h.value = val;
}
if (h.right.isRed() && !h.left.isRed()) {
h = rotateLeft(h);
}
if (h.left.isRed()&& h.left.left.isRed()) {
h = rotateRight(h);
}
if (h.left.isRed() && h.right.isRed()) {
flipColors(h);
}
h.numberOfNodesInThisSubtree = size(h.left) + size(h.right) + 1;
return h;
}
public boolean isRed(Node node) {
return node.isRed();
}
Node rotateLeft(Node h)
{
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
x.numberOfNodesInThisSubtree = h.numberOfNodesInThisSubtree;
h.numberOfNodesInThisSubtree = 1 + size(h.left)
+ size(h.right);
return x;
}
Node rotateRight(Node h)
{
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
x.numberOfNodesInThisSubtree = h.numberOfNodesInThisSubtree;
h.numberOfNodesInThisSubtree = 1 + size(h.left)
+ size(h.right);
return x;
}
void flipColors(Node h)
{
h.color = RED;
h.left.color = BLACK;
h.right.color = BLACK;
}
public int size(Node node) {
if(node == null){
return 0;
}
return node.numberOfNodesInThisSubtree;
}
public class Node {
public Key key;
public Value value;
public Node left;
public Node right;
public int numberOfNodesInThisSubtree;
public boolean color; // link from parent
Node(Key key, Value val, int N, boolean color)
{
this.key = key;
this.value = val;
this.numberOfNodesInThisSubtree = N;
this.color = color;
}
public boolean isRed()
{
return this.color == RED;
}
}
}