Binary Search Trees

External

• https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/juAOg/balanced-search-trees-operations-and-applications
• https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/1FBl2/binary-search-tree-basics-part-i
• https://www.coursera.org/learn/algorithms-graphs-data-structures/lecture/cXMbA/binary-search-tree-basics-part-ii

Internal

• Tree Concepts
• Binary Search

Overview

A binary search tree is a binary tree that has the Binary Search Tree Property. It supports insertion, deletions and searches and can be thought as the dynamic version of a sorted array: any operation exposed by a static sorted array is available, but additionally, we have access to insertion and deletion.

While in general the running time of the insertion, deletion and search operations on a binary search tree is asymptotically bounded by the height of the tree, these operations become efficient when the binary search tree is kept balanced, and thus its height is the minimum possible. Balanced binary search trees are addressed in detail below.

A binary search tree is represented in memory using three pointers: left child, right child and the parent. More details on binary tree representation in memory are available here:

Binary Tree Representation in Memory

For a set of keys, there are many search tree corresponding to those keys

Binary Search Tree Property

The fundamental property of the binary search tree, called the Binary Search Tree Property:

For every single node of a binary search tree, if the node has a key value, then all of the keys stored in the left subtree should be less than the node's key value and all of the keys stored in the right subtree should be bigger than the node's key value. This property holds not only at the root, but in every single node of the three.

The binary search tree property is preserved through rotations.

Note that the Binary Search Tree Property is different from the Heap Property. Search tree are designed so we can search easily through them, unlike heaps that are designed to find the minimum (or maximum) easily.

TODO CLRS Page 286.

Canonical Use

A balanced binary search tree supports efficiently the same operations as a static sorted array, but additionally allows for insertion and deletion. The same operations are exposed by unbalanced binary search trees, but their efficiency degrades in case of degraded binary search tree, so keeping the tree balanced is essential. For more details see Balanced Binary Search Trees below.

Supported Operations

The binary search tree support the following operations:

Operation	Running Time	Notes
INSERT(X)	Θ(tree_height), Θ(log n) for balanced trees	INSERT Implementation
DELETE(X)	Θ(tree_height), Θ(log n) for balanced trees	DELETE Implementation
SEARCH(K)	Θ(tree_height), Θ(log n) for balanced trees	SEARCH Implementation
SELECT(ith order statistics)	Θ(tree_height), Θ(log n) for balanced trees	SELECT Implementation
MINIMUM()	Θ(tree_height), Θ(log n) for balanced trees	MINIMUM Implementation
MAXIMUM()	Θ(tree_height), Θ(log n) for balanced trees	MAXIMUM Implementation
PREDECESSOR(X)	Θ(tree_height), Θ(log n) for balanced trees	PREDECESSOR Implementation
SUCCESSOR(X)	Θ(tree_height), Θ(log n) for balanced trees	SUCCESSOR Implementation
RANK(X)	Θ(tree_height), Θ(log n) for balanced trees	RANK Implementation

SEARCH

The motivation for the search tree property is that searching in a search tree just involves "following your nose", like a binary search in a sorted array.

SEARCH(root, X)

SEARCH(n, X)
  if X == value(n) return n
  if X < value(n) 
    if there is no left child return NULL
    else SEARCH(left_child(n), X)
  if X > value(n) 
    if there is no right child return NULL
    else SEARCH(right_child(n), X)

The running time is Θ(tree_height).

INSERT

One implementation, that does not care about keeping the tree balanced, uses the recursive search procedure described above to keep searching for the key to be inserted until a NULL child pointer is encountered. At that point, the procedure wires a new tree node in that position:

INSERT(root, X)

INSERT(n, X)
  if X <= value(n) 
    if there is no left child wire X as left child
    else INSERT(left_child(n), X)
  if X > value(n) 
    if there is no right child wire X as right child
    else INSERT(right_child(n), X)

The running time is Θ(tree_height).

DELETE

The DELETE(X) function gets as argument the node to delete. The DELETE(K) function gets as argument the key to delete and in this case we need to locate the node X corresponding to the given key K with SEARCH(K). If no such node exists, nothing is deleted.

To continue, we assume the node X exists.

There are three distinct cases that need to be handled:

1. X has no children. This is the easiest case, the node is just simply deleted from the three.

2. X has just one child - a left child or a right child. In this case, splice out the node to delete, which creates a hole in the tree, and then rewire its child into its parent. The unique child assumes the position of the deleted node.

3. X has both the left and right child. Find the predecessor of the node to be deleted using the PREDECESSOR() function. Since X has both left and right subtrees, the predecessor will be the rightmost leaf of its left subtree, as explained in PREDECESSOR Implementation. Then splice out the node to be deleted and wire the predecessor such found in its place. If the predecessor node has a left child, you may need to wire it into its parent.

MINIMUM

Search for -∞: Start with the root and follow the left child until the leftmost leaf. The running time is Θ(tree_height).

MAXIMUM

Search for +∞: Start with the root and follow the right child until the rightmost leaf. The running time is Θ(tree_height).

PREDECESSOR

Computing the predecessor of a node X in a binary search tree involves finding the node whose key is the next smaller element relative to the X's key.

If the argument to the PREDECESSOR() function is the key itself, the implementation first must search the tree and find the corresponding node. If no node is found, the problem has no solution.

To continue, we assume that the node corresponding to the given key K is found in the tree, and it is X. Computing the predecessor of the key K reduces to two cases:

1. The node X has a left subtree. In this case, the predecessor node is the node with the maximum key in the left subtree, which can be compute with MAXIMUM(left_child(X)), and it is the rightmost leaf.

2. The node X has no left subtree. In this case, the predecessor node is found by walking up in the tree until we find an ancestor node with a key smaller than K. It is possible to not find a predecessor, if the node we start with is the minimum in the tree.

SUCCESSOR

TODO

SELECT

To implement SELECT efficiently, we need to augment the binary tree structure by storing extra information about the tree itself in each tree node. In this specific case, we maintain a "size" field (size(X)) which contains the number of tree nodes that exist in subtree rooted at X.

Start at root X with children Y and Z.
Let a = size(Y) # a = 0 if X has no left child
if a = i - 1 return X's key
if a ≥ i recursively compute ith order statistic of the search tree rooted at Y
if a < i - 1 recursively compute (i - a - 1)th order statistic of the search tree rooted at Z

The running time is O(tree_height).

Also see:

Randomized Selection in an Unsorted Array

Balanced vs. Unbalanced Binary Search Trees

A binary search tree can be unbalanced or balanced. For the same set of key, the search tree can vary in height between log n and n, where n is the number of keys. Balanced trees are more useful for search because they yield better running times, so techniques to keep the tree balanced while inserting or deleting nodes have been developed.

Balanced Binary Search Trees

The reason to exist for balanced binary search trees is to expose the same set of operations as a static sorted array, while allowing dynamic insertion and deletions. Some of the operations won't be as fast as in the case of a static sorted array, though. Unlike generic binary search trees, the balanced binary search trees are guaranteed to stay balanced, which means their height is guaranteed to stay logarithmic, which means all of the operations search trees support will also have a running time logarithmic in the number of keys that they're storing. The height of a binary tree can't be better than the logarithm of its number of keys, so the balanced binary trees have the best performance of all binary trees.

If we know apriori the relative frequency of various search terms, a balanced search tree is not optimal relative to the total number of node traversals. Intuitively, higher in the tree we place the most frequently search terms, the fewer overall node traversals we get. Building optimal binary search trees can be approached using dynamic programming algorithms:

Computing Optimal Binary Search Trees with Dynamic Programming

Primitives

Rotation

All balanced binary search trees use this primitive to rebalance themselves.

Search Tree Rotation

Balanced Binary Search Tree Types

Red-Black Trees

Red-Black Trees

AVL Trees

AVL Trees

Splay Trees

Splay Trees

B-Trees

B-trees are k-ary, not binary, but they are search trees and they are balanced.

B and B+ Trees

Comparison between a Balanced Binary Search Tree and a Heap

A heap does not do as much as a balanced binary search tree, but what it does, it does very well. The heap is as dynamic as a search tree, in what insertion and deletion is concerned, it implements insertion and deletion in logarithmic time. It also keeps track of the minimum element (or maximum element, but not both). So if only INSERT(), DELETE() and MINIMUM() (or MAXIMUM()) are needed, a binary search tree is overkill, the heap implements these better, with smallest constant factors both in space and time.

Organizatorium

• https://github.com/jwasham/coding-interview-university#binary-search-trees-bsts