Self-balancing binary search tree
In computer science, a self-balancing binary search tree (BST) is any node-based binary 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 these abstract data structures receive the attribute "self-balancing".
Splay trees and treaps 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 ordered lists, and can be used for other abstract data structures such as associative arrays, priority queues and sets.
[1] However, the simplest algorithms for BST item insertion may yield a tree with height n in rather common situations.
For example, when the items are inserted in sorted key order, the tree degenerates into a linked list with n nodes.
Although a certain overhead is involved, it is not bigger than the always necessary lookup cost and may be justified by ensuring fast execution of all operations.
For comparison, an AVL 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.
These times are asymptotically optimal among all data structures that manipulate the key only through comparisons.
They can also be used for associative arrays; key-value pairs are simply inserted with an ordering based on the key alone.
In this capacity, self-balancing BSTs have a 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 items in key order, which hash tables do not provide.
Self-balancing BSTs can be used to implement any algorithm that requires mutable ordered lists, to achieve optimal worst-case asymptotic performance.
For example, if binary tree sort is implemented with a self-balancing BST, we have a very simple-to-describe yet asymptotically optimal
Self-balancing BSTs are flexible data structures, in that it's easy to extend them to efficiently record additional information or perform new operations.
