3622
правки
Изменения
→Расширение структуры данных
=== Расширение структуры данных ===
Расширим [[СНМ_(реализация_с_помощью_леса_корневых_деревьев)|лес корневых деревьев]] следующим образом:
Это нововведение, очевидно, позволит нам менять элементы в дереве местами за <tex>O(1)</tex>.
* Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список <tex> \mathrm{C_{list}} </tex> ее детей. Будем считать, что дети упорядочены по направлению списка слева направо.
* Для корня каждого дерева храним двусвязный список <tex> \mathrm{NL_{list}} </tex> его детей, не являющихся листьями.
Эти три нововведения необходимы для нахождения листа в дереве (как оказывается, это гораздо более нетривиальная задача)
Введем также следующие определения:
