Изменения

Перейти к: навигация, поиск

Декартово дерево

9 байт убрано, 07:23, 8 апреля 2011
рисунки запилены!
Дерамиды были предложены Сиделем (Siedel) и Арагоном (Aragon) в 1996 г.
== Операция split ==
== Операция split ==
[[file:split.png|thumb|200px|Операция split]]
Операция <tex>\mathrm{split}</tex>(''распилить'') позволяет сделать следующее: разрезать декартово дерево <tex>T</tex> по ключу
равна <tex>\mathcal{O}(h)</tex>, где <tex>h</tex> {{---}} высота дерева. Так как высота декартова дерева {{---}}
<tex>\mathcal{O}(\log n)</tex>, то и операция <tex>\mathrm{split}</tex> работает за <tex>\mathcal{O}(\log n)</tex>.
 
{{TODO|t=Запилить рисунок}}
== Операция merge ==
[[file:merge.png|thumb|200px|Операция merge]]
Рассмотрим вторую замечательную операцию с декартовыми деревьями {{---}} <tex>\mathrm{merge}</tex>(''слить'').
Рассуждая аналогично операции <tex>\mathrm{split}</tex> приходим к выводу, что трудоёмкость операции <tex>\mathrm{merge}</tex>
равна <tex>\mathcal{O}(\log n)</tex>.
 
{{TODO|t=запилить рисунок}}
== Операция add==
403
правки

Навигация