Self-balancing binary search tree

Self-balancing binary search tree

In computer science, 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. It is one of the most efficient ways of implementing ordered lists and can be used for other data structures such as associative arrays and sets.

Overview

Most operations on a binary search tree take time directly proportional to the tree's height, so it is desirable to keep the height small. 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. If we know all the data ahead of time, we can keep the height small on average by adding values in a random order, but we don't always have this luxury, particularly in online algorithms.

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 justified in the long run by drastically decreasing the time of later operations.

The height must always be at least the ceiling of "log2 n", since there are at most 2"k" nodes on the "k"th level; a "complete" or "full" binary tree has exactly this many levels. Balanced BSTs are not always so precisely balanced, since it can be expensive to keep a tree at minimum height at all times; instead, most algorithms keep the height within a constant factor of this lower bound.

Times for various operations in terms of number of nodes in the tree "n":For some implementations these times are worst-case, while for others they are amortized.

Implementations

Popular data structures implementing this type of tree include:

* AA tree
* AVL tree
* red-black tree
* splay tree
* scapegoat tree

Applications

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. Lookup is somewhat complicated in the case where the same key can be used multiple times.

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 segment 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, 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

* B-tree
* DSW algorithm
* Fusion tree
* Red-black tree
* Skip list
* Treap
* Sorting

External links

* [http://www.nist.gov/dads/HTML/heightBalancedTree.html Dictionary of Algorithms and Data Structures: Height-balanced binary search tree]

References

* Donald Knuth. "The Art of Computer Programming", Volume 3: "Sorting and Searching", Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. Section 6.2.3: Balanced Trees, pp.458–481.


Wikimedia Foundation. 2010.

Игры ⚽ Нужно решить контрольную?

Look at other dictionaries:

  • Binary search tree — In computer science, a binary search tree (BST) is a binary tree data structurewhich has the following properties: *each node (item in the tree) has a value; *a total order (linear order) is defined on these values; *the left subtree of a node… …   Wikipedia

  • Binary search algorithm — for performing binary searches on Java arrays and Lists, respectively. They must be arrays of primitives, or the arrays or Lists must be of a type that implements the Comparable interface, or you must specify a custom Comparator object. Microsoft …   Wikipedia

  • Binary tree — Not to be confused with B tree. A simple binary tree of size 9 and height 3, with a root node whose value is 2. The above tree is unbalanced and not sorted. In computer science, a binary tree is a tree data structure in which each node has at… …   Wikipedia

  • Search algorithm — In computer science, a search algorithm, broadly speaking, is an algorithm that takes a problem as input and returns a solution to the problem, usually after evaluating a number of possible solutions. Most of the algorithms studied by computer… …   Wikipedia

  • 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… …   Wikipedia

  • Tree (data structure) — A simple unordered tree; in this diagram, the node labeled 7 has two children, labeled 2 and 6, and one parent, labeled 2. The root node, at the top, has no parent. In computer science, a tree is a widely used data structure that emulates a… …   Wikipedia

  • Splay tree — A splay tree is a self balancing binary search tree with the additional property that recently accessed elements are quick to access again. It performs basic operations such as insertion, look up and removal in O(log(n)) amortized time. For many… …   Wikipedia

  • Scapegoat tree — In computer science, a scapegoat tree is a self balancing binary search tree, invented by Igal Galperin and Ronald L. Rivest. It provides worst case O(log n ) lookup time, and O(log n ) amortized insertion and deletion time.Unlike other self… …   Wikipedia

  • Dancing tree — For the film Dancing tree, see Dancing tree (film) In computer science, a dancing tree is a tree data structure, which is similar to B+ tree. Invented by Hans Reiser, for use by the Reiser4 file system. As opposed to self balancing binary search… …   Wikipedia

  • AVL tree — In computer science, an AVL tree is a self balancing binary search tree, and it is the first such data structure to be invented. [Robert Sedgewick, Algorithms , Addison Wesley, 1983, ISBN 0 201 06672 6, page 199, chapter 15: Balanced Trees.] In… …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”