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. 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". 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 AVL trees and red–black trees. 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.
Overview
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 height h can contain at most 20+21+···+2h = 2h+1−1 nodes. It follows that for any tree with n nodes and height h:
n ≤ 2 h + 1 − 1 {\displaystyle n\leq 2^{h+1}-1}
And that implies:
h ≥ ⌈ log 2 ( n + 1 ) − 1 ⌉ ≥ ⌊ log 2 n ⌋ {\displaystyle h\geq \lceil \log _{2}(n+1)-1\rceil \geq \lfloor \log _{2}n\rfloor } . In other words, the minimum height of a binary tree with n nodes is log2(n), rounded down; that is, ⌊ log 2 n ⌋ {\displaystyle \lfloor \log _{2}n\rfloor } . 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. The difference in performance between the two situations may be enormous: for example, when n = 1,000,000, the minimum height is ⌊ log 2 ( 1 , 000 , 000 ) ⌋ = 19 {\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 a random binary search tree. However, there are many situations (such as online algorithms) where this randomization is not viable. Self-balancing binary trees solve this problem by performing transformations on the tree (such as tree rotations) at key insertion times, in order to keep the height proportional to log2(n). 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. While it is possible to maintain a BST with minimum height with expected O ( log n ) {\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, 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. Therefore, most self-balancing BST algorithms keep the height within a constant factor of this lower bound. In the asymptotic ("Big-O") sense, a self-balancing BST structure containing n items allows the lookup, insertion, and removal of an item in O ( log n ) {\displaystyle O(\log n)} worst-case time, and ordered enumeration of all items in O ( n ) {\displaystyle O(n)} time. For some implementations these are per-operation time bounds, while for others they are amortized bounds over a sequence of operations. These times are asymptotically optimal among all data structures that manipulate the key only through comparisons.
Implementations Data structures implementing this type of tree include:
AA tree AVL tree Red–black tree Scapegoat tree Tango tree Treap Weight-balanced tree
… excerpt ends here. Continue reading the full article.
