Self-balancing binary search tree

An example of an unbalanced tree; following the path from the root to a node takes an average of 3.27 node accesses The same tree after being height-balanced; the average path effort decreased to 3.00 node accesses

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

Tree rotations are very common internal operations on self-balancing binary trees to keep perfect or near-to-perfect balance.

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 2+2+···+2 = 2−1 nodes. It follows that for any tree with n nodes and height h:

log2(n), rounded down; that is, 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(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

edit

Data structures implementing this type of tree include:

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

Applications

edit

Self-balancing binary search trees can be used in a natural way to construct and maintain ordered lists, such as priority queues. 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. 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 hash tables (O(log⁡n) compared to O(log⁡n) time. These extensions can be used, for example, to optimize database queries or other list-processing algorithms.

See also

edit

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

References

edit

---

View original on Wikipedia | Back | FazBrowse Home