Ok, we'll start with a quick overview of the headerfile, as per usual.
Some things to notice about the tree itself:
- The B in the B-Tree is actually a template parameter. This is kind of
neat. It probably could have just as easily been a parameter on the
- Elements are keyed on integers always, and the info is stored as an
- No iterators. There is a Print which does a post order traversal of the
- The only interesting public operations are Insert and Remove.
- What's missing?
But before we delve into the Btree src itself, we should familiarize
ourselves with the internals of the BTreeNode.
Some things to notice about the node
- The Internal and the Leaf nodes are represented with the same data
The isLeaf flag is used to differentiate between the two, and the unused
pointers will be NULL. An alternate implementation would be to use
inheritance, and derive a leaf or a node from a base class.
- Code! The BTreeNode has a lot of code, unlike it's List, BST and AVL
- The search on the node is done with a linear search, not a binary
The naming of these four are somewhat confusing. The Free's create an
extra index in the appropriate array, so that we may insert a new node into
the tree, where as the Fill's delete an index hole ("fill it in") after we
remove a node. Somewhat backwards.
So from here, the code is going to run very similar to what I described
last week. We just have to not be afraid of all the array manipulation.
Tracing through insert.
Consider tracing through remove? Not so important. You can look at it on
Skip list src
Quick review of what a skiplist is on the board.
Again, lets start by having a look at the include file.
Things to notice:
- Big 3!
- A head and current pointer
- A max level, and a size.
- The next pointers are implemented using the array ADT
- Just like Jason said, the level of a node is chosen at random
- Specified - used in copy constructor.
Trace through find using Fig 6.2b in green book.
Possibly insert? Not so important. You can look at it on your own.