Self-balancing binary search tree
|
|
In computing, a self-balancing binary search tree or height-balanced binary search tree is a binary search tree that attempts to keep its height, or the number of levels of nodes beneath the root, as small as possible at all times, automatically. This is important, because most operations on a binary search tree take time directly proportional to the tree's height. They are one of the most efficient ways of implementing associative arrays, sets, and other data structures.
Ordinary binary search trees have the primary disadvantage that they can attain very large heights in rather ordinary situations, such as when the keys are inserted in order. The result is a data structure similar to a linked list, making all operations on the tree expensive. Self-balancing binary trees solve this problem by performing transformations on the tree, such as tree rotations, at key times, in order to reduce the height. Although a certain overhead is involved, it is typically spread across many operations.
Times for various operations in terms of number of nodes in the tree n:
| Operation | Big-O time |
| Lookup | O(log n) |
| Insertion | O(log n) |
| Removal | O(log n) |
| In-order iteration | O(n) |
For some implementations these times are worst-case, while for others they are amortized.
| Contents |
Implementations
Popular data structures implementing this type of tree include:
Applications
Self-balancing binary search trees can be used in a natural way to construct associative arrays; key-value pairs are simply inserted with an ordering based on the key alone. Lookup is somewhat complicated in the case where the same key can be used multiple times. In this capacity, self-balancing BSTs have a number of advantages and disadvantages over their main competitor, hash tables.
Many algorithms can exploit self-balancing BSTs to achieve good worst-case bounds with very little effort. For example, if binary tree sort is done with a BST, we have a very simple-to-describe yet asymptotically optimal O(n log n) sorting algorithm (although such an algorithm has practical disadvantages due to bad cache behavior). Similarly, many algorithms in computational geometry exploit variations on self-balancing BSTs to solve problems such as the line intersection problem and the point location problem efficiently.
Self-balancing BSTs are a flexible data structure, 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, allow one to count the number of nodes in a certain key range with that property in O(log n) time. These extensions can be used, for example, to optimize database queries or other list-processing algorithms.
See also
External links
- Dictionary of Algorithms and Data Structures: Height-balanced binary search tree (http://www.nist.gov/dads/HTML/heightBalancedTree.html)es:Árbol de búsqueda binario auto-balanceable