116
правок
Изменения
м
→Расширение структуры данных
** '''вершиной дерева''' назовем объект, содержащий ссылки <tex>next</tex>, <tex>prev</tex> и <tex>head</tex> (где необходимо) для каждого из вышеперечисленных списков, а так же ссылку на соответствующий вершине '''элемент множества''';
** '''элемент множества''' - объект, содержащий значение элемента и ссылку на соотв. '''вершину дерева'''.
<br />Последнее нововведение, очевидно, позволит нам менять элементы в дереве местами за <tex>O(1)</tex>. <br />Первые три необходимы для нахождения листа в дереве (как оказывается, это гораздо более нетривиальная задача)<br/>
Введем также следующие определения:
}}
В нашей структуре данных будет поддерживаться следующий инвариант: '''дерево является либо только полным, либо только сокращеннымвсегда полное или сокращенное'''.
Этот инвариант влечет за собой очевидные следствия:
* Все деревья (и поддеревья) размера < 4 - сокращенные, а >= 4 - полные
