1 Отредактировано Hack-Yer (2011-11-14 18:36:08)

Тема: Декартово дерево (treap)

Может добавить алгоритм построения декартово дерева за O(N) оффлайн, используя этот материал?

2

Re: Декартово дерево (treap)

Что делает процедура Union(t1, t2)?

3

Re: Декартово дерево (treap)

Может добавить алгоритм построения декартово дерева за O(N) оффлайн, используя этот материал?

Хм, мне казалось, что построение в оффлайн я уже добавлял (там же аж целых два способа существует smile ), а оказалось - нет ещё... Займусь этим, когда руки дойдут.

Что делает процедура Union(t1, t2)?

Сливает две декартовых дерева в одно, но, в отличие от Merge, никаких дополнительных предположений о деревьях не делается. Вообще эта операция полезна крайне редко (особенно учитывая её асимптотику), и стоит её вынести куда-нибудь в конец, как далеко не самый важный пункт.

4

Re: Декартово дерево (treap)

Ждем обновления  smile