Don't like this style? Click here to change it! blue.css
Class 21: 234 Trees (a specific B-Tree)
So this is a type of "search tree" that stays very balanced and has some great properties. It's not the most
elegant thing to implement and I hope you find the idea simple enough.
A B-Tree is like a binary search tree which keeps more than 1 key per node. If it keeps many
keys it also keeps a pointer to a child-tree in-between each of its keys. Like this:
Search Task 1: Imagine an algorithm which searches inside of this structure. How
many comparisons do you need before you would find 52.
We classify B-Trees by the minimum and maximum number of children. The one above is a degree 3 B-Tree (max
degree 6). A 2-3-4 tree is
just the B-Tree with minimum degree 2 (max degree 4).
Here are the opening steps of implementing a 2-3-4 Tree:
We have four attributes, a number of keys (which changes over time), an indicator of being a leaf, an array of
at most 3 keys, an array of at most 4 children.
Search Better Task 2: In the code I give here I'm returning a
Node234* which has the key you want. Change the code to return both a Node234* and the index
of the key that was searched for (use -1 for unsuccessful search).
The Big Idea
So the main mechanic of B-Trees is that when you try to insert into a "full" node, the node has to be "split" to
have enough room for all of the keys.
Let's watch: Let's go play with this B-Tree
implementation.
Visual Task 3: Put the visualization to max-degree 4 with preemptive-split.
Insert the letters of the alphabet, in order, until the tree is height 4. What letter pushed it to height 4?
What patterns have you spotted?
OK, so here's a rough sketch of how splitting works:
Half of the children will stay, half will move to a new node, the median key moves up to join its parent, the
new node becomes a child of the parent.
When we are heading down the tree if we see a full node we preemptively split it so that we can rely on always
having room in the parent (less complicated code).
Here is the code:
Understand Task 4: How does insert_not_full work?
Design Task 5: Why is root_insert different than
insert_not_full? Where exactly do non-leaf nodes come from?
Sketch Task 6: Sketch out what the 2-3-4 tree looks like after my insertions.
Big Idea Task 7: Why is this structure always balanced? (That is the number of
nodes from root to leaf is the same for every single leaf.)
Red-Black trees are just the Binary Search Tree version of 2-3-4 trees. We'll talk about them on Tuesday.
Play Tasks
If you would like to work on your projects with your group I'll accept that now. But ideally you will work on
this 2-3-4
tree hand's on task :
Coding Task 8: Implement min() and next() (logical
successor) in our 2-3-4
code.