(a,b)-tree

Wikipedia on Answers.com:

(a,b)-tree

Top

Home > Library > Miscellaneous > Wikipedia

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.

Contents

1 Definition
2 Inner node representation
3 See also
4 References

Definition

Let $a, b \in 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 $ρ 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.

v d e Trees in computer science

Binary trees	Binary search tree (BST) · Cartesian tree · Top tree · T-tree

Self-balancing binary search trees	AA tree · AVL 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 tree · Finger tree · Metric tree · Cover tree · BK-tree · Doubly-chained tree · iDistance · Link-cut tree · Fenwick tree

This algorithms or data structures-related article is a stub. You can help Wikipedia by expanding it.

This entry is from Wikipedia, the leading user-contributed encyclopedia. It may not have been reviewed by professional editors (see full disclaimer)

Donate to Wikimedia

(a,b)-tree

Top

Home > Library > History, Politics & Society > FiveMinPersistent

Click to Play

The Connection Between Human Teeth and Trees

Click to Play

Dr. Krause Discovers a Singing Cottonwood Tree

Click to Play

Visit the Strangling Trees of Angkor Wat in Cambodia

Click to Play

How a Tree Planter Became a Willamette Valley Winemaker

View more Science videos

Help us answer these

Who formulated the b-tree and b plus tree?

Difference between b tree and b tree?

What is the advantage of b tree over b tree?

Who formalized b plus tree and b tree?

Post a question - any question - to the WikiAnswers community:

Copyrights:

Cite

Wikipedia on Answers.com This article is licensed under the Creative Commons Attribution/Share-Alike License. It uses material from the Wikipedia article (a,b)-tree. Read