(a, b)-Baum

2009-02-22T19:42:33Z

Cacadril: Increased language precision. Correct factual error, a tree can be empty in which case the root has no children.

In [[computer science]], an '''(a,b) tree''' is a specific kind of [[Tree traversal|search tree]].

An (a,b) tree has all of its [[leaf node|leaves]] at the same depth, and all internal [[Node (computer science)|nodes]] have between <math>a</math> and <math>b</math> [[Child node|children]], where <math>a</math> and <math>b</math> are integers such that <math>2 \le a \le (b+1)/2</math>. The root may have as few as zero children.

== Definition ==
Let <math>a, b \in N</math> such that <math>a \leq b</math>. Then tree a tree ''T'' is an '''(a,b) tree''' when:
* Every inner node except the root has at least <math>a</math> and maximally <math>b</math> child nodes.
* Root has maximally <math>b</math> child nodes.
* All paths from the root to the leaves are of the same length.

== Inner node representation ==
Every inner node <math>v</math> has the following representation:
* Let <math>\rho_v</math> be the number of child nodes of node v.
* 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]]

==References==
* {{DADS|(a,b)-tree|abtree}}

[[Category:Trees (structure)|A,b tree]]

{{datastructure-stub}}

[[cs:(a,b)-strom]]

Wikipedia - Benutzerbeiträge [de]

(a, b)-Baum