[prev] 35 [next]

Binary Search Trees

Binary search trees have the characteristic properties
  • each node is the root of 0, 1 or 2 subtrees
  • all values in any left subtree are less than root
  • all values in any right subtree are greater than root
  • these properties applies over all nodes in the tree
Operations:
  • insert(Tree,Item) ... add new item to tree via key
  • delete(Tree,Key) ... remove item with specified key from tree
  • search(Tree,Key) ... find item containing key in tree
  • plus, "bookeeping" ... new(), dispose(), show(), empty(), ...