(a,b)-tree

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

An (a,b) tree has all of its leaves at the same depth, and all internal nodes have between $a$ and $b$ children, where $a$ and $b$ are integers such that $2 \le a \le (b+1)/2$ . The root may have as few as zero children.

1 Definition
2 Inner node representation
3 See also
4 References

Definition

Let $a, b \in \mathbb{N}$ such that $a \leq b$ . Then a tree T is an (a,b) tree when:

Every inner node except the root has at least $a$ and maximally $b$ child nodes.
Root has maximally $b$ child nodes.
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

Paul E. Black, (a,b)-tree at the NIST Dictionary of Algorithms and Data Structures.

Trees in computer science

Binary trees	Binary search tree (BST) Cartesian tree MVP Tree Top tree T-tree

Self-balancing binary search trees	AA tree AVL tree LLRB tree Red–black tree Scapegoat tree Splay tree Treap

B-trees	B+ tree B-tree B^x-tree UB-tree 2-3 tree 2-3-4 tree (a,b)-tree* Dancing tree Htree

Tries	Suffix tree Radix tree Ternary search tree X-fast trie Y-fast trie

Binary space partitioning (BSP) trees	Quadtree Octree k-d tree Implicit k-d tree VP tree

Non-binary trees	Exponential tree Fusion tree Interval tree PQ tree Range tree SPQR tree Van Emde Boas tree

Spatial data partitioning trees	R-tree R+ tree R* tree X-tree M-tree Segment tree Hilbert R-tree Priority R-tree

Other trees	Heap Hash calendar Hash tree Finger tree Order statistic tree Metric tree Cover tree BK-tree Doubly chained tree iDistance Link-cut tree Fenwick tree Log-structured merge-tree

Contents

Definition

Inner node representation

See also

References