This articleneeds additional citations forverification. Please helpimprove this article byadding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Self-balancing binary search tree" – news ·newspapers ·books ·scholar ·JSTOR(November 2010) (Learn how and when to remove this message)

Incomputer science, aself-balancing binary search tree (BST) is anynode-basedbinary search tree that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.^[1]These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that theseabstract data structures receive the attribute "self-balancing".

Forheight-balanced binary trees, the height is defined to be logarithmic${\displaystyle O(\log n)}$ in the number${\displaystyle n}$ of items. This is the case for many binary search trees, such asAVL trees andred–black trees.Splay trees andtreaps are self-balancing but not height-balanced, as their height is not guaranteed to be logarithmic in the number of items.

Self-balancing binary search trees provide efficient implementations for mutable orderedlists, and can be used for other abstract data structures such asassociative arrays,priority queues andsets.

Most operations on a binary search tree (BST) take time directly proportional to the height of the tree, so it is desirable to keep the height small. A binary tree with heighth can contain at most2⁰+2¹+···+2^h = 2^h+1−1 nodes. It follows that for any tree withn nodes and heighth:

${\displaystyle n\le 2^{h+1}-1}$

And that implies:

${\displaystyle h\ge \lceil {\log }_2(n+1)-1\rceil \ge \lfloor {\log }_{2}n\rfloor }$.

In other words, the minimum height of a binary tree withn nodes islog₂(n),rounded down; that is,${\displaystyle \lfloor {\log }_{2}n\rfloor }$.^[1]

However, the simplest algorithms for BST item insertion may yield a tree with heightn in rather common situations. For example, when the items are inserted in sortedkey order, the tree degenerates into alinked list withn nodes. The difference in performance between the two situations may be enormous: for example, whenn = 1,000,000, the minimum height is${\displaystyle \lfloor {\log }_2(1,000,000)\rfloor =19}$.

If the data items are known ahead of time, the height can be kept small, in the average sense, by adding values in a random order, resulting in arandom binary search tree. However, there are many situations (such asonline algorithms) where thisrandomization is not viable.

Self-balancing binary trees solve this problem by performing transformations on the tree (such astree rotations) at key insertion times, in order to keep the height proportional tolog₂(n). Although a certainoverhead is involved, it is not bigger than the always necessary lookup cost and may be justified by ensuring fast execution of all operations.

While it is possible to maintain a BST with minimum height with expected${\displaystyle O(\log n)}$ time operations (lookup/insertion/removal), the additional space requirements required to maintain such a structure tend to outweigh the decrease in search time. For comparison, anAVL tree is guaranteed to be within a factor of 1.44 of the optimal height while requiring only two additional bits of storage in a naive implementation.^[1] Therefore, most self-balancing BST algorithms keep the height within a constant factor of this lower bound.

In theasymptotic ("Big-O") sense, a self-balancing BST structure containingn items allows the lookup, insertion, and removal of an item in${\displaystyle O(\log n)}$ worst-case time, andordered enumeration of all items in${\displaystyle O(n)}$ time. For some implementations these are per-operation time bounds, while for others they areamortized bounds over a sequence of operations. These times are asymptotically optimal among all data structures that manipulate the key only through comparisons.

Data structures implementing this type of tree include:

• AA tree
• AVL tree
• Red–black tree
• Scapegoat tree
• Tango tree
• Treap
• Weight-balanced tree

Self-balancing binary search trees can be used in a natural way to construct and maintain ordered lists, such aspriority queues. They can also be used forassociative arrays; key-value pairs are simply inserted with an ordering based on the key alone. In this capacity, self-balancing BSTs havea number of advantages and disadvantages over their main competitor,hash tables. One advantage of self-balancing BSTs is that they allow fast (indeed, asymptotically optimal) enumeration of the itemsin key order, which hash tables do not provide. One disadvantage is that their lookup algorithms get more complicated when there may be multiple items with the same key. Self-balancing BSTs have better worst-case lookup performance than most^[2] hash tables (${\displaystyle O(\log n)}$ compared to${\displaystyle O(n)}$), but have worse average-case performance (${\displaystyle O(\log n)}$ compared to${\displaystyle O(1)}$).

Self-balancing BSTs can be used to implement any algorithm that requires mutable ordered lists, to achieve optimal worst-case asymptotic performance. For example, ifbinary tree sort is implemented with a self-balancing BST, we have a very simple-to-describe yetasymptotically optimal${\displaystyle O(n\log n)}$ sorting algorithm. Similarly, many algorithms incomputational geometry exploit variations on self-balancing BSTs to solve problems such as theline segment intersection problem and thepoint location problem efficiently. (For average-case performance, however, self-balancing BSTs may be less efficient than other solutions. Binary tree sort, in particular, is likely to be slower thanmerge sort,quicksort, orheapsort, because of the tree-balancing overhead as well ascache access patterns.)

Self-balancing BSTs are flexible data structures, in that it's easy to extend them to efficiently record additional information or perform new operations. For example, one can record the number of nodes in each subtree having a certain property, allowing one to count the number of nodes in a certain key range with that property in${\displaystyle O(\log n)}$ time. These extensions can be used, for example, to optimize database queries or other list-processing algorithms.

• Search data structure
• Day–Stout–Warren algorithm
• Fusion tree
• Skip list
• Sorting

• Dictionary of Algorithms and Data Structures: Height-balanced binary search tree
• GNU libavl, a LGPL-licensed library of binary tree implementations in C, with documentation

• Binary trees
• Trees (data structures)

• Articles with short description
• Short description is different from Wikidata
• Articles needing additional references from November 2010
• All articles needing additional references