Skip to content

Commit 38541d7

Browse files
williamfisetwilliamfiset
committed
refactored
1 parent 4ec05c8 commit 38541d7

File tree

3 files changed

+46
-65
lines changed

3 files changed

+46
-65
lines changed

‎RedBlackTree/RedBlackTree.java

Lines changed: 25 additions & 64 deletions
Original file line numberDiff line numberDiff line change
@@ -44,14 +44,11 @@ public Node getRight() {
4444

4545
@Override
4646
public String getText() {
47-
// return String.valueOf(value) + "("+(color==RED?"r":"b")+","+(parent==null?null:parent.value)+")";
48-
return String.valueOf(value) +
49-
" " + (color==RED?"r":"b")
50-
+ " ("
51-
+(left==null?"N":left.value)+","
52-
+(right==null?"N":right.value)+","
53-
+(parent==null?"N":parent.value)
54-
+")";
47+
return String.valueOf(value) + (color == RED ? " r" : " b") + " ("
48+
+ (left == null ? "N" : left.value) + ","
49+
+ (right == null ? "N" : right.value) + ","
50+
+ (parent == null ? "N" : parent.value)
51+
+ ")";
5552
}
5653

5754
@Override
@@ -61,7 +58,7 @@ public String toString() {
6158

6259
}
6360

64-
// The root node of the AVL tree.
61+
// The root node of the RB tree.
6562
Node root;
6663

6764
// Tracks the number of nodes inside the tree.
@@ -96,20 +93,24 @@ public boolean contains(T value) {
9693
// Recursive contains helper method.
9794
private boolean contains(Node node, T value) {
9895

99-
if (node == null) return false;
96+
if (node == null || value == null) return false;
10097

101-
// Compare current value to the value in the node.
102-
int cmp = value.compareTo(node.value);
98+
while(node != null) {
10399

104-
// Dig into left subtree.
105-
if (cmp < 0) return contains(node.left, value);
100+
// Compare current value to the value in the node.
101+
int cmp = value.compareTo(node.value);
102+
103+
// Dig into left subtree.
104+
if (cmp < 0) node = node.left;
106105

107-
// Dig into right subtree.
108-
if (cmp > 0) return contains(node.right, value);
106+
// Dig into right subtree.
107+
else if (cmp > 0) node = node.right;
109108

110-
// Found value in tree.
111-
return true;
109+
// Found value in tree.
110+
else return true;
111+
}
112112

113+
return false;
113114
}
114115

115116
public boolean insert(T value) {
@@ -165,6 +166,7 @@ private void insertionRelabel(Node node) {
165166
root = node;
166167
return;
167168
}
169+
168170
Node grandParent = parent.parent;
169171

170172
// Tree has a height of one, in which case the root is black
@@ -180,7 +182,6 @@ private void insertionRelabel(Node node) {
180182
boolean parentIsRightChild = !parentIsLeftChild;
181183

182184
Node uncle = parentIsLeftChild ? grandParent.right : grandParent.left;
183-
184185
boolean uncleIsRedNode = (uncle == null) ? BLACK : uncle.color;
185186

186187
if (uncleIsRedNode) {
@@ -340,55 +341,15 @@ public void remove() {
340341
};
341342
}
342343

343-
// Make sure all left child nodes are smaller in value than their parent and
344-
// make sure all right child nodes are greater in value than their parent.
345-
// (Used only for testing)
346-
boolean validateBinarySearchTreeInvariant(Node node) {
347-
if (node == null) return true;
348-
T val = node.value;
349-
boolean isValid = true;
350-
if (node.left != null) isValid = isValid && node.left.value.compareTo(val) < 0;
351-
if (node.right != null) isValid = isValid && node.right.value.compareTo(val) > 0;
352-
return isValid && validateBinarySearchTreeInvariant(node.left) && validateBinarySearchTreeInvariant(node.right);
353-
}
354-
355-
// Used for testing.
356-
boolean validateParentLinksAreCorrect(Node node, Node parent) {
357-
if (node == null) return true;
358-
if (node.parent != parent) return false;
359-
return validateParentLinksAreCorrect(node.left, node) && validateParentLinksAreCorrect(node.right, node);
360-
}
361-
362344
public static void main(String[] args) {
363345

364-
// int[] values = {88, 94, 99, 32, 3, 48, 93, 62, 85};
365-
// RedBlackTree<Integer> rbTree = new RedBlackTree<>();
366-
// for (int v : values) {
367-
// System.out.println("======================================================================================================================================================================================");
368-
// System.out.println("INSERTING: " + v);
369-
// rbTree.insert(v);
370-
// System.out.println("PARENT LINK STATUS: " + rbTree.validateParentLinksAreCorrect(rbTree.root, null));
371-
// rbTree.display();
372-
// }
373-
374-
outer:
375-
for (int loop = 0; loop < 1000000; loop++) {
376-
RedBlackTree<Integer> rbTree = new RedBlackTree<>();
377-
List<Integer> ar = new ArrayList<>();
378-
for (int i = 0; i < 9; i++) ar.add((int)(Math.random() * 100));
379-
for (int j = 0; j < ar.size(); j++) {
380-
rbTree.insert(ar.get(j));
381-
boolean inv = rbTree.validateBinarySearchTreeInvariant(rbTree.root);
382-
if (!inv) {
383-
System.out.println("BROKE AT INDEX: " + j);
384-
System.out.println(ar);
385-
rbTree.display();
386-
break outer;
387-
}
388-
}
346+
int[] values = {88, 94, 99, 32, 3, 48, 93, 62, 85};
347+
RedBlackTree<Integer> rbTree = new RedBlackTree<>();
348+
for (int v : values) {
349+
rbTree.insert(v);
350+
rbTree.display();
389351
}
390352

391-
392353
}
393354

394355
}

‎RedBlackTree/test_rb_tree renamed to ‎RedBlackTree/runTests.sh

File renamed without changes.

‎RedBlackTree/tests/RedBlackTreeTest.java

Lines changed: 21 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -244,7 +244,8 @@ public void testRandomizedValueInsertionsAgainstTreeSet() {
244244
int v = randValue();
245245
assertEquals(set.add(v), tree.insert(v));
246246
assertEquals(set.size(), tree.size());
247-
assertTrue(tree.validateBinarySearchTreeInvariant(tree.root));
247+
assertTrue(tree.contains(v));
248+
assertBinarySearchTreeInvariant(tree.root);
248249
// validateRedBlackTreeInvariant
249250
}
250251

@@ -310,6 +311,25 @@ static void assertCorrectParentLinks(RedBlackTree.Node node, RedBlackTree.Node p
310311
assertCorrectParentLinks(node.right, node);
311312
}
312313

314+
// Make sure all left child nodes are smaller in value than their parent and
315+
// make sure all right child nodes are greater in value than their parent.
316+
// (Used only for testing)
317+
boolean assertBinarySearchTreeInvariant(RedBlackTree.Node node) {
318+
if (node == null) return true;
319+
boolean isValid = true;
320+
if (node.left != null) isValid = isValid && node.left.value.compareTo(node.value) < 0;
321+
if (node.right != null) isValid = isValid && node.right.value.compareTo(node.value) > 0;
322+
return isValid && assertBinarySearchTreeInvariant(node.left) && assertBinarySearchTreeInvariant(node.right);
323+
}
324+
325+
// Used for testing.
326+
boolean validateParentLinksAreCorrect(RedBlackTree.Node node, RedBlackTree.Node parent) {
327+
if (node == null) return true;
328+
if (node.parent != parent) return false;
329+
return validateParentLinksAreCorrect(node.left, node) && validateParentLinksAreCorrect(node.right, node);
330+
}
331+
332+
313333
static List<Integer> genRandList(int sz) {
314334
List <Integer> lst = new ArrayList<>(sz);
315335
for (int i = 0; i < sz; i++) lst.add(i); // unique values.

0 commit comments

Comments
 (0)