In computer science

Computer science

Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...

, an (a,b) tree is a specific kind of search tree

Tree traversal

In computer science, tree-traversal refers to the process of visiting each node in a tree data structure, exactly once, in a systematic way. Such traversals are classified by the order in which the nodes are visited...

.

An (a,b) tree has all of its leaves at the same depth, and all internal nodes

Node (computer science)

A node is a record consisting of one or more fields that are links to other nodes, and a data field. The link and data fields are often implemented by pointers or references although it is also quite common for the data to be embedded directly in the node. Nodes are used to build linked, often...

 have between and children, where and are integers such that . The root may have as few as zero children.

Definition

Let such that . Then a tree T is an (a,b) tree when:

• Every inner node except the root has at least and maximally child nodes.
• Root has maximally child nodes.
• All paths from the root to the leaves are of the same length.

Inner node representation

Every inner node has the following representation:

• Let be the number of child nodes of node 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 .