Balanced Search tree

Definition
A balanced search tree is a tree which can provide operations like insert, delete and search in O(lg n) where n is the height of tree and lg n is height.

Motivation behind Balanced Search tree
Properties of sorted array
 Consider the sorted array. If we have a sorted array, what kinds of operations can we perform on it?

1. Binary search in O(logn) time. (We use binary search)
2. Select element given ith order statistic in O(1)
3. Computing min/max of array - O(1)
4. Predecessor/Successor - O(1), just find that element and return one before/after it
5. Rank - how many keys stored are less than or equal to the key - O(logn)
6. Output in sorted order - O(n)

Simply using a sorted array would be unacceptable for insertion/deletion because it could use O(n) time.  So it is good for static data, but for dynamic data where we have to change the data structure again again, balanced search tree comes in picture. 

Properties of Balanced Search Tree

 We can think about a balanced binary search tree as a dynamic sorted array. A BST is like a sorted array, but with logarithmic insertion and deletion. Now, the operations:

1. Binary search - O(log n)
2. Select - O(log n)
3. Min/max - O(log n)
4. Pred/succ - O(log n)
5. Rank - O(log n)
6. Output in sorted order - O(n)
7. Insert/Deletion - O(log n)

Choice of Data Structure
If you only need min/max, you should use a heap instead. If you only need fast insertion and lookup, use a hash table instead which gives result in O(k) time, where k is constant. So, choosing the data structure depends on the need.

We have already seen BST, but it doesn't guarantee such operations, because it is not balanced.

Example of Balanced Trees
Some balanced trees are :
Binary Search tree

• AVL tree - found in 1962.
• Red Black tree - found in 1970's
• Splay trees -  Unlike AVL and RBT they don't just change when we insert or delete, but also change when we lookups well.

Non binary tree

• 2-3 tree
• 2-3-4 tree
• B-Tree, B+ trees -  Used for implementing databases. Here given a node, we don't have just one key, but many key, from there you can move to various branches. The motivation in database context, of shifting from binary paradigm is to match with the memory hierarchy, which is also very important.
• skiplist

Other
treaps - 1996