Binary search tree (BST)

Key-value pair abstraction - Map/Dictionary

• key -> value
• insert
• search/get
• delete

Binary search tree (BST)

• Each node has a key
• For every key:
  • Larger than all keys in its left subtree
  • Smaller than all keys in its right subtree

So with BST the drawback includes:

• No good guarantee that if insertion has order, the tree will be imbalanced. (The red black tree can help)
• when deleting: the order of growth of the expected height of a binary search tree with n keys after a long intermixed sequence of random insertions and random Hibbard deletions is: sqrt(N). This currently is not optimized to log N and it is an open question.

Notes on delete