Lecture 14.
Balanced search trees are an amazing
invention. One can perform the
dictionary
operations
INSERT
DELETE
FIND
in logarithmic worst case time,
(i.e. O(log N) when the tree holds N data
items.)
However, understanding
and explaining these structures is highly non-trivial.
Today I resumed with a
presentation of 2-3 trees which in my opinion is the
easiest
balanced tree structure to understand. We then looked at the structure named an
AA-tree in our text after the inventor Arne Andersson. Andersson simply calls
his structure a variant of the BB-tree which gets its name from its inventor
Bayer. (I promise I am not making this up!) In any case the BB-tree and it's
variant the AA-tree are binary tree simulations of 2-3 trees. I drew a picture
of an a 2-3 tree along with the equivalent AA-tree. I then went through a small
example illustrating an insert. The text has examples of insert and delete for
AA-trees as well as some C++
code.
On Monday's update of the
readings I included the section on B-trees as a Read item. You can postpone
reading that section until week 8. Furthermore Red-Black trees are on our
syllabus, so I will promote the Red-Black section from Skip to Read. However,
the one sentence summary of Red-Black
trees,
i.e. Red-Black trees simulate 2-4
trees with a binary search tree, gives you the big picture on the topic.
On Friday I will summarize our
treatment of balanced search trees. I will try and simplify the notion of
rotation with a few illuminating
examples.
Finally I made an
announcement in class regarding the COMPSA Computing Career Workshop. You can
find all the details in the new entry in the Announcements category of this
Blog.
Posted: Wed - February 9, 2005 at 03:11 PM