HOME

TheInfoList



OR:

In
computer science Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied science, ...
, 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 tree, rooted binary tree data structure with the key of each internal node being greater than all the keys in the respective node's left ...
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 and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of comp ...
. '' The Art of Computer Programming'', 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 O(\log n) in the number 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 array In computer science, an associative array, key-value store, 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 math ...
s,
priority queue In computer science, a priority queue is an abstract data type similar to a regular queue (abstract data type), queue or stack (abstract data type), stack abstract data type. In a priority queue, each element has an associated ''priority'', which ...
s 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+···+2''h'' = 2''h''+1−1 nodes. It follows that for any tree with ''n'' nodes and height ''h'': :n\le 2^-1 And that implies: :h\ge\lceil\log_2(n+1)-1\rceil\ge \lfloor\log_2 n\rfloor. In other words, the minimum height of a binary tree with ''n'' nodes is rounded down; that is, \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 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 whi ...
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 \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 Randomization is a statistical process in which a random mechanism is employed to select a sample from a population or assign subjects to different groups.Oxford English Dictionary "randomization" The process is crucial in ensuring the random alloc ...
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 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) 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 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 Limit of a function#Limits at infinity, tends to infinity. In pro ...
(" 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 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


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 (abstract data type), queue or stack (abstract data type), stack abstract data type. In a priority queue, each element has an associated ''priority'', which ...
s. They can also be used for
associative array In computer science, an associative array, key-value store, 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 math ...
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 computer science, a hash table is a data structure that implements an associative array, also called a dictionary or simply map; an associative array is an abstract data type that maps Unique key, keys to Value (computer science), values. ...
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 most Cuckoo hashing provides worst-case lookup performance of O(1). 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 is implemented with a self-balancing BST, we have a very simple-to-describe yet asymptotically optimal O(n \log n) sorting algorithm. Similarly, many algorithms in computational geometry exploit variations on self-balancing BSTs to solve problems such as the line segment intersection problem and the point location 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 and as ) is an efficient, general-purpose, and comparison sort, comparison-based sorting algorithm. Most implementations of merge sort are Sorting algorithm#Stability, stable, wh ...
,
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, because of the tree-balancing overhead as well as cache 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 *
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 Big-O notation, O(log ''n'') nodes, where ''n'' is the total number of nodes. Unlike a self-balancing binary sear ...
* Fusion tree * Skip list *
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 p ...


References


External links


Dictionary of Algorithms and Data Structures: Height-balanced binary search tree

GNU libavl
a LGPL-licensed library of binary tree implementations in C, with documentation {{DEFAULTSORT:Self-Balancing Binary Search Tree Binary trees Trees (data structures)