Self-balancing binary search tree

In [computing], a self-balancing binary search tree is a type of binary search tree which attempts to keep its height, or the number of level of nodes beneath the root, as small as possible at all times, automatically. This is important, because most operations on a binary search tree take time proportional to the tree's height, and ordinary binary search trees can attain very large heights in rather ordinary situations, such as when the keys are inserted in order. Keeping the height small is usually accomplished by performing transformations on the tree at key times.

Popular data structures implementing this type of tree include

• red-black trees
• splay trees
• AVL trees

See these pages for more information.

This article is a stub. You can help Wikipedia by fixing it.