“(a,b)-tree”的意思、由来-开放百科全书

词条

(a,b)-tree

释义

Definition
Internal node representation
See also
References

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

Definition

Let {{mvar|a}}, {{mvar|b}} be positive integers such that {{math|2 ≤ a ≤ (b+1)/2}}. Then a rooted tree {{mvar|T}} is an (a,b)-tree when:

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

Internal node representation

Every internal node {{mvar|v}} of a (a,b)-tree {{mvar|T}} has the following representation:

Let be the number of child nodes of node {{mvar|v}}.
Let be pointers to child nodes.
Let be an array of keys such that equals the largest key in the subtree pointed to by .

References

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

1 : Search trees

随便看

开放百科全书收录14589846条英语、德语、日语等多语种百科知识，基本涵盖了大多数领域的百科知识，是一部内容自由、开放的电子版国际百科全书。

Definition

Internal node representation

See also

References