Изменения

Рассмотрим более подробно, как необходимо хранить клетки таблицы <tex>\mathrm{Rake-Compress}</tex> дерева. Для вершины необходимо сохранить ее родителя, а также множество детей. Для того, чтобы обрабатывать каждую клетку таблицы за <tex>O(\log{n})</tex>, нужно производить операции с множеством детей за <tex>O(1)</tex>. <br><br>На самом деле, множество детей хранится для того, чтобы определятьРассмотрим, в каких случаях можно ли сжать вершину. Если :* если детей у вершины больше одного, то ее точно нельзя сжать. Если , * если у неё нет детей, то ее можно сжать только во время операции <tex>\mathrm{Rake}</tex>* если у вершины один ребёнок, то её возможно сжать во время операции <tex>\mathrm{Compress}</tex>. Чтобы определить , можно ли применить операцию <tex>\mathrm{Compress}</tex> к вершине, в том случае, когда у нее один ребёнок, нужно узнать, как какой бит был сгенерирован на текущей итерации для ребёнка(один из трёх битов, генерируемых при операции <tex>\mathrm{Compress}</tex>). Для этого необходимо знать номер вершины-ребёнка. Значит, необходимо уметь нам нужно определять, кто находится какие элементы находятся в множестве детей только в том случае, если в нём не более одного элементакогда размер множества равен <tex>1</tex>. Поэтому, всю информацию о множестве можно хранить с помощью двух величин {{---}} хранить количество элементов в множестве и сумму их номеров. Поддерживая сумму номеров детей и их количество, можно эффективно узнавать номер вершины-ребёнка, когда это необходимо. Данная оптимизация позволяет за <tex>O(1)</tex> получать номер ребёнка и за <tex>O(1)</tex> обновлять множество детей.<br><br>