Английская Википедия:(a,b)-tree

Содержание

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

Текст

In computer science, an (a,b) tree is a kind of balanced search tree.

An (a,b)-tree has all of its leaves at the same depth, and all internal nodes except for the root have between Шаблон:Mvar and Шаблон:Mvar children, where Шаблон:Mvar and Шаблон:Mvar are integers such that Шаблон:Math. The root has, if it is not a leaf, between 2 and Шаблон:Mvar children.

Definition

Let Шаблон:Mvar, Шаблон:Mvar be positive integers such that Шаблон:Math. Then a rooted tree Шаблон:Mvar is an (a,b)-tree when:

• Every inner node except the root has at least Шаблон:Mvar and at most Шаблон:Mvar children.
• The root has at most Шаблон:Mvar children.
• All paths from the root to the leaves are of the same length.

Internal node representation

Every internal node Шаблон:Mvar of a (a,b)-tree Шаблон:Mvar has the following representation:

• Let <math>\rho_v</math> be the number of child nodes of node Шаблон:Mvar.
• Let <math>S_v[1 \dots \rho_v]</math> be pointers to child nodes.
• Let <math>H_v[1 \dots \rho_v - 1]</math> be an array of keys such that <math>H_v[i]</math> equals the largest key in the subtree pointed to by <math>S_v[i]</math>.

See also

• B-tree
• 2–3 tree
• 2–3–4 tree

References

• Шаблон:DADS

Шаблон:Datastructure-stub