R-Dense tree

Материал из WEGA
Перейти к навигации Перейти к поиску

[math]\displaystyle{ r }[/math]-Dense tree --- [math]\displaystyle{ r }[/math]-плотное дерево.

An [math]\displaystyle{ m }[/math]-ary tree [math]\displaystyle{ T }[/math] is said to be [math]\displaystyle{ r }[/math]-dense tree, where [math]\displaystyle{ r }[/math] is a natural number with [math]\displaystyle{ 1 \leq r \leq m-1 }[/math], iff the following properties hold:

(1) the root of [math]\displaystyle{ T }[/math] is at least binary,

(2) each unsaturated (the number of sons is less than [math]\displaystyle{ m }[/math]) node different from the root has either only saturated brothers and at least one such brother or at least [math]\displaystyle{ r }[/math] saturated brothers,

(3) all leaves have the same depth.

A class of [math]\displaystyle{ m }[/math]-ary trees is called dense if it is a class of [math]\displaystyle{ r }[/math]-dense [math]\displaystyle{ m }[/math]-ary trees for some [math]\displaystyle{ r }[/math]. In particular, we speak of weakly dense [math]\displaystyle{ m }[/math]-ary trees and strongly dense [math]\displaystyle{ m }[/math]-ary trees, respectively, if we have in mind the classes of [math]\displaystyle{ r }[/math]-dense and [math]\displaystyle{ (m-1) }[/math]-dense [math]\displaystyle{ m }[/math]-ary trees, respectively.

Observe that there is only one class of dense binary trees. This class coincides with the class of brother trees.