A splay tree is a self-adjusting binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look-up and removal in O(log n) amortized time. For many sequences of operations, splay trees perform better than other search trees, even when the specific pattern of the sequence is unknown.

AVL trees are more rigidly balanced than red-black ones; this leads to slower insertion and removal but faster retrieval. The differences are anyway very small and notable only when using extremely large data structures that may be built once and loaded without reconstruction (e.g. language dictionaries).

Red-black trees offer worst-case guarantees for insertion, deletion, and search time. This feature makes them valuable in time-sensitive applications such as real-time applications; for example, many data structures used in computational geometry can be based on red-black trees (e.g. the Completely Fair Scheduler used in current Linux kernels uses red-black trees).

1. a node is either red or black
2. the root is black
3. all leaves are black
4. both children of every red node are black
5. every simple path from a given node to any of its descendant leaves contains the same number of black nodes

An AVL tree is a binary search tree such that for every internal node v of T, the heights of the children of v can differ by at most 1. The basic operations of an AVL tree involve carrying out the same actions as would be carried out on an unbalanced binary search tree (search, insertion, deletion, traversal, sort), but modifications are preceded or followed by one or more operations called tree rotations, which help to restore the height balance of the subtrees.