Section notes for Week 8 (B-tree and skiplist src)

Section Notes for Week 8 (B-tree and skiplist src)

Story thus far

  1. Conversion of Java into C++
  2. C++ I/O
  3. C++ Preprocessor
  4. Pointers, local variables, and the stack
  5. new and delete
  6. Code Review
  7. More Example Code
  8. Reference Variables and Method invocation
  9. Const keyword
  10. Constructors, copy constructors, and destructors
  11. Operator Overloading and the string class
  12. Big 3
  13. Templates and the array class
  14. Discussion of the List ADT
  15. A look at an array list implementation
  16. A look at the Linked List implementation
  17. Brief Discussion of Doubly Linked Lists
  18. Iterators
  19. Function Objects
  20. Generic Programming
  21. Trees
  22. Binary Search Trees
  23. Tree Traversal
  24. Trees with Back Pointers
  25. Exam Review
  26. Motivation
  27. Cases
  28. Rotations
  29. The Big Picture
  30. Iterators in AVL


  1. RedBlack Operations
  2. B-Tree src
  3. RedBlack-Trees
  4. Quick Review

B-Tree src

Ok, we'll start with a quick overview of the headerfile, as per usual.

Some things to notice about the tree itself:

  1. 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 constructor, though.
  2. Elements are keyed on integers always, and the info is stored as an Etype pointer.
  3. No iterators. There is a Print which does a post order traversal of the tree.
  4. The only interesting public operations are Insert and Remove.
  5. 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

  1. The Internal and the Leaf nodes are represented with the same data structure.
    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.
  2. Code! The BTreeNode has a lot of code, unlike it's List, BST and AVL analogs.
    1. The search on the node is done with a linear search, not a binary search.
    2. (Free|Fill)(Subtree|Index)Cell
      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 your own.

    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:

    1. Big 3!
    2. A head and current pointer
    3. A max level, and a size.
    4. SkipListNode
      1. The next pointers are implemented using the array ADT
      2. Just like Jason said, the level of a node is chosen at random
      3. 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.