BT

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? Binary search in O(logn) time. (We use binary search) Select element given ith order statistic in O(1) Computing min/max of array - O(1) Predecessor/Successor - O(1), just find that element and return one before/after it Rank - how many keys stored are less than or equal to the key - O(logn) Output in sorted order - O(n) Simply using a sorted array would be unacceptable for insertion/deletion because it could use O(n) time. [Read More]