Karteziánský strom

karteziánský strom
Angličtina  Treap
Typ Binární vyhledávací strom
Rok vynálezu 1989
Autor Raimund Siedel, Cecilia Aragon
Složitost v O-symbolech
Průměrný Při nejhorším
Budova
Vyhledávání
Vložit
Odstranění
 Mediální soubory na Wikimedia Commons

Kartézský strom  je binární strom, jehož uzly ukládají:

Odkaz na nadřazený uzel je volitelný, je žádoucí pouze pro algoritmus vytváření lineárního stromu.

Kartézský strom není samovyvažující v obvyklém smyslu a používá se z následujících důvodů:

Nevýhody karteziánského stromu:

Terminologie

V anglické literatuře se kartézský strom vytvořený pro pole daných klíčů a náhodných vah, které jim byly při sestavování přiřazeny, nazývá peněženkové slovo treap , protože kombinuje vlastnosti třídícího haldového stromu ( heap ) a náhodného binárního stromu ( strom ) s logaritmickým očekáváním výšky. V ruštině byla slova ducha [1] ( strom + halda ), deramide ( strom + pyramida ), kurevo ( halda + strom ) navrhována podobně jako slovo treap .

Nejjednodušší algoritmus pro konstrukci kartézského stromu

Nejjednodušeji pochopitelný algoritmus pro konstrukci kartézského stromu ze sady párů dat (x, y) je následující. Seřaďme všechny dvojice podle klíče x a výslednou sekvenci klíčů y očíslujme:

y(1), y(2), y(3), …, y(n).

Pojďme najít minimální klíč y. Nechť je y(k). Bude to kořen stromu. Klávesa y(k) rozděluje sekvenci kláves y na dvě:

y(1), …, y(k-1); y(k+1), …, y(n).

V každém z nich najdeme minimum y - to budou potomci uzlu y (k) - vlevo a vpravo. S výslednými 4 kusy (možná méně) uděláme totéž. Navrhovaný algoritmus pro konstrukci kartézského stromu je založen na rekurzi: najdeme minimum y v posloupnosti a přiřadíme jej jako kořen. found y rozdělí sekvenci na dvě části, pro každou z nich spustíme algoritmus pro konstrukci kartézského stromu.

Schematicky to lze zapsat takto:

T( y(1), ..., y(n) ) = kořen: y(k) levý_strom: T( y(1), ..., y(k−1) ) pravý_strom: T( y(k+1), ..., y(n))) kde y(k) = min( y(1), ..., y(n) )


Vlastnost jednoznačnosti struktury

Z tohoto algoritmu vyplývá, že množina dvojic (x, y) jednoznačně určuje strukturu kartézského stromu. Pro srovnání si všimněte, že sada klíčů, která je uložena v binárním vyhledávacím stromu, neurčuje jednoznačně strukturu stromu. Totéž platí pro binární haldu – jaká bude struktura binární haldy (jak jsou klíče rozmístěny mezi uzly), závisí nejen na samotné sadě klíčů, ale také na pořadí, ve kterém jsou přidávány. V karteziánském stromě taková nejednoznačnost neexistuje.

Algoritmus konstrukce lineárního stromu

Další algoritmus pro vytváření stromu je také založen na rekurzi. Teprve nyní postupně přidáme prvky y a přebudujeme strom. Strom T(y(1), …, y(k+1)) sestaví ze stromu T(y(1), …, y(k)) a dalšího prvku y(k+1).

T( y(1), ..., y(k+1) ) = F ( T( y(1), ..., y(k) ), y(k+1) )

V každém kroku si zapamatujeme odkaz na poslední přidaný uzel. Bude vpravo. Ve skutečnosti jsme objednali klíče y podle klíče x, který je k nim připojen. Protože je kartézský strom vyhledávacím stromem, po promítnutí na vodorovnou čáru se musí klávesy x zvětšovat zleva doprava. Uzel zcela vpravo má vždy nejvyšší možnou hodnotu klíče x.

Funkce F, která mapuje kartézský strom T(y(1), …, y(k)) předchozího kroku a následujícího y(k+1) do nového stromu T(y(1), …, y(k) +1)), následovně. Je definována vertikála pro uzel y(k+1). Musíme rozhodnout o jeho horizontále. Nejprve zkontrolujeme, zda nový uzel y(k+1) může být správným potomkem uzlu y(k) - to by mělo být provedeno, pokud y(k+1) > y(k). V opačném případě vystoupíme po svahu od uzlu y(k) a podíváme se na hodnotu y, která je tam uložena. Stoupejte po svahu nahoru, dokud nenajdeme uzel, kde je hodnota y menší než y(k+1), načež z y(k+1) uděláme jeho pravého potomka a z jeho předchozího pravého potomka uděláme levého potomka y( k+ jedna).

Tato amortizace algoritmu (v součtu všech kroků) funguje v lineárním čase (podle počtu přidaných uzlů). Jakmile jsme totiž „přešlápli“ jakýkoli uzel, stoupali po svahu, už se s ním při přidávání dalších uzlů nikdy nesetkali. Celkový počet kroků po svahu tedy nemůže být větší než celkový počet uzlů.

Poznámky

  1. ↑ Donald Knuth . Umění počítačového programování, díl 3. Třídění a vyhledávání = The Art of Computer Programming, díl 3. Třídění a vyhledávání. - 2. vyd. - M .: "Williams" , 2007. - ISBN 0-201-89685-0 .

Odkazy

Literatura