Algorithms for generation of rooted tree on the base of total partition procedure.pdf Деревья являются одним из важнейших классов комбинаторных множеств, которыедостаточно хорошо изучены. Однако можно предложить ряд алгоритмов генерацииклассов корневых деревьев, основанных на процедуре полного разбиения. Впервыеподобную процедуру предложил Н. Я. Виленкин как подсчет процессов последовательныхразбиений [1]. Р. Стенли предложил использовать эту процедуру для полногоразбиения конечного множества S , в результате выполнения которой получается некотороекорневое дерево [2]. Основная идея данного доклада заключается в том, что этупроцедуру можно модифицировать, используя вместо конечного множества S натуральноечисло n. Тогда, имея некоторый алгоритм R(n) представления натуральногочисла n в виде суммы, в общем случае, неотрицательных чисел Ai, строится непомеченноеn-узловое корневое дерево. Алгоритм построения дерева следующий.1) Создаем корень дерева r и пару < n, r > заносим в стек.2) Если стек пуст, то завершаем процедуру.3) Вынимаем из стека очередную пару < k,z >. Если k = 1, то данный узелстановится листом, и переходим на шаг 2, иначе, в соответствии с алгоритмом R,получаем представление п : [Ai + A2 + + Am], такое, что ^2^ Ai = k - 1, и переходимна шаг 4.4) Создаем m узлов {s i}m=1, присоединяем их в качестве сыновей к узлу z в соответствиис порядком, заданным в представлении {Ai}m=1. Все пары < Ai, si > записываемв стек. Переходим на шаг 3.Рассмотрим свойства предложенного алгоритма полного разбиения.1. Если задан R(n) и Ai ^ 1 для всех представлений п Е Pn-1, то предложенныйалгоритм всегда остановится.Это утверждение основано на условии, что в дереве с n узлами имеется корень,следовательно, число n - 1 является количеством узлов во всех поддеревьях сыновейкорня. Алгоритм R получает некоторое представление A1 + A2 + + Am = n - 1,где Ai определяет число узлов в поддереве i-го сына и 1 ^ Ai ^ n - 1. Тем самым,последовательно применяя алгоритм R к числам, меньшим чем n, получим останов.Поскольку алгоритм строит корневое дерево и всегда останавливается, то он всегдастроит дерево.2. Число деревьев для заданного числа узлов равногде п = {A1 + A2 + + Ak = n - 1}; Pn-1 - множество представлений числа n - 1в соответствии с алгоритмом R.Применим этот алгоритм для генерации n-узловых корневых упорядоченных деревьев.Поскольку в таких деревьяхпорядок следования сыновей в узле важен и суммачисел узлов в поддеревьях сыновей равна n - 1, то для генерации таких деревьев можноиспользовать процедуру полного разбиения, основанную на генерации композицийнатурального числа n. ТогдаK (n + 1 ) = K (А,),i=1где п = {А1 + А2 + + Ak = n}; - множество композиций числа n. Известнотакже [2], что K(n + 1 ) = Cn, где Cn - число Каталана. Тогда получим следующеетождество для чисел Каталана:kL Cn ? I I II cс Л; - 1 i=1Из выражения (2) следует, что каждая композиция порождает некоторое подмножествокорневых упорядоченных деревьев. Для построения эффективного генератора[3] необходимо знать число деревьев для каждой композиции п Е Sn. Обозначимчерез T(i) число корневых упорядоченных деревьев для i-й композиции в лексикографическомупорядочении композиций. С использованием свойств композиций былополучено выражение для функции T(i):T(i) = 1, i = 0,T(i - 2m) 4+22, i > 0. (3)где m = Ll°S2(i)J, lm - Llog2(2m+1 - i - 1)J - 1, 0 ^ i < 2m+1 - 1,m i = 2Ш+1 _ 1.На рис. 1 изображен график функции T(i). Свойства этой функции таковы:1) ^22=0 1 T(i) = Cm, где Cm - число Каталана.2) T(2m - 1) = Cm-1.3) В точках i = 2m - 1 функция T(i) будет иметь локальные максимумы.Рис. 1. График функции T(i)В докладе будут подробно рассмотрены алгоритмы генерации корневых деревьевс использованием процедуры полного разбиения, основанной на разложениях, композицияхи разбиениях натурального числа n.

Скачать электронную версию публикации