Don't like this style? Click here to change it! blue.css
It's been a wild ride! I hope that you feel like you've picked up many useful skills. Not just technical skills but professional skills. I hope that you've learned to tolerate ambiguity and discomfort a bit more and that you see failure as a step towards success.
I want to thank each of you for your efforts this semester.
Here was a make-up final I gave once:
"I let you create your own assertions and give some mild guidance in the actual code. You can change anything you want except the Cat struct and theCats array. Your 6 goals are to take in 2500 cats and first convert them into a linked list, then reverse that linked list, then create another array from that linked list, then heapify that array in linear time, then insert those cats into a BST, finally tell me the height of the tree when these exact cats are inserted in that exact order. So it's not like a normal test but more like a really weird little work project."
Fix this mess:
Use your bit tricks to set and fetch single bits of a number:
Use your intuition and experience to adjust to this new data structure:
Take in a BST and do rotations to make the max value the root:
Adjust our Trie to look up contacts by their phone number:
Use the STL to prioritize students by three different traits:
So it's also nice to look at the actual things we've learned together:
These are things that we probably should have learned (so go learn them this summer):
We got a quick preview last time at 2-3-4 trees. These are binary search trees where each node also stores a color. Every Red-Black tree satisfies these properties:
The heights of red-black trees are at most \(2 \log{(n+1)}\) and they are BSTs so we immediately get:
FindMinMaxNextPrevWe just have to worry about RB_insert and RB_delete.
Obligatory color images of red-black trees:
We also saw yesterday that Red Black Trees are really just Binary versions of 2-3-4 trees. Here is the same tree re-visualized as a 2-3-4 tree:
Let's watch: Let's go play with this Red-Black tree implementation.
Bust a tree up in this - Task 1: Last time we inserted into a 2-3-4 tree until it burst. Look for nodes "splitting"… Now let's add the letters of the alphabet until the red-black tree has a "black height" of 4. What letter busted it? (Which letter busted us to black-height 3?) (Also set the width to at least 1200.)
The basic algorithm is to insert the new node like normal, make it RED (because this doesn't increase the black height of the tree… (better to ask forgiveness than beg permission)) then try to fix any problems that made.
The big idea: the freshly painted red node is the one asking to join a 2-3-4 node. Red nodes are never leaf nodes so leaves can only be created by splits. If the red node is accepted straight-up then we're good. Otherwise we have to get that red node into the bigger node somehow.
Black Root Task 2: In my code snippet (not finished) why can we paint the root node black without fear?
The small issues to work out: 1) Doing a full node split. 2) Accepting the pushed up node from a split.
Recall what a "full" 2-3-4 node looks like in a Red-Black tree.
1) OK, so what does a 2-3-4 split do in a red black tree?
That looks like it was just a gentle re-coloring. Cool!
Uncle Task 3: So detecting that a split is needed (in code) require checking the color of your uncle. What does that mean and how do you pull it off?
Case 1 Task 4: When the 4-node is expressed in Red-Black and F2 is a freshly inserted red node how should you twiddle things to keep all of the rules satisfied? (Hint: just use the 2-3-4 analogy.)
2) How about the issue of "accepting" the new pushed up node?
There are three types of "virtual" 2-3-4 nodes that show up in a Red-Black tree, so we get 3 cases of headaches to solve (and their mirror images). This image shows the two degree 3 nodes in both forms. On the left imagine F2 as a freshly colored red node asking for acceptance. On the right imagine F3 as a freshly colored red node asking for acceptance.
Case 2 Task 5: In the left 3-node image, if F2 were asking for permission to join A and B what would the final 2-3-4 node look like? How can you accomplish that with rotations?
Case 3 Task 6: In the right 3-node image, if F3 were asking for permission to join B and A what would the final 2-3-4 node look like? How can you accomplish that with rotations?
OK, that's about it for concepts. The rest is just mirror images of what we've seen so far.
So I want you to build a balanced binary search tree without giving you the actual code. I've given you some starter code but not the AVL and now not the Red Black. But you're also very busy folks. So what I will give you is the pseudo-code for the FixRB method and let you spend the rest of class finishing it off.
