Изменения
→Модификации для 2-го соображения
Это нововведение, очевидно, позволит нам менять элементы в дереве местами за <tex>O(1)</tex>.
==== Модификации для 2-го соображения ====
* Для каждой вершины дерева, не являющейся листом, будем хранить двусвязный список <tex> \mathrm{C_{listLIST}} </tex> ее детей. Будем считать, что дети упорядочены по направлению списка слева направо.* Для корня каждого дерева храним двусвязный список <tex> \mathrm{N_{listLIST}} </tex> его детей, не являющихся листьями.* Для каждого дерева (включая поддеревья) храним циклический двусвязный список <tex> \mathrm{DFS_{listLIST}} </tex> его вершин, располагаемых в порядке обхода в глубину, начиная с левой вершины.
Эти три нововведения необходимы для нахождения листа в дереве (как оказывается, это гораздо более нетривиальная задача).
