188
правок
Изменения
→Построение
==Построение==
Для того, чтобы отвечать на запросы относительно структуры леса необходимо сохранить информацию о том, как происходил процесс сжатия леса. Для этого будем хранить таблицу, в каждой строке которой записана информация о структуре леса после выполнения операций. Каждая клетка таблицы будет хранить информацию о вершине после выполнения операций <tex>\mathrm{Rake}</tex> и <tex>\mathrm{Compress}</tex>. Из информации будем сохранять родителя вершины, множество детей и метку, сжата ли вершина.<br>
Пример таблицы для следующей последовательности операций:
[[Файл:RC_tree_example.png|x200px|thumb|Пример выполнения операций.]]
{| class="wikitable"
|-
! Шаг
! align="center" | Операция
! <tex>1</tex>
! <tex>2</tex>
! <tex>3</tex>
! <tex>4</tex>
|-
| align="center" | 4
| align="center" | <tex>\mathrm{Rake}</tex>
| Родитель: {{---}}<br>Дети: <tex>\emptyset</tex>
| align="center" | {{---}}
| align="center" | {{---}}
| align="center" | {{---}}
|-
| align="center" | 3
| align="center" | <tex>\mathrm{Compress}</tex>
| Родитель: {{---}}<br>Дети: <tex>\{3\}</tex>
| align="center" | {{---}}
| Родитель: <tex>1</tex><br>Дети: <tex>\emptyset</tex>
| align="center" | {{---}}
|-
| align="center" | 2
| align="center" | <tex>\mathrm{Rake}</tex>
| Родитель: {{---}}<br>Дети: <tex>\{2\}</tex>
| Родитель: <tex>1</tex><br>Дети: <tex>\{3\}</tex>
| Родитель: <tex>2</tex><br>Дети: <tex>\emptyset</tex>
| align="center" | {{---}}
|-
| align="center" | 1
|
| Родитель: {{---}}<br>Дети: <tex>\{2\}</tex>
| Родитель: <tex>1</tex><br>Дети: <tex>\{3\}</tex>
| Родитель: <tex>2</tex><br>Дети: <tex>\{4\}</tex>
| Родитель: <tex>3</tex><br>Дети: <tex>\emptyset</tex>
|}
==Возможность параллельного построения==
