116
правок
Изменения
→Расширение структуры данных
** '''вершиной дерева''' назовем объект, содержащий ссылки <tex>next</tex>, <tex>prev</tex> и <tex>head</tex> (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине '''элемент множества''';
** '''элемент множества''' - объект, содержащий значение элемента и ссылку на соотв. '''вершину дерева'''.
Введем также следующие определения:
{{Определение
|id=def_reduced_tree
|definition=Дерево, либо состоящее ровно из одной вершины, либо же из 1 вершины ранга 1 и листьев ранга 0, называется '''сокращенным''' (''reduced'')
}}
{{Определение
|id=def_full_tree
|definition=Дерево называется '''полным''', если каждый из его узлов либо является листом с рангом 0, либо имеет не менее 3 детей.
}}
В нашей структуре данных будет поддерживаться следующий инвариант: '''дерево является либо только полным, либо только сокращенным'''.
Этот инвариант влечет за собой очевидные следствия:
* Все деревья (и поддеревья) размера < 4 - сокращенные, а >= 4 - полные
* Каждая вершина, среди детей которой есть хотя бы 1 нелистовая вершина, имеет не менее 3 детей (это не позволяет дереву вытягиваться в бамбук, например)
