Self-balancing binary search tree

A balanced tree ( in English often self -balancing tree ) is a special case of computer science data structure tree. Maximum amount of guarantees, where the number of elements in the tree indicates, is a constant independent of Some authors also expect data structures to contain the provision that the average height or path length remains logarithmic for each tree.

Problem: degeneration

One important use of trees in computer science is the search tree as. The duration of the most important operations in a search tree ( search, insert, or delete a value ) in the worst case depends linearly on the height of the tree from ( the operations have a complexity of, height of the tree ).

Each k- ary tree with nodes has a height of; and on average still for a certain constant. So also the operations on a tree, at least the complexity.

Adds one but, for example, a search tree a large amount of an already sorted data, this grows unevenly and in extreme cases has a height of with the undesirable consequence that each subsequent insert, search and delete operation complexity is.

See also: O notation, complexity, expected value

Counter-strategy: keep balance

Balanced trees have been developed to prevent the degeneration and to ensure a height of.

To this end, we followed different concepts. All have in common: They ask specific properties of the tree,

• From which it follows that the height of the tree in any case.
• So it ( makes sense of complexity) are appropriate search, insert, and delete operations that preserve the special characteristics.

This gives such an operation by using the operation of general search trees and checked after each execution at the point of change, the balance, adjusted and if necessary re- balanced. It may happen that this adjustment and repair wave continues up to the root.

Höhenbalance

After the height balanced trees ensures for each node that the height of the left sub-tree and the height of the right subtree differ only by a certain ratio or a certain difference from each other.

When red-black tree each node is assigned a color ( red or black ); the tree is height-balanced with respect to the black node and the optimal amount of red nodes is limited. These trees represent a binary implementation of the 2-3 4- trees, a special variant of B- trees.

In AVL tree for each node: the height of its left child differs from that of its right child by more than ± 1 from.

Balance the number of nodes

Be a binary tree with left subtree and right subtree. Then say

The root of balance. Here means the number of the ( external ) of sheets.

A binary tree of bounded balance called α if for each subtree of:

Mehlhorn gathered all binary trees with limited balance α in the set BB ( α ), and proved on p 181: Be and T is a BB ( α ) tree. Then, the search operations (A, T), insertion (a, t ), Clear (A, T) each have the time complexity.

Weight balance

Under the weight of a node is to be understood here to it the probability of the access.

If the tree is static, ie, insert, or delete operations do not matter, then the Bellman algorithm offers that constructs an optimal weighted binary search tree. Its efficiency is also given when the weights are only approximately known. However, a more extreme distribution of access probabilities and the optimal weighted binary search tree is a linear come out ( not logarithmic ) function of the height of the number.

Are insert or Entfernoperationen important, as well as the weights are to be maintained in principle. In the limit, even prospecting, because in the process, at least change the access statistics.

All this and more make the splay trees.