Skip to content

Commit 31597c9

Browse files
williamfisetwilliamfiset
committed
Added RB tree testing
1 parent 3c88c33 commit 31597c9

File tree

2 files changed

+63
-19
lines changed

2 files changed

+63
-19
lines changed

‎RedBlackTree/RedBlackTree.java

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -111,6 +111,7 @@ public boolean insert(T value) {
111111
if (root == null) {
112112
root = new Node(value, null);
113113
insertionRelabel(root);
114+
nodeCount++;
114115
return true;
115116
}
116117

@@ -123,6 +124,7 @@ public boolean insert(T value) {
123124
if (node.left == null) {
124125
node.left = new Node(value, node);
125126
insertionRelabel(node.left);
127+
nodeCount++;
126128
return true;
127129
}
128130
node = node.left;
@@ -132,6 +134,7 @@ public boolean insert(T value) {
132134
if (node.right == null) {
133135
node.right = new Node(value, node);
134136
insertionRelabel(node.right);
137+
nodeCount++;
135138
return true;
136139
}
137140
node = node.right;

‎RedBlackTree/tests/RedBlackTreeTest.java

Lines changed: 60 additions & 19 deletions
Original file line numberDiff line numberDiff line change
@@ -45,11 +45,8 @@ public void testLeftLeftRotation() {
4545
assertEquals(tree.root, tree.root.left.parent);
4646
assertEquals(tree.root, tree.root.right.parent);
4747

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);
48+
assertNullChildren(tree.root.left, tree.root.right);
49+
assertCorrectParentLinks(tree.root, null);
5350

5451
}
5552

@@ -71,11 +68,8 @@ public void testLeftRightRotation() {
7168
assertEquals(tree.root, tree.root.left.parent);
7269
assertEquals(tree.root, tree.root.right.parent);
7370

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);
71+
assertNullChildren(tree.root.left, tree.root.right);
72+
assertCorrectParentLinks(tree.root, null);
7973

8074
}
8175

@@ -97,11 +91,8 @@ public void testRightLeftRotation() {
9791
assertEquals(tree.root, tree.root.left.parent);
9892
assertEquals(tree.root, tree.root.right.parent);
9993

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);
94+
assertNullChildren(tree.root.left, tree.root.right);
95+
assertCorrectParentLinks(tree.root, null);
10596

10697
}
10798

@@ -123,12 +114,62 @@ public void testRightRightRotation() {
123114
assertEquals(tree.root, tree.root.left.parent);
124115
assertEquals(tree.root, tree.root.right.parent);
125116

126-
assertNull(tree.root.parent);
127-
assertNull(tree.root.left.left);
128-
assertNull(tree.root.left.right);
117+
assertNullChildren(tree.root.left, tree.root.right);
118+
assertCorrectParentLinks(tree.root, null);
119+
120+
}
121+
122+
@Test
123+
public void testLeftRedUncleCase() {
124+
125+
tree.insert(1);
126+
tree.insert(2);
127+
tree.insert(3);
128+
tree.insert(4);
129+
130+
assertEquals(2, tree.root.value.intValue());
131+
assertEquals(1, tree.root.left.value.intValue());
132+
assertEquals(3, tree.root.right.value.intValue());
133+
assertEquals(4, tree.root.right.right.value.intValue());
134+
135+
assertEquals(RedBlackTree.BLACK, tree.root.color);
136+
assertEquals(RedBlackTree.BLACK, tree.root.left.color);
137+
assertEquals(RedBlackTree.BLACK, tree.root.right.color);
138+
assertEquals(RedBlackTree.RED, tree.root.right.right.color);
139+
129140
assertNull(tree.root.right.left);
130-
assertNull(tree.root.right.right);
141+
assertNullChildren(tree.root.left, tree.root.right.right);
142+
assertCorrectParentLinks(tree.root, null);
143+
144+
tree.insert(5);
145+
146+
assertEquals(2, tree.root.value.intValue());
147+
assertEquals(1, tree.root.left.value.intValue());
148+
assertEquals(4, tree.root.right.value.intValue());
149+
assertEquals(3, tree.root.right.left.value.intValue());
150+
assertEquals(5, tree.root.right.right.value.intValue());
151+
152+
assertEquals(RedBlackTree.BLACK, tree.root.color);
153+
assertEquals(RedBlackTree.BLACK, tree.root.left.color);
154+
assertEquals(RedBlackTree.BLACK, tree.root.right.color);
155+
assertEquals(RedBlackTree.RED, tree.root.right.left.color);
156+
assertEquals(RedBlackTree.RED, tree.root.right.right.color);
157+
assertCorrectParentLinks(tree.root, null);
158+
159+
}
160+
161+
static void assertNullChildren(RedBlackTree.Node... nodes) {
162+
for (RedBlackTree.Node node : nodes) {
163+
assertNull(node.left);
164+
assertNull(node.right);
165+
}
166+
}
131167

168+
static void assertCorrectParentLinks(RedBlackTree.Node node, RedBlackTree.Node parent) {
169+
if (node == null) return;
170+
assertEquals(node.parent, parent);
171+
assertCorrectParentLinks(node.left, node);
172+
assertCorrectParentLinks(node.right, node);
132173
}
133174

134175
static List<Integer> genRandList(int sz) {

0 commit comments

Comments
 (0)