KMI/WEB Tvorba webových stránek

Red-Black stromy

Červeno černé stromy jsou dalším typem binárních vyhledávacích stromů. Což znamená, že stále platí uspořádání stromu - všechny uzly nalevo jsou menší a všechny uzly napravo jsou větší. U červeno černých stromů přidáme každému uzlu další položku - color, která bude u nového node nastavena na červenou. Jinak může být přebarvena na černou.

Červeno černé stromy mají několik pravidel, které je třeba dodržovat, aby se strom nacházel v konzistentním stavu. Pokud se některou z úprav stave strom nekonzistentní, budeme tuto situaci neprodleně řešit.

Pravidla

• zavádíme speciální vrchol NIL
• kořen je černý
• každý list (NIL) je černý
• každý červený uzel má dva černé potomky
• každá cesta od uzlu do listu obsahuje stejný počet černých uzlů

Odstranění vrcholu

Odstranění vrcholu je velmi podobné odstranění vrcholu v binárním vyhledávacím stromu. Rozdělíme si operaci delete na 2 části

• delete
• delete Fixup - pouze pokud byl odebíraný uzel černý

delete-fixup

Pokud odebreme černý uzel, pak nebude platit poslední podmínka Red Black stromu (každá cesta z uzlu do listu obsahuje stejný počer černých uzlů).

• sourozenec je červený
• sourozence obarvím na černou
• rodiče přebarvím na červenou
• na rodiče provedu levou rotaci
• sourozenec je černý a oba jeho potomci jsou černí
• sourozence obarvím na červenou
• aktuálním uzlem označím rodiče
• sourozenec je černý, jeho levý potomec je červený a pravý potomek černý
• červeného potomka nastavím na černou
• sourozence nastavím na červenou
• provedu pravou rotaci na sourozence
• sourozenec je černý, jeho pravý i levý potomek je červený
• sourozence nastavím na barvu rodiče
• rodiče nastavím na černou
• pravého potomka sourozence obarvím na černou
• na rodiče provedu levou rotaci

B-stromy

B strom parametrizujeme přirozeným číslem t > 2.Dále je definován následujícími podmínkami

• Počer klíčů ve vrcholech
• V každém vrcholu stromu je maximálně 2t - 1 klíčů a minimálně t - 1 klíčů. Výjimkou je kořen, kde může být méne než t - 1 klíčů.
• počet potomků
• Pokud vbrchol obsahuje n klíčů, má 0 nebo n + 1 potomků
• Hloubka listů
• Všechny listy jsou ve stejné hloubce.
• Podmínka uspořádání
• Klíče jsou ve vrcholu uspořádány vzestupně. Pro podstromy opět platí, že vše nalevo od klíče je menší a vše napravo od klíče je větší.

Vyhledávání

Poměrně podobné s binárním vyhledávacícm stromem vzhledem k uspořádání, ale nyní porovnáváme vyhledávanou hodnotu s celým polem klíčů v uzlu.

Vkládání

Opět první vyhledáme uzel, kde klíč patří a následně musíme zjistit, jestli se do uzlu vleze. Pokud ano, uzel vložíme. Pokud se nám již klíč do uzlu nevejde, rozdělíme uzel, kde by měl přijít podle mediánu a vytvoříme dva nové uzly - první se vším nalevo od mediánu z uzlu a druhý se vším naprovo od mediánu. Medián umístíme do rodiče na správné místo. Pokud je rodič plný, proces opakujeme.

Mazání

Smazání klíče probíhá ve dvou fázích. V první fázi klíč smažeme a pomocí search najdeme vrchol ve kterém jsme odstraňovali.

• Pokud je list
• V poli posuneme prvky větří než odstranění o jedno políčko do leva (spojíme pole aby tam nebylo prázdné místo) a počet klíčů v uzlu snížíme o 1.
• Pokud není list
• Najdeme v pravém podstromu od odstraněného klíče minimální klíč m (pořádkový následník) a tímto klíčem nahradíme smazaný uzel. Pořádkového následníka smažeme (rekurzivně).

Ve druhé fázi mazání upravujeme nekorektní počty klíčů ve vrcholech.

• Převod klíče ze sourozence
• Poslední uzel z levého potomka převedeme do rodiče a klíč z rodiče přesuneme do pravého potomka na začátek. Případně opačně z pravého do levého.
• Sloučení se sourozencem
• Dva sourozence dáme do jednoho uzlu a přidáme k němu "medián" z rodiče.

Úkol

Úkol bude zadán i vypracován na hodině. V případě absence mě kontaktujte.