Binary Search Trees (BST)

Binary Search Tree is a node based binary tree data structure which has the following properties:

• The left subtree of a node contains only nodes with key's less than the node's key
• The right subtree of a node contains only nodes with keys greater than node's key
• The left and right subtree each must also be a binary search tree
• The tree must not have no duplicate nodes

The above properties provide an ordering among keys such that operations like 

1. Search
2. Min 
3. Max 

can be done fast enough.The tree actions are 

1. Search 
2. Insert 
3. Delete

There are many types of binary trees. Few among them are self balancing trees like 

1. AVL Trees
2. Red Black Trees
3. Splay Trees

All operations take time directly proportional to the height of the tree. Complexity at worst crosses O(h).

Optimal Binary Search Tree

If we do not plan to modify a search tree and if we know how exactly often each item will be accessed.We can construct an optimal binary search tree (with an average cost of looking up an item).

Also refer to Day - Stout - Warren Algorithm or DSW algorithm.