What is the advantage of a binary search tree over an array based structure?

Answer 1

In a binary search tree, insertion, deletion and lookup are O(log n) (i.e. fast) when balanced.
With unsorted arrays, insertion and deletion are O(1) (i.e. very fast) but lookup is O(n) (i.e. slow).
With sorted arrays, insertion and deletion are O(n) (i.e. slow) and lookup is O(log n) (i.e. fast).

Binary search trees are good if you do all three operation (insertion, deletion, lookup) often and have enough data to justify the added burden of more complex structures and algorithms.

Answer 2

A binary tree is a data structure created from nodes that form a tree-like structure with a single root node at the top of the tree. Each node in a binary tree can link with a maximum of 2 child nodes which we conventionally denote left and right. Leaf nodes have no children while parent nodes always have at least one child. The path from the root node to any given node in the tree can be denoted using a unique binary value (hence we call them binary trees), such that a 0 bit means we must traverse left to reach the next node and a 1 bit means we must traverse right. These binary values are known as prefix codes because a child node inherits the full prefix of its parent, appending a 0 or 1 bit depending on whether it is to the left or right of that parent. The root node naturally has no prefix.

Binary trees are fundamental to Huffman encoding/decoding, a prefixing technique that is central to many compression algorithms, whereby symbols that appear most often are allocated shorter prefixes than those that appear less often. Huffman is credited with discovering the algorithm that could reliably produce the most efficient prefix encodings for any given set of data. The resultant binary tree is known as Huffman tree for that reason. His pioneering work in this field is worthy of further study by the reader.

Prefix encoding is just one of many practical applications for binary trees. However, the most common application is the binary search tree (BST). A BST is an ordered binary tree. To understand how it works, imagine we have a sequential data stream of random data. At the start we have no binary tree, so we create a root node and place the first element in that root. We then read the next element and compare with the root. If the new element has a lower value than the root element, we traverse left otherwise we traverse right. If there is no node in that position (which there won't be at this point) we create a new node and place the data in that node. We then repeat the process for each subsequent element, always starting at the root. Each time we arrive at a node, we compare it data to the new element to decide which way we traverse (always traversing left for lower values), creating a new node whenever there is no node in that position. When we've read all the data, we'll have an ordered binary tree (a BST).

Once we have a BST we can search it. We might do this to determine if a particular value exists in the tree. Again, we start at the root and compare values. If the value we seek is there, we are done (the value exists). If the values don't match, we traverse left if the value we seek is less, otherwise we traverse right. We continue in this manner until the value is found or there is no child to traverse to, in which case the value does not exist.

The problem with this is that our construction method was rather naive. There's a high probability that our tree is unbalanced, which simply means the root has more nodes on one side than the other (the same could be true of any parent node in the tree). The ideal is to have a perfectly balanced tree, such that there are the same number of nodes on either side of the root and on either side of every parent (with a maximum difference of just 1 node). To achieve this we use a red/black tree, a special type of binary tree that allows us to "rotate" nodes in order to maintain balance. Node rotations can occur on any parent node, including the root.

A balanced BST can also be implemented using an array. Indeed, this is more efficient as it consumes less memory (we don't need to maintain any links between elements) and traversing elements in an array is generally quicker than traversing a tree because we have constant time random access without the overhead of dereferencing nodes. First we read the data into the array in sequential order, pushing new elements onto the back of the array. Once all the elements are inserted, we sort the array. Sorting an array is (generally) more efficient than maintaining balance in a binary tree.

The middle element of any sorted array (or indeed any sorted sub-array) is the root of a balanced BST. The sub-arrays on either side of the root represent the left and right sub-trees of the root, where the middle elements of those sub-arrays are the children of the root. Thus when seeking a value in any sub-array, we simply compare with the middle element. If the values match, we're done. If there is no match, the comparison will tell us in which sub-array to continue the search, eliminating half the elements each time (just as we would by traversing left or right in a balanced BST). If a sub-array has no elements then the value does not exist.

The following function demonstrates how we can binary search a sorted array.

// return index of v in a[n] (return n if not found)

template<typename T>

size_t find (T a[], size_t n, T v) {

if (n==0) return n; // sanity check!

size_t lo=0, hi=n-1; // lower and upper bounds of sub-array (initially the whole array)

while (lo<=hi) { // while the sub-array has one or more elements...

size_t mid = (hi-lo)/2+lo; // calculate the middle index

if (v==a[mid]) return mid; // value found at a[mid]

// else

if (v<a[mid]) hi = mid-1; else lo = mid+1; // adjust upper or lower bound as appropriate

}

return -1; // v does not exist!

}

The choice between using a red/black tree or an array typically comes down to whether or not the elements are inserted all at once (before we do any searches). If so, use an array. If not, use a red/black tree.