Research on the BST Problem

(Binary) trees are widely used to represent large sets of data when you need to find an element by its key. Definition of a Binary Search Tree (Niklaus Wirth): in a search tree, any existing key can be found by always descending left whenever the sought key is smaller than the visited node’s key, and always right whenever it’s larger.

The choice of search direction depends only on the key being searched for and the current node’s key. Searching for an element in a balanced tree with n elements takes average time of log(n), i.e., O(log n). Thanks to the tree structure, a search can be done with just log(n) comparisons.

The height of a Binary Search Tree depends on the order in which keys are inserted. Consider, for instance, what happens when an already-sorted sequence of keys is inserted — a balanced tree could be built from that same sequence, if it were known in advance. Search is efficient when the tree is reasonably balanced, and that’s where the degradation problem comes from: inserting elements with simple insertion, depending on the data distribution, can cause one side of the tree to grow much larger than the other from the root, creating imbalance and making it inefficient to keep the tree balanced under constant insertions and deletions.

With that problem in mind, Soviet researchers Adelson-Velsky and Landis created the AVL tree — a binary tree with balancing rules that, while not always perfectly balanced, keeps insertion, deletion, and balancing operations reasonably fast.

Research done for the Data Structures II course.