We have defined binary trees in general, and for the next couple of lectures
we are going to look at special kinds of binary trees - binary trees -
that have specific properties that make certain kinds of processing very
The first special kind of binary tree we will look at is Binary Search
Trees. These are binary trees with specific properties that make it
very efficient to search for a value in the tree.
Notes Lecture 10:
B-Trees And HeapsIn this lecture we will look at two kinds of balanced
trees, B-trees and Heaps.
B-trees are extremely widely used in practice for storing large amounts
of data on disk. A B-tree is perfectly height-balanced version of
a data structure called an M-way search tree, so we will begin by discussing
M-way search trees.