Self-balancing binary search tree

In <a href="/facts/Computer_science/lN3pEyPz">computer science</a>, a self-balancing binary search tree (BST) is any <a href="/facts/Node_(computer_science)/eYlvVE0z">node</a>-based <a href="/facts/Binary_search_tree/gWubNt7b">binary search tree</a> that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.
These operations when designed for a self-balancing binary search tree, contain precautionary measures against boundlessly increasing tree height, so that these <a href="/facts/Abstract_data_type/BaVGSHNP">abstract data structures</a> receive the attribute "self-balancing".
For height-balanced binary trees, the height is defined to be logarithmic 
 
 
 
 O
 (
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(\log n)}
 
 in the number 
 
 
 
 n
 
 
 {\displaystyle n}
 
 of items. This is the case for many binary search trees, such as <a href="/facts/AVL_tree/DfexIbS6">AVL trees</a> and <a href="/facts/Red%E2%80%93black_tree/ckgWTV7G">red–black trees</a>. <a href="/facts/Splay_tree/DHKCdoST">Splay trees</a> and <a href="/facts/Treap/sNDcxCpE">treaps</a> 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 <a href="/facts/List_(computing)/9tzhAH6M">lists</a>, and can be used for other abstract data structures such as <a href="/facts/Associative_array/IFGd2xcP">associative arrays</a>, <a href="/facts/Priority_queue/1uXVo4Uf">priority queues</a> and <a href="/facts/Set_(abstract_data_type)/ovoXUmF9">sets</a>.

Self-balancing binary search tree open-in-new

Self-balancing binary search tree