(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 $a$ and $b$ children, where $a$ and $b$ are integers such that $2 \leq a \leq (b +1)/2$ . The root has, if it is not a leaf, between 2 and $b$ children.

Definition

Let $a$ , $b$ be positive integers such that $2 \leq a \leq (b +1)/2$ . Then a rooted tree $T$ is an (a,b)-tree when:

Every inner node except the root has at least $a$ and at most $b$ children.
The root has at most $b$ children.
All paths from the root to the leaves are of the same length.

Inner node representation

Every inner node $v$ has the following representation:

Let $\rho_v$ be the number of child nodes of node v.
Let $S_{v}[1\dots \rho _{v}]$ be pointers to child nodes.
Let $H_{v}[1\dots \rho _{v}-1]$ be an array of keys such that $H_{v}[i]$ equals the largest key in the subtree pointed to by $S_{v}[i]$ .

References

This article incorporates public domain material from the NIST document: Black, Paul E. "(a,b)-tree". Dictionary of Algorithms and Data Structures.

Tree data structures

Search trees (dynamic sets/associative arrays)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (Optimal) Binary search Dancing HTree Interval Order statistic (Left-leaning) Red-black Scapegoat Splay T Treap UB Weight-balanced

Heaps	Binary Binomial Fibonacci Leftist Pairing Skew Van Emde Boas

Tries	Ctrie C-trie (compressed ADT) Hash Radix Suffix Ternary search X-fast Y-fast

Spatial data partitioning trees	Ball BK BSP Cartesian Hilbert R k-d (implicit k-d) M Metric MVP Octree Priority R Quad R R+ R* Segment VP X

Other trees	Cover Exponential Fenwick Finger Fractal tree index Fusion Hash calendar iDistance K-ary Left-child right-sibling Link/cut Log-structured merge Merkle PQ Range SPQR Top

This article is issued from Wikipedia - version of the 4/28/2015. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

(a,b)-tree

Definition

Inner node representation

See also

References