Balanced tree

A balanced tree ( English often self-balancing tree is) in the computer science a special case of the data structure tree , a maximum height of guaranteed, wherein the number of elements in the tree indicates and one of is independent constant. Some authors also include data structures that contain provisions that the mean height or path length of each tree remains logarithmic. ${\ displaystyle c \ cdot \ log (n)}$ ${\ displaystyle n}$ ${\ displaystyle c}$ ${\ displaystyle n}$

Problem: degeneration

An important application of trees in computer science is as a search tree . In the worst case, the runtime of the most important operations in a search tree (searching, inserting or deleting a value) depends linearly on the height of the tree (the operations have a complexity of ; height of the tree). ${\ displaystyle {\ mathcal {O}} (h)}$ ${\ displaystyle h}$

Each k -nary tree with nodes has a height of ; and on average still for some constant . So are the operations on a tree at least of complexity . ${\ displaystyle n}$ ${\ displaystyle h \ geq \ log _ {k} (n + 1)}$ ${\ displaystyle c \ cdot \ log _ {k} \ n}$ ${\ displaystyle c}$ ${\ displaystyle {\ mathcal {O}} (\ log _ {k} n) = {\ mathcal {O}} (\ log n)}$

Example of unbalanced tree

If, for example, a large amount of already sorted data is added to a search tree, it grows unevenly and, in extreme cases, has a height of with the undesirable consequence that each subsequent insert, search and delete operation is also complex . ${\ displaystyle n}$ ${\ displaystyle {\ mathcal {O}} (n)}$

A search tree that has degenerated into a list

The result of this one-sided insertion would be a singly linked list ; the benefits of a tree would be nullified

Counter strategy: keep balance

Balanced trees are designed to prevent degeneration and guarantee a height of . ${\ displaystyle c \ cdot \ log (n)}$

To do this, one pursues different concepts. They all have one thing in common: They demand special properties of the tree,

from which it follows that the height of the tree is in each case . ${\ displaystyle c \ cdot \ log (n)}$
so that there are suitable search, insert and delete operations (sensibly of complexity ) that preserve the special properties. ${\ displaystyle {\ mathcal {O}} (h)}$

Such an operation is obtained by using the operation of the general search trees and after each execution at the point of change, the balance is checked, adjusted and, if necessary, rebalanced. It can happen that this wave of adjustment and repair continues up to the root.

Height balance

Trees balanced according to the height ensure for each node that the height of the left subtree and the height of the right subtree only deviate by a certain ratio or a certain difference.

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

The following applies to every node in the AVL tree : The height of the child on the left deviates from that of the child on the right by a maximum of ± 1.

Nodal balance

Let be a binary tree with a left subtree and a right subtree . Then is called ${\ displaystyle T}$ ${\ displaystyle T_ {l}}$ ${\ displaystyle T_ {r}}$

{\ displaystyle \ rho (T): = {\ tfrac {| T_ {l} |} {| T |}} = 1 - {\ tfrac {| T_ {r} |} {| T |}}}

the root balance of . Here means the number of (external) Leaves of . ${\ displaystyle T}$ ${\ displaystyle | T |}$ ${\ displaystyle T}$

A binary tree is called of bounded balance α if for each subtree of : ${\ displaystyle T '}$ ${\ displaystyle T}$

{\ displaystyle \ alpha \ leq \ rho (T ') \ leq 1- \ alpha}

.

This kind of binary trees were introduced in 1972 by Reingold and Nievergelt. In the English literature they are also called "weight-balanced trees" (WBTs).

Mehlhorn assembles all binary trees with bounded balance α in the set BB (α) and proves on p. 181:
Let and T be a BB (α) -tree. Then the operations search ( a , T ), insert ( a , T ), delete ( a , T ) each have the time complexity . ${\ displaystyle {\ tfrac {1} {4}} <\, \ alpha \, \ leq 1 - {\ tfrac {\ sqrt {2}} {2}}}$ ${\ displaystyle {\ mathcal {\ mathcal {O}}} (\ log | T |)}$

Weight balance

The weight of a node is understood here to mean the probability of access to it.

If the tree is static, i.e. insert or delete operations are irrelevant, then the Bellman algorithm is available , which constructs an optimal weighted binary search tree. Its efficiency is given even if the weights are only roughly known.

However, with an extreme distribution of the access probabilities, even with the optimal weighted binary search tree, a linear (no longer logarithmic) dependence of the height on the number can result.

If inserting or removing operations are important, the weights must also be maintained in principle. In the borderline case even when searching, as this at least changes the access statistics.

Splay trees do this and more .

Individual evidence

^ Nievergelt, J. & Reingold, EM (1972) Binary search trees of bounded balance. In Proceedings of the Fourth Annual Acm Symposium on Theory of Computing. ACM, pp. 137-142.
↑ Y. Hirai, K. Yamamoto: Balancing weight-balanced trees . In: J. Functional Programming . 21, No. 3, 2011, p. 287. doi : 10.1017 / S0956796811000104 .

literature

Kurt Mehlhorn data structures and efficient algorithms Teubner Stuttgart 1988, ISBN 3-519-12255-3 .

[1] Nievergelt, J. & Reingold, EM (1972) Binary search trees of bounded balance. In Proceedings of the Fourth Annual Acm Symposium on Theory of Computing. ACM, pp. 137-142.

[Hirai-2] Y. Hirai, K. Yamamoto: Balancing weight-balanced trees . In: J. Functional Programming . 21, No. 3, 2011, p. 287. doi : 10.1017 / S0956796811000104 .