en>Qetuth: more specific stub type

2012-01-01T10:38:56Z

more specific stub type

New page

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]] except for the root 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 has, if it is not a leaf, between 2 and b children.

== Definition ==
Let <math>a, b \in \mathbb{N}</math> such that <math>a \leq b</math>. Then 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]]
*[[2-3 tree]]

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

{{CS-Trees}}

{{DEFAULTSORT:A,b tree}}
[[Category:Trees (data structures)]]

{{datastructure-stub}}

Polynormal subgroup - Revision history

en>Qetuth: more specific stub type