Lecture 30.
Multi-way search trees lead to efficient
data structures for two separate reasons. The so called m-way search tree with
small m makes compares favourably with a binary search tree in terms of worst
case asymptotic performance. With large m an m-way search tree is useful for
searching large collections of data that are stored on slow secondary memory.
I gave a general introduction
on multi-way search trees, and then went on to the so called B-tree, and in
particular a 2-4 tree. I illustrated through an example how inserts work on a
2-4 tree. I will continue this example on Monday.
Posted: Fri - March 23, 2007 at 03:51 PM