Exploring 3 types of self-balancing binary search trees- AVL, Red-Black, and Left Leaning Read-Black.
For all three types of balancing strategies, remove is not implemented- only insert. After a node is inserted, a fix up method will be used to repair the tree- possibly rotating, coloring, or recomputing.
Maintains pairs of self balancing sub-trees that can differ in height by at most 1.
- Fix up method is found in
impl/AVLBSTMap.java
- Tested empirically (with JUnit cases) using
test/AVLBSTMTest.java
Maintains pairs of self balancing sub-trees where each node has an attached boolean that holds red or black. This coloring scheme is used with invariants to measure how unbalanced a tree can become, before a fix up is required.
- Fix up method is found in
impl/TraditionalRedBlackTreeMap.java
- Tested empirically (with JUnit cases) using
test/TRBBSTMTest.java
Maintains pairs of self balancing sub-trees where each left node has an attached boolean that holds red or black. This coloring scheme is used with invariants to measure how unbalanced a tree can become, before a fix up is required. For LLRBT's right nodes will not remain red after a fix up is processed.
- Fix up method is found in
impl/LLRedBlackTreeMap.java
- Tested empirically (with JUnit cases) using
test/LLRBTMTest.java
Note: Basic project stub, outline, and test cases are written by Dr. Thomas VanDrunen of Wheaton College (IL)