Suvarna Garge (Editor)

(a,b) tree

Updated on
Edit
Like
Comment
Share on FacebookTweet on TwitterShare on LinkedInShare on Reddit

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

Contents

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 ≤ a ≤ (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 ≤ a ≤ (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 ρ v be the number of child nodes of node v.
  • Let S v [ 1 … ρ v ] be pointers to child nodes.
  • Let H v [ 1 … ρ 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

    (a,b)-tree Wikipedia
    (Text) CC BY-SA