# 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.