Data Structures: Binary Search Trees

What is a binary search tree?

A binary tree (aka BT) is a Tree implementation where a node can have only max two children. In common practice, they are mostly used as a structural basis (in balanced search form) behind sequential data structures (maps and sets) whose entries need to remain sorted.

A binary search tree (aka BST) is a binary tree that uses a comparator function to have its entries (nodes) self-sorted. The algorithm is: Whatever is smaller than root should be looked after on left child. Whatever is greater than root should be looked after on right child. Do so recursively until a match is found!. Thanks to this algorithm if we populate a binary search tree with random entries we would achieve an acceptable O(log(N)) look-up time. What happens when we populate it with already sorted entries? In this case it keeps up populating right children until we end up with a big ugly Linked List with linear O(N) look-up time.

A balanced binary search tree (aka BBST) solves above problem by having the tree balance itself on entry insertion/deletion, so depth searches (number of recursions until a match is found) are kept to a minimum. The ugly side of balancing is that it's very complicated to design and, regardless of solution chosen, any insertion/deletion requires potentially the whole tree being rebalanced (which is what makes this structure so slow compared to a Hash Table).

What are the operations it implements?

Apart of implementing operations required by Tree abstract data type, binary seach trees are too varied in usage to allow any other shared logic.

What is the solution of choice for balancing?

There are multiple solutions to make binary search tree balance itself automatically. Most powerful are:

The AVL trees are more balanced compared to Red-Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves many frequent insertions and deletions, then Red Black trees should be preferred. And if the insertions and deletions are less frequent and search is a more frequent operation, then AVL tree should be preferred over Red-Black Tree.
Source: GeeksForGeeks

The solution of choice, employed by standard libraries of both Java and C++ and this API, is to use Red Black Tree.


Share