Binary Search TreeEdit

Types

Red-Black Tree

This is a self-balancing binary search tree.

The longest path from the root node to a leaf is no more than twice as long as the shortest path. This makes search a guaranteed O(log n) operation (insertion and deletion are also O(log n)).

AVL Tree

Another example of a self-balancing binary search tree. It offers more rigid guarantees around tree height and therefore faster lookup, at the cost of making insertion and deletion more expensive.