Skip to content

Commit 55c3aac

Browse files
author
Christian Bender
authored
Merge pull request TheAlgorithms#428 from jack870131/PR-Test
Red Black Tree Implementation (Java)
2 parents 595cc8f + 384f588 commit 55c3aac

File tree

1 file changed

+330
-0
lines changed

1 file changed

+330
-0
lines changed

‎Data Structures/Trees/RedBlackBST.java

Lines changed: 330 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,330 @@
1+
/**
2+
*
3+
* @author jack870131
4+
*/
5+
public class RedBlackBST {
6+
7+
private final int R = 0;
8+
private final int B = 1;
9+
10+
private class Node {
11+
12+
int key = -1, color = B;
13+
Node left = nil, right = nil, p = nil;
14+
15+
Node(int key) {
16+
this.key = key;
17+
}
18+
}
19+
20+
private final Node nil = new Node(-1);
21+
private Node root = nil;
22+
23+
public void printTree(Node node) {
24+
if (node == nil) {
25+
return;
26+
}
27+
printTree(node.left);
28+
System.out.print(((node.color == R) ? " R " : " B ") + "Key: " + node.key + " Parent: " + node.p.key + "\n");
29+
printTree(node.right);
30+
}
31+
32+
public void printTreepre(Node node) {
33+
if (node == nil) {
34+
return;
35+
}
36+
System.out.print(((node.color == R) ? " R " : " B ") + "Key: " + node.key + " Parent: " + node.p.key + "\n");
37+
printTree(node.left);
38+
printTree(node.right);
39+
}
40+
41+
private Node findNode(Node findNode, Node node) {
42+
if (root == nil) {
43+
return null;
44+
}
45+
if (findNode.key < node.key) {
46+
if (node.left != nil) {
47+
return findNode(findNode, node.left);
48+
}
49+
} else if (findNode.key > node.key) {
50+
if (node.right != nil) {
51+
return findNode(findNode, node.right);
52+
}
53+
} else if (findNode.key == node.key) {
54+
return node;
55+
}
56+
return null;
57+
}
58+
59+
private void insert(Node node) {
60+
Node temp = root;
61+
if (root == nil) {
62+
root = node;
63+
node.color = B;
64+
node.p = nil;
65+
} else {
66+
node.color = R;
67+
while (true) {
68+
if (node.key < temp.key) {
69+
if (temp.left == nil) {
70+
temp.left = node;
71+
node.p = temp;
72+
break;
73+
} else {
74+
temp = temp.left;
75+
}
76+
} else if (node.key >= temp.key) {
77+
if (temp.right == nil) {
78+
temp.right = node;
79+
node.p = temp;
80+
break;
81+
} else {
82+
temp = temp.right;
83+
}
84+
}
85+
}
86+
fixTree(node);
87+
}
88+
}
89+
90+
private void fixTree(Node node) {
91+
while (node.p.color == R) {
92+
Node y = nil;
93+
if (node.p == node.p.p.left) {
94+
y = node.p.p.right;
95+
96+
if (y != nil && y.color == R) {
97+
node.p.color = B;
98+
y.color = B;
99+
node.p.p.color = R;
100+
node = node.p.p;
101+
continue;
102+
}
103+
if (node == node.p.right) {
104+
node = node.p;
105+
rotateLeft(node);
106+
}
107+
node.p.color = B;
108+
node.p.p.color = R;
109+
rotateRight(node.p.p);
110+
} else {
111+
y = node.p.p.left;
112+
if (y != nil && y.color == R) {
113+
node.p.color = B;
114+
y.color = B;
115+
node.p.p.color = R;
116+
node = node.p.p;
117+
continue;
118+
}
119+
if (node == node.p.left) {
120+
node = node.p;
121+
rotateRight(node);
122+
}
123+
node.p.color = B;
124+
node.p.p.color = R;
125+
rotateLeft(node.p.p);
126+
}
127+
}
128+
root.color = B;
129+
}
130+
131+
void rotateLeft(Node node) {
132+
if (node.p != nil) {
133+
if (node == node.p.left) {
134+
node.p.left = node.right;
135+
} else {
136+
node.p.right = node.right;
137+
}
138+
node.right.p = node.p;
139+
node.p = node.right;
140+
if (node.right.left != nil) {
141+
node.right.left.p = node;
142+
}
143+
node.right = node.right.left;
144+
node.p.left = node;
145+
} else {
146+
Node right = root.right;
147+
root.right = right.left;
148+
right.left.p = root;
149+
root.p = right;
150+
right.left = root;
151+
right.p = nil;
152+
root = right;
153+
}
154+
}
155+
156+
void rotateRight(Node node) {
157+
if (node.p != nil) {
158+
if (node == node.p.left) {
159+
node.p.left = node.left;
160+
} else {
161+
node.p.right = node.left;
162+
}
163+
164+
node.left.p = node.p;
165+
node.p = node.left;
166+
if (node.left.right != nil) {
167+
node.left.right.p = node;
168+
}
169+
node.left = node.left.right;
170+
node.p.right = node;
171+
} else {
172+
Node left = root.left;
173+
root.left = root.left.right;
174+
left.right.p = root;
175+
root.p = left;
176+
left.right = root;
177+
left.p = nil;
178+
root = left;
179+
}
180+
}
181+
182+
void transplant(Node target, Node with) {
183+
if (target.p == nil) {
184+
root = with;
185+
} else if (target == target.p.left) {
186+
target.p.left = with;
187+
} else
188+
target.p.right = with;
189+
with.p = target.p;
190+
}
191+
192+
Node treeMinimum(Node subTreeRoot) {
193+
while (subTreeRoot.left != nil) {
194+
subTreeRoot = subTreeRoot.left;
195+
}
196+
return subTreeRoot;
197+
}
198+
199+
boolean delete(Node z) {
200+
if ((z = findNode(z, root)) == null)
201+
return false;
202+
Node x;
203+
Node y = z;
204+
int yorigcolor = y.color;
205+
206+
if (z.left == nil) {
207+
x = z.right;
208+
transplant(z, z.right);
209+
} else if (z.right == nil) {
210+
x = z.left;
211+
transplant(z, z.left);
212+
} else {
213+
y = treeMinimum(z.right);
214+
yorigcolor = y.color;
215+
x = y.right;
216+
if (y.p == z)
217+
x.p = y;
218+
else {
219+
transplant(y, y.right);
220+
y.right = z.right;
221+
y.right.p = y;
222+
}
223+
transplant(z, y);
224+
y.left = z.left;
225+
y.left.p = y;
226+
y.color = z.color;
227+
}
228+
if (yorigcolor == B)
229+
deleteFixup(x);
230+
return true;
231+
}
232+
233+
void deleteFixup(Node x) {
234+
while (x != root && x.color == B) {
235+
if (x == x.p.left) {
236+
Node w = x.p.right;
237+
if (w.color == R) {
238+
w.color = B;
239+
x.p.color = R;
240+
rotateLeft(x.p);
241+
w = x.p.right;
242+
}
243+
if (w.left.color == B && w.right.color == B) {
244+
w.color = R;
245+
x = x.p;
246+
continue;
247+
} else if (w.right.color == B) {
248+
w.left.color = B;
249+
w.color = R;
250+
rotateRight(w);
251+
w = x.p.right;
252+
}
253+
if (w.right.color == R) {
254+
w.color = x.p.color;
255+
x.p.color = B;
256+
w.right.color = B;
257+
rotateLeft(x.p);
258+
x = root;
259+
}
260+
} else {
261+
Node w = x.p.left;
262+
if (w.color == R) {
263+
w.color = B;
264+
x.p.color = R;
265+
rotateRight(x.p);
266+
w = x.p.left;
267+
}
268+
if (w.right.color == B && w.left.color == B) {
269+
w.color = R;
270+
x = x.p;
271+
continue;
272+
} else if (w.left.color == B) {
273+
w.right.color = B;
274+
w.color = R;
275+
rotateLeft(w);
276+
w = x.p.left;
277+
}
278+
if (w.left.color == R) {
279+
w.color = x.p.color;
280+
x.p.color = B;
281+
w.left.color = B;
282+
rotateRight(x.p);
283+
x = root;
284+
}
285+
}
286+
}
287+
x.color = B;
288+
}
289+
290+
public void insertDemo() {
291+
Scanner scan = new Scanner(System.in);
292+
while (true) {
293+
System.out.println("Add items");
294+
295+
int item;
296+
Node node;
297+
298+
item = scan.nextInt();
299+
while (item != -999) {
300+
node = new Node(item);
301+
insert(node);
302+
item = scan.nextInt();
303+
}
304+
printTree(root);
305+
System.out.println("Pre order");
306+
printTreepre(root);
307+
break;
308+
}
309+
}
310+
311+
public void deleteDemo() {
312+
Scanner scan = new Scanner(System.in);
313+
System.out.println("Delete items");
314+
int item;
315+
Node node;
316+
item = scan.nextInt();
317+
node = new Node(item);
318+
System.out.print("Deleting item " + item);
319+
if (delete(node)) {
320+
System.out.print(": deleted!");
321+
} else {
322+
System.out.print(": does not exist!");
323+
}
324+
325+
System.out.println();
326+
printTree(root);
327+
System.out.println("Pre order");
328+
printTreepre(root);
329+
}
330+
}

0 commit comments

Comments
 (0)