( a , b ) tree

Figure 1: (2, 4) tree

The ( a , b ) -tree is a data structure in computer science and is a special case of a tree, especially an out-tree .

In a -tree, all subtrees have the same depth, and all inner nodes - except for the root - have children between and , where and are natural numbers that must satisfy the property . The root has, if no sheet is between 2 and children. ${\displaystyle (a,b)}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle 2\leq a\leq (b+1)/2}$ ${\displaystyle b}$

The keys and data elements are only stored in the leaves.

definition

Be natural numbers with . Then the out-tree is a -tree if: ${\displaystyle a,b\in \mathbb {N} }$ ${\displaystyle 2\leq a\leq (b+1)/2}$ ${\displaystyle T}$ ${\displaystyle (a,b)}$

• For inner nodes other than the root, the initial degree is . ${\displaystyle a\leq }$ ${\displaystyle \leq b}$
• The root has children at most . ${\displaystyle b}$
• All paths from the root to a leaf have the same depth

Identification of the inner nodes

Each inner node consists of the following identifiers: ${\displaystyle v}$

• Let be the number of children of . ${\displaystyle \rho _{v}}$ ${\displaystyle v}$
• Be the edges to the kids. ${\displaystyle S_{v}[1\dots \rho _{v}]}$
• Let be a sorted list of keys, where is equal to the largest key in the subtree with a root . ${\displaystyle H_{v}[1\dots \rho _{v}-1]}$ ${\displaystyle H_{v}[i]}$ ${\displaystyle S_{v}[i]}$

See also

• B-tree
• Search tree

Web links

• http://tcs.rwth-aachen.de/lehre/DA/SS2011/handout-2011-05-03.pdf
• https://daphne.informatik.uni-freiburg.de/svn-public/AlgoDatSS2015/public/folien/vorlesung-08b.pdf

Individual evidence

1. ^ Paul E. Black: (a, b) -tree. ( Memento of the original from October 13, 2018 in the Internet Archive ) Info: The archive link was automatically inserted and has not yet been checked. Please check the original and archive link according to the instructions and then remove this notice. In: Vreda Pieterse, Paul E. Black (Ed.): Dictionary of Algorithms and Data Structures. October 6, 2004, accessed June 20, 2015.