Lecture 12.
Today I finished up the algorithm for
deleting from a binary search tree. Our attention then turned to the
Dictionary
Abstract Data Type (ADT).
The
Dictionary ADT supports instructions
findElement(key, k)
insertElelment(key,
k)
deleteElement(key,k)
An
ordered dictionary is a dictionary that supports the additional operations
inorderPredecessor(key,k)
iorderSuccessor(key,k).
We
discussed the computational complexity of implementing an ordered dictionary
with an ordered array, a linked list both ordered and unordered, as well as a
binary search tree. As a result we needed to look at the height of a binary
tree. We examined the best and worst case heights of a binary tree. We also
discussed, without going into too much detail, the expected height of a binary
tree.
The most efficient (in a
theory) implementation of an ordered dictionary used balanced search trees. Next
week we will study one such balanced search tree, the
AVL
tree.
Posted: Fri - February 2, 2007 at 11:00 AM