A binary Search tree (BST) is a binary tree where each node has a
Comparable key (and an associated value) and satisfies the restriction that the key
in any node is larger than the keys in all nodes in that node's left subtree and smaller
than the keys in all nodes in that node's right subtree. Search.
Search hits in a BST built from N random keys require ~1.39lgN compares on the average
Insertions and search misses in a BST built from N random keys require 1.39lgN compares on the average
However, in a BST, all operations take time proportional to the height of the tree in the worst case.
