In
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, a self-balancing binary search tree (BST) is any
node
In general, a node is a localized swelling (a "knot") or a point of intersection (a vertex).
Node may refer to:
In mathematics
*Vertex (graph theory), a vertex in a mathematical graph
*Vertex (geometry), a point where two or more curves, lines, ...
-based
binary search tree
In computer science, a binary search tree (BST), also called an ordered or sorted binary tree, is a rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left subtree and ...
that automatically keeps its height (maximal number of levels below the root) small in the face of arbitrary item insertions and deletions.
Donald Knuth
Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of computer sc ...
. ''The Art of Computer Programming
''The Art of Computer Programming'' (''TAOCP'') is a comprehensive monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. Volumes 1–5 are intended to represent the central core of compu ...
'', Volume 3: ''Sorting and Searching'', Second Edition. Addison-Wesley, 1998. . Section 6.2.3: Balanced Trees, pp.458–481.
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
in the number
of items. This is the case for many binary search trees, such as
AVL tree
In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node d ...
s and
red–black tree
In computer science, a red–black tree is a kind of self-balancing binary search tree. Each node stores an extra bit representing "color" ("red" or "black"), used to ensure that the tree remains balanced during insertions and deletions.
When the ...
s.
Splay trees and
treap
In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys. After any sequence of in ...
s 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
A ''list'' is any set of items in a row. List or lists may also refer to:
People
* List (surname)
Organizations
* List College, an undergraduate division of the Jewish Theological Seminary of America
* SC Germania List, German rugby unio ...
, and can be used for other abstract data structures such as
associative array
In computer science, an associative array, map, symbol table, or dictionary is an abstract data type that stores a collection of (key, value) pairs, such that each possible key appears at most once in the collection. In mathematical terms an as ...
s,
priority queue
In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a ''priority'' associated with it. In a priority queue, an element with high priority is se ...
s and
sets.
Overview
![BinaryTreeRotations](https://upload.wikimedia.org/wikipedia/commons/4/43/BinaryTreeRotations.svg)
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+···+2''h'' = 2''h''+1−1 nodes. It follows that for any tree with ''n'' nodes and height ''h'':
:
And that implies:
:
.
In other words, the minimum height of a binary tree with ''n'' nodes is
rounded down; that is,
.
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
Key or The Key may refer to:
Common meanings
* Key (cryptography), a piece of information that controls the operation of a cryptography algorithm
* Key (lock), device used to control access to places or facilities restricted by a lock
* Key (map ...
order, the tree degenerates into a
linked list
In computer science, a linked list is a linear collection of data elements whose order is not given by their physical placement in memory. Instead, each element points to the next. It is a data structure consisting of a collection of nodes whic ...
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
.
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
In computer science and probability theory, a random binary tree is a binary tree selected at random from some probability distribution on binary trees. Two different distributions are commonly used: binary trees formed by inserting nodes one at ...
. However, there are many situations (such as
online algorithm
In computer science, an online algorithm is one that can process its input piece-by-piece in a serial fashion, i.e., in the order that the input is fed to the algorithm, without having the entire input available from the start.
In contrast, an o ...
s) where this
randomization Randomization is the process of making something random. Randomization is not haphazard; instead, a random process is a sequence of random variables describing a process whose outcomes do not follow a deterministic pattern, but follow an evolution d ...
is not viable.
Self-balancing binary trees solve this problem by performing transformations on the tree (such as
tree rotation
In discrete mathematics, tree rotation is an operation on a binary tree that changes the structure without interfering with the order of the elements. A tree rotation moves one node up in the tree and one node down. It is used to change the shape ...
s) at key insertion times, in order to keep the height proportional to 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
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
In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node d ...
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
In analytic geometry, an asymptote () of a curve is a line such that the distance between the curve and the line approaches zero as one or both of the ''x'' or ''y'' coordinates tends to infinity. In projective geometry and related contexts, ...
("
Big-O") sense, a self-balancing BST structure containing ''n'' items allows the lookup, insertion, and removal of an item in O(log ''n'') worst-case time, and
ordered enumeration of all items in O(''n'') time. For some implementations these are per-operation time bounds, while for others they are
amortized
In computer science, amortized analysis is a method for analyzing a given algorithm's complexity, or how much of a resource, especially time or memory, it takes to execute. The motivation for amortized analysis is that looking at the worst-case r ...
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:
*
2–3 tree
In computer science, a 2–3 tree is a tree data structure, where every node with children (internal node) has either two children (2-node) and one data element or three children (3-nodes) and two data elements. A 2–3 tree is a B-tree of order 3 ...
*
AA tree
An AA tree in computer science is a form of balanced tree used for storing and retrieving ordered data efficiently. AA trees are named after Arne Andersson, the one who theorized them.
AA trees are a variation of the red–black tree, a form of ...
*
AVL tree
In computer science, an AVL tree (named after inventors Adelson-Velsky and Landis) is a self-balancing binary search tree. It was the first such data structure to be invented. In an AVL tree, the heights of the two child subtrees of any node d ...
*
B-tree
In computer science, a B-tree is a self-balancing tree data structure that maintains sorted data and allows searches, sequential access, insertions, and deletions in logarithmic time. The B-tree generalizes the binary search tree, allowing for n ...
*
Red–black tree
In computer science, a red–black tree is a kind of self-balancing binary search tree. Each node stores an extra bit representing "color" ("red" or "black"), used to ensure that the tree remains balanced during insertions and deletions.
When the ...
*
Scapegoat tree
In computer science, a scapegoat tree is a self-balancing binary search tree, invented by Arne Andersson (computer scientist), Arne Andersson in 1989 and again by Igal Galperin and Ronald L. Rivest in 1993. It provides worst-case big O notation ...
*
Splay tree
*
Tango tree
A tango tree is a type of binary search tree proposed by Erik D. Demaine, Dion Harmon, John Iacono, and Mihai Pătrașcu in 2004. It is named after Buenos Aires, of which the tango is emblematic.
It is an online binary search tree that achieves ...
*
Treap
In computer science, the treap and the randomized binary search tree are two closely related forms of binary search tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys. After any sequence of in ...
*
Weight-balanced tree
In computer science, weight-balanced binary trees (WBTs) are a type of self-balancing binary search trees that can be used to implement dynamic sets, dictionaries (maps) and sequences. These trees were introduced by Nievergelt and Reingold in the ...
Applications
Self-balancing binary search trees can be used in a natural way to construct and maintain ordered lists, such as
priority queue
In computer science, a priority queue is an abstract data-type similar to a regular queue or stack data structure in which each element additionally has a ''priority'' associated with it. In a priority queue, an element with high priority is se ...
s. They can also be used for
associative array
In computer science, an associative array, map, symbol table, or dictionary is an abstract data type that stores a collection of (key, value) pairs, such that each possible key appears at most once in the collection. In mathematical terms an as ...
s; 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 table
In computing, a hash table, also known as hash map, is a data structure that implements an associative array or dictionary. It is an abstract data type that maps keys to values. A hash table uses a hash function to compute an ''index'', als ...
s. 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 hash tables (O(log n) compared to O(n)), but have worse average-case performance (O(log n) compared to O(1)).
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
A tree sort is a sort algorithm that builds a binary search tree from the elements to be sorted, and then traverses the tree ( in-order) so that the elements come out in sorted order. Its typical use is sorting elements online: after each insert ...
is implemented with a self-balancing BST, we have a very simple-to-describe yet
asymptotically optimal
In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm. It is a term commonly en ...
O(''n'' log ''n'') sorting algorithm. Similarly, many algorithms in
computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems ar ...
exploit variations on self-balancing BSTs to solve problems such as the
line segment intersection
In geometry, an intersection is a point, line, or curve common to two or more objects (such as lines, curves, planes, and surfaces). The simplest case in Euclidean geometry is the line–line intersection between two distinct lines, which either ...
problem and the
point location
The point location problem is a fundamental topic of computational geometry. It finds applications in areas that deal with processing geometrical data: computer graphics, geographic information systems (GIS), motion planning, and computer aided ...
problem efficiently. (For average-case performance, however, self-balancing BSTs may be less efficient than other solutions. Binary tree sort, in particular, is likely to be slower than
merge sort
In computer science, merge sort (also commonly spelled as mergesort) is an efficient, general-purpose, and comparison-based sorting algorithm. Most implementations produce a stable sort, which means that the order of equal elements is the same i ...
,
quicksort
Quicksort is an efficient, general-purpose sorting algorithm. Quicksort was developed by British computer scientist Tony Hoare in 1959 and published in 1961, it is still a commonly used algorithm for sorting. Overall, it is slightly faster than ...
, or
heapsort
In computer science, heapsort is a comparison-based sorting algorithm. Heapsort can be thought of as an improved selection sort: like selection sort, heapsort divides its input into a sorted and an unsorted region, and it iteratively shrinks the ...
, because of the tree-balancing overhead as well as
cache
Cache, caching, or caché may refer to:
Places United States
* Cache, Idaho, an unincorporated community
* Cache, Illinois, an unincorporated community
* Cache, Oklahoma, a city in Comanche County
* Cache, Utah, Cache County, Utah
* Cache Count ...
access patterns.)
Self-balancing BSTs are flexible data structures, 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, allowing 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
*
Search data structure In computer science, a search data structure is any data structure that allows the efficient retrieval of specific items from a set of items, such as a specific record from a database.
The simplest, most general, and least efficient search struc ...
*
Day–Stout–Warren algorithm
The Day–Stout–Warren (DSW) algorithm is a method for efficiently balancing binary search trees that is, decreasing their height to O(log ''n'') nodes, where ''n'' is the total number of nodes. Unlike a self-balancing binary search tree, it doe ...
*
Fusion tree
In computer science, a fusion tree is a type of tree data structure that implements an associative array on -bit integers on a finite universe, where each of the input integer has size less than 2w and is non-negative. When operating on a collecti ...
*
Skip list
In computer science, a skip list (or skiplist) is a probabilistic data structure that allows \mathcal(\log n) average complexity for search as well as \mathcal(\log n) average complexity for insertion within an ordered sequence of n elements. ...
*
Sorting
Sorting refers to ordering data in an increasing or decreasing manner according to some linear relationship among the data items.
# ordering: arranging items in a sequence ordered by some criterion;
# categorizing: grouping items with similar pro ...
References
External links
Dictionary of Algorithms and Data Structures: Height-balanced binary search treeGNU libavl a LGPL-licensed library of binary tree implementations in C, with documentation
{{DEFAULTSORT:Self-Balancing Binary Search Tree
Binary trees
Trees (data structures)