[prev] 127 [next]

Application of BSTs: Sets

Trees provide efficient search.

Sets require efficient search

  • to find where to insert/delete
  • to test for set membership
Logical to implement a Set ADT via BSTree

Assuming we have BSTree implementation

  • which precludes duplicate key values
  • which implements insertion, search, deletion
then Set implementation is
  • addToSet(Set,Item) ≡ TreeInsert(Tree,Item)
  • removeFromSet(Set,Item) ≡ TreeDelete(Tree,Item.Key)
  • elementOfSet(Set,Item) ≡ TreeSearch(Tree,Item.Key)