Multiway tree

Multiway tree --- многоходовое дерево.

A multiway tree of order [math]\displaystyle{ m }[/math] [math]\displaystyle{ (m \geq 2) }[/math] is a tree such that the properties P1, P2, P3 and P4 hold.

(P1) Every node, if it is not a leaf, has at most [math]\displaystyle{ m }[/math] sons.

(P2) Every node contains at most [math]\displaystyle{ m-1 }[/math] keys.

Let the generic node contain [math]\displaystyle{ j }[/math] keys, [math]\displaystyle{ 1 \leq j \leq m-1 }[/math]. The structure of such a node will be represented as:

[math]\displaystyle{ [p_{1}(k_{1},\alpha_{1}), p_{2}(k_{2},\alpha_{2}), \ldots, (k_{j},\alpha_{j})p_{j+1}) }[/math]

where [math]\displaystyle{ p_{i} }[/math] is the [math]\displaystyle{ i }[/math]-th pointer and the pair [math]\displaystyle{ (k_{i},\alpha_{i}) }[/math] is the [math]\displaystyle{ i }[/math]-th key [math]\displaystyle{ (k_{i}) }[/math] with associated information [math]\displaystyle{ (\alpha_{i}) }[/math]. The following properties hold for every node of a multiway tree:

(P3) [math]\displaystyle{ k_{1} \lt k_{2} \lt \ldots \lt k_{j} }[/math].

(P4) For each [math]\displaystyle{ p_{i} \neq \ 0 }[/math], letting [math]\displaystyle{ P(p_{i}) }[/math] be the node pointed to [math]\displaystyle{ p_{i} }[/math], and [math]\displaystyle{ K(p_{i}) }[/math] be the set of keys contained in the subtree of which [math]\displaystyle{ P(p_{i}) }[/math] is a root, we have:

(a) [math]\displaystyle{ \forall y \in K(p_{i}) \Rightarrow y \lt k_{i} }[/math],

(b) [math]\displaystyle{ \forall y \in K(p_{i}) \Rightarrow k_{i-1} \lt y \lt k_{i}, \; 2 \leq i \leq j }[/math],

(c) [math]\displaystyle{ \forall y \in K(p_{j+1}) \Rightarrow y \gt k_{i} }[/math].