Skip to content

Commit 2685dab

Browse files
williamfisetwilliamfiset
committed
Added RB tree insert method tests
1 parent 63a261f commit 2685dab

File tree

3 files changed

+122
-24
lines changed

3 files changed

+122
-24
lines changed

‎.DS_Store

-2 KB
Binary file not shown.

‎RedBlackTree/RedBlackTree.java

Lines changed: 40 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -42,7 +42,12 @@ public Node getRight() {
4242

4343
@Override
4444
public String getText() {
45-
return String.valueOf(value);
45+
return String.valueOf(value) + "("+(color==RED?"r":"b")+")";
46+
}
47+
48+
@Override
49+
public String toString() {
50+
return getText();
4651
}
4752

4853
}
@@ -111,7 +116,7 @@ public boolean insert(T value) {
111116

112117
for(Node node = root;;) {
113118

114-
int cmp = node.value.compareTo(value);
119+
int cmp = value.compareTo(node.value);
115120

116121
// Left subtree.
117122
if (cmp < 0) {
@@ -174,23 +179,36 @@ private void insertionRelabel(Node node) {
174179

175180
} else {
176181

182+
// System.out.println("HERE");
183+
177184
// Left-left case.
178185
if (parentIsLeftChild && nodeIsLeftChild) {
186+
System.out.println("Left-left case.");
179187
grandParent = leftLeftCase(grandParent);
180188

181189
// Left-right case.
182190
} else if (parentIsLeftChild && nodeIsRightChild) {
191+
192+
System.out.println("Left-right case");
183193
grandParent = leftRightCase(grandParent);
184-
194+
// System.out.println("GP: " + grandParent.getText());
195+
// System.out.println( (grandParent.left==null?"null":grandParent.left.getText()) + " - " + (grandParent.right==null?"null":grandParent.right.getText()));
196+
185197
// Right-left case.
186198
} else if (parentIsRightChild && nodeIsLeftChild) {
199+
System.out.println("Right-left case.");
187200
grandParent = rightLeftCase(grandParent);
188201

189202
// Right-right case.
190203
} else {
204+
System.out.println("Right-right case.");
191205
grandParent = rightRightCase(grandParent);
192206
}
193207

208+
if (grandParent.parent == null) {
209+
root = grandParent;
210+
}
211+
194212
}
195213

196214
insertionRelabel(grandParent);
@@ -205,8 +223,7 @@ private Node leftLeftCase(Node node) {
205223

206224
private Node leftRightCase(Node node) {
207225
node.left = leftRotate(node.left);
208-
leftLeftCase(node);
209-
return node;
226+
return leftLeftCase(node);
210227
}
211228

212229
private Node rightRightCase(Node node) {
@@ -217,8 +234,7 @@ private Node rightRightCase(Node node) {
217234

218235
private Node rightLeftCase(Node node) {
219236
node.right = rightRotate(node.right);
220-
rightRightCase(node);
221-
return node;
237+
return rightRightCase(node);
222238
}
223239

224240
private Node rightRotate(Node parent) {
@@ -231,8 +247,6 @@ private Node rightRotate(Node parent) {
231247
child.parent = grandParent;
232248
parent.parent = child;
233249

234-
updateParentChildLink(grandParent, parent, child);
235-
236250
return child;
237251
}
238252

@@ -246,23 +260,21 @@ private Node leftRotate(Node parent) {
246260
child.parent = grandParent;
247261
parent.parent = child;
248262

249-
updateParentChildLink(grandParent, parent, child);
250-
251263
return child;
252264
}
253265

254266
// Sometimes the left or right child node of a parent changes and the
255267
// parent's reference needs to be updated to point to the new child.
256268
// This is a helper method to do just that.
257-
private void updateParentChildLink(Node parent, Node oldChild, Node newChild) {
258-
if (parent != null) {
259-
if (parent.left == oldChild) {
260-
parent.left = newChild;
261-
} else {
262-
parent.right = newChild;
263-
}
264-
}
265-
}
269+
// private void updateParentChildLink(Node parent, Node oldChild, Node newChild) {
270+
// if (parent != null) {
271+
// if (parent.left == oldChild) {
272+
// parent.left = newChild;
273+
// } else {
274+
// parent.right = newChild;
275+
// }
276+
// }
277+
// }
266278

267279
// Helper method to find the leftmost node (which has the smallest value)
268280
private Node findMin(Node node) {
@@ -332,6 +344,14 @@ public void remove() {
332344

333345
public static void main(String[] args) {
334346

347+
RedBlackTree<Integer> rbTree = new RedBlackTree<>();
348+
int[] values = {9,8,4,3,7,6,5,2,1,0};
349+
for (int v : values) {
350+
rbTree.insert(v);
351+
rbTree.display();
352+
System.out.println("------------------------------------------------------------------------------");
353+
}
354+
335355
}
336356

337357
}

‎RedBlackTree/tests/RedBlackTreeTest.java

Lines changed: 82 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -17,16 +17,94 @@ public void setup() {
1717
tree = new RedBlackTree<>();
1818
}
1919

20-
// @Test(expected=IllegalArgumentException.class)
21-
// public void testNullInsertion() {
22-
// tree.insert(null);
23-
// }
20+
@Test(expected=IllegalArgumentException.class)
21+
public void testNullInsertion() {
22+
tree.insert(null);
23+
}
2424

2525
@Test
2626
public void testTreeContainsNull() {
2727
assertFalse(tree.contains(null));
2828
}
2929

30+
@Test
31+
public void testLeftLeftRotation() {
32+
33+
tree.insert(3);
34+
tree.insert(2);
35+
tree.insert(1);
36+
37+
assertEquals(2, tree.root.value.intValue());
38+
assertEquals(1, tree.root.left.value.intValue());
39+
assertEquals(3, tree.root.right.value.intValue());
40+
41+
assertEquals(RedBlackTree.BLACK, tree.root.color);
42+
assertEquals(RedBlackTree.RED, tree.root.left.color);
43+
assertEquals(RedBlackTree.RED, tree.root.right.color);
44+
45+
assertEquals(tree.root, tree.root.left.parent);
46+
assertEquals(tree.root, tree.root.right.parent);
47+
48+
assertNull(tree.root.parent);
49+
assertNull(tree.root.left.left);
50+
assertNull(tree.root.left.right);
51+
assertNull(tree.root.right.left);
52+
assertNull(tree.root.right.right);
53+
54+
}
55+
56+
@Test
57+
public void testLeftRightRotation() {
58+
59+
tree.insert(3);
60+
tree.insert(1);
61+
tree.insert(2);
62+
63+
assertEquals(2, tree.root.value.intValue());
64+
assertEquals(1, tree.root.left.value.intValue());
65+
assertEquals(3, tree.root.right.value.intValue());
66+
67+
assertEquals(RedBlackTree.BLACK, tree.root.color);
68+
assertEquals(RedBlackTree.RED, tree.root.left.color);
69+
assertEquals(RedBlackTree.RED, tree.root.right.color);
70+
71+
assertEquals(tree.root, tree.root.left.parent);
72+
assertEquals(tree.root, tree.root.right.parent);
73+
74+
assertNull(tree.root.parent);
75+
assertNull(tree.root.left.left);
76+
assertNull(tree.root.left.right);
77+
assertNull(tree.root.right.left);
78+
assertNull(tree.root.right.right);
79+
80+
}
81+
82+
@Test
83+
public void testRightLeftRotation() {
84+
85+
tree.insert(1);
86+
tree.insert(3);
87+
tree.insert(2);
88+
89+
assertEquals(2, tree.root.value.intValue());
90+
assertEquals(1, tree.root.left.value.intValue());
91+
assertEquals(3, tree.root.right.value.intValue());
92+
93+
assertEquals(RedBlackTree.BLACK, tree.root.color);
94+
assertEquals(RedBlackTree.RED, tree.root.left.color);
95+
assertEquals(RedBlackTree.RED, tree.root.right.color);
96+
97+
assertEquals(tree.root, tree.root.left.parent);
98+
assertEquals(tree.root, tree.root.right.parent);
99+
100+
assertNull(tree.root.parent);
101+
assertNull(tree.root.left.left);
102+
assertNull(tree.root.left.right);
103+
assertNull(tree.root.right.left);
104+
assertNull(tree.root.right.right);
105+
106+
}
107+
30108
static List<Integer> genRandList(int sz) {
31109
List <Integer> lst = new ArrayList<>(sz);
32110
for (int i = 0; i < sz; i++) lst.add(i); // unique values.

0 commit comments

Comments
 (0)