Datové struktury
Líné vyvažování stromů
Uvažujme binární vyhledávací strom, který je na počátku vyvážený a na kterém chceme vykonávat jen operace Search a Delete.
► Delete je zbytečně komplikované: Co takhle jeho složitost odložit?
Datové struktury
Líné vyvažování stromů 2
Uvažujme nyní binární vyhledávací strom, který je na počátku prázdný a na kterém chceme vykonávat jen operace Search a Insert.
► Kdy o stromu řekneme, že je vyvážený?
► Jak těžké je vyvážit nevyvážený strom?
► Jak vyvažovat po Insertu tak, aby to nebylo moc často?
Datové struktury
Scapegoat tree (scapegoat - obětní beránek)
► kombinace dvou předchozích nápadů
► zjednodušení: maximálně jeden podstrom se musí vyvažovat po Insertu (to je scapegoat)
► další zjednodušení: nemusíme si nic pamatovat v uzlech, stačí tři čísla pro celý strom, tj. extra paměť je pouze 0(1)
Datové struktury
Soubor řetězců
Chceme datovou strukturu, která udržuje soubor řetězců a podporuje následující operace:
► NEwSTRiNG(a) - vytvoří nový řetězec o jednom znaku
► Concat(S, 7") - odstraní řetězce S a T ze souboru a vloží řetězec S • T
► Reverse(S) - odstraní řetězec S ze souboru a vloží jeho zrcadlový obraz
► Lookup(S, k) - vrátí ktý znak z řetězce S
Chceme, aby Concat měla amortizovanou složitost 0(\ogn) a ostatní operace měly v nejhorším případě složitost 0(1).
Datové struktury
Splay tree
► vyvažování pomocí rotací
► splay (rozevření) - posunutí vrcholu až do kořene pomocí rotací (cena: hloubka vrcholu)
Operace Search, Insert, Delete používají splay. Jaká je jejich amortizovaná složitost?