By the end of this module, you should be able to:

  • list some fundamental operations supported by an ordered collection type

  • describe how to do these fundamental operations on a binary search tree

  • define "balance" in a tree and explain why it is important its performance as an ordered collection

  • explain how to efficiently maintain the height and/or size of each subtree in a tree under dynamic insertion and deletion