Data Structures 7/7: Binary Search Trees

Note: Check out the entire supplemental source code for this blog series.

Binary Search Trees

So far, every data structure we’ve looked at has excelled in some aspects and not others. The hash table has Θ(1) searching, but only linear (Θ(n)) minimum and maximum operations. Binary heaps can have Θ(1) minimum or maximum operations, but have linear searching. The binary search tree is the first data structure we’ve seen that has an average case time complexity of Θ(lgn) for all operations we’ve covered (insertion, deletion, search, minimum, and maximum).

Implementation

A binary search tree is a binary tree data structure, meaning each node in the tree has at most two children (a left and a right child). The basic property of a binary search tree is that for each node of the tree, its left child is less than or equal to itself, and its right child is greater than or equal to itself. This structure allows searching (and thus minimum and maximum operations) to be done in Θ(lgn) time on average because you can start at the node, and searh your way down the tree, pruning or ignoring most of it as you go.

Insertion

To insert in a binary tree, start at the root, and travel left or right if the node is less than (left) or greater than (right) the node. If the value is equal, then either left or right can be chosen. Eventually, you will reach the end of the tree, and this is where the node can be inserted.

Deletion

Deletion is a little nuanced, so we won’t cover it in details, but the main idea is to search the tree for the node to delete. When found, splice out that node and rearrange the deleted node’s parent and children in such a way to maintain the structure of the tree.

BinarySearchTree.cs

BinarySearchTreeNode.cs

Pros

• Unlike the previous data structures we’ve covered, binary search trees have an average case runtime of Θ(lgn) for all operations.

Cons

• Unlike linked lists and hash tables, insertion and deletions take Θ(lgn) time on average instead of Θ(1).

• Unlike hash tables, searching takes Θ(lgn) time on average instead of Θ(1).

Use Cases

• Because binary search trees can perform all basic operations in Θ(lgn) time on average, they are well suited for general purpose applications when all operations might be used.

Binary Heaps in C#

• The built-in C# generic implementation of the binary search tree is System.Collections.Generic.SortedDictionary<T>. The implementation is very similar, but with a few more optimizations built in.

Performance