Red-black trees

COIS 2020H Assignment 5
AVL( 1 mark: note you are getting 2 from the lab on AVL trees)
AVL: Deletion
AVL: modified to support generics, with testing
Splay (2 marks total)
Splay: Insertion
Splay: Find
Splay: Deletion
Splay: modified to support generics, with testing
2-3-4 (3 marks)
2-3-4: Insertion
2-3-4: Find
2-3-4: Deletion
2-3-4: modified to support generics, with testing

Bonus: 1 mark
BST traversal that actually shows levels on different levels, and correctly centres

Theory (2 marks each)
Showing how red-black trees are equivalent to 2-3-4 trees (theory question, not programming)
Using a B Tree + Linked List for a filesystem

Programming Part (6 marks)
You are going to test and implement your own AVL, Splay, and 2-3-4 trees (note that AVL is mostly in the lab). Your implementations need to support generics, (using icomparable) so you need to test with sortable objects or simple version of those you make yourself, but I would test these with integers first.

1. AVL Tree.
   Red Black Tree Normally I ask for Red-Black Trees in this assignment, but I don’ think there’s time in summer 2021
2. Splay Tree.
3. A 2-3-4 Tree. (These are also called 2-4 Trees or 2,4 trees)
   It’s up to you to write test cases to show that the trees are working properly for small numbers of inputs (~ 20 elements are fine).
   Key operations:

• Insert
• Traverse (Breadth first + one of the depth first traversals, I suggest in-order). For AVL and Splay these traversals are the same (exactly the same) as the BST ones, since they are both BSTs.
• Find (note that in the splay tree “Find” puts the found node at the root)
• FindAndDelete (this should search for a specific entry, if it exists delete it and then properly fix the tree)

You will likely need to make several methods which make this work (rotations for example), show tests for each of those as well.

BBBBBBONUS!

4. Challenge problem: Make a traversal for the BST variants that prints the trees in something like a natural formatting of how you would write them by hand (with the root in the middle of the tree at the top). Assume the data values are 1 or 2 digit integers. There’s some badly working code to get you started in the AVL lab as a ‘printLevelOrder’ which also uses “printGivenLevel’, but you need to make this work for a tree that could potentially have 32 leaf nodes. This is a variant of a level order traversal. Ideally what your program should do is figure out how wide the tree is at the bottom and set the spacing for that appropriately at the beginning, so the tree doesn’t just start in the middle of the screen, but is left justified with the leftmost element on the left edge of the screen being the leftmost node of the tree. Discuss the run time efficiency of this sort of traversal.

Oh and for more fun – you can widen the window that Visual studio generates by default so you’re not actually stuck to the size it creates things at.

Theory Part (2 marks each)

5. Theory Question (Note: I realise there are answers to this on the web). Show how Red-Black Tree insertions are equivalent to 2-3-4 tree insertions.
6. How would you use a B tree combined with a linked list to make a filesystem? (this is essentially FAT from MS-DOS)

Sample Solution