Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

### Vyvažované vyhledávací stromy

Kvůli zajištění větší rychlosti (menší asymptotické časové složitosti) operací byly vytvořeny speciální druhy binárních vyhledávacích stromů, které jsou průběžně vyvažovány, aby měly max. výšku menší než , kde je počet uzlů a nějaká konstanta.

Definice (Pomocné operace na stromech)

Pro vyvažování stromů při vkládání a odebírání uzlů se definují pomocné operace: pravá a levá rotace. Zachovávají vlastnosti bin. vyhledávacích stromů a jsou proveditelné v konstatním čase - jde jen o přepojení uzlů násl. způsobem (pro pravou rotaci na uzlu a levou na ):

(Zdroj obrázku: Wikipedia)

Definice (Červeno-černé stromy)

Červeno-černé stromy jsou binární vyhledávací stromy s garantovanou max. výškou , kde je počet uzlů, tj. operace na nich mohou mít asymptotickou časovou složitost . Pro jejich popis je nutné definovat interní uzly - všechny uzly stromu a externí uzly - na (interních) listech (a uzlech s jedním potomkem) uměle přidané NULLové ukazatele (de facto listy červeno-černého stromu). Externí uzly slouží jenom jako abstrakce pro popis stromů, při implementaci se s nimi neoperuje. Červeno-černý strom má tyto čtyři povinné vlastnosti:

1. Každý uzel (externí i interní) má definovanou barvu, a to černou nebo červenou.
2. Každý externí uzel je černý.
3. Každý červený vrchol musí mít oba syny černé.
4. Každá cesta od libovolného vrcholu k listům v jeho podstromě musí obsahovat stejný počet černých uzlů.

Pro červeno-černé stromy se definuje výška uzlu ( ) jako počet uzlů na nedelší možné cestě k listu v jeho podstromě. Černá výška uzlu ( ) je počet černých uzlů na takové cestě.

Věta (Vlastnosti červeno-černých stromů)

Podstrom libovolného uzlu obsahuje alespoň interních uzlů. Díky tomu má červeno-černý strom výšku vždy nejvýše (kde je počet uzlů). (Důkaz prvního tvrzení indukcí podle , druhého z prvního a třetí vlastnosti červeno-černých stromů)

Důsledek

Operace hledání (minima, maxima, následníka, ...), které jsou stejné jako u obecných binárních vyhledávacích stromů, mají garantovanou časovou složitost .

Algoritmus (Vkládání a odebírání uzlů v červeno černých stromech)

Obě operace mají podle garantované max. výšky garantovanou čas. složitost pro počet uzlů. Protože bez porušení vlastností červeno-černých stromů lze kořen vždy přebarvit načerno, můžeme pro ně předpokládat, že kořen stromu je vždy černý.

Vkládání vypadá následovně:

- Nalezení místa pro vložení a přidání nového prvku jako v obecných bin. vyhl. stromech, nový prvek se přebarví načerveno.
- Pokud je jeho otec černý, můžeme skončit - vlastnosti stromů jsou splněné. Pokud je červený, musíme strom upravovat (tady předpokládám, že otec přidávaného uzlu je levým synem, opačný připad je symetrický):
- Je-li i strýc červený, přebarvit otce a strýce načerno a přenést chybu o patro výš (je-li děd černý, končím, jinak můžu pokračovat až do kořene, který už lze přebarvovat beztrestně).
- Je-li strýc černý a přidaný uzel je levým synem, udělat pravou rotaci na dědovi a přebarvit uzly tak, aby odpovídaly vlastnostem stromů.
- Je-li strýc černý a přidaný uzel je pravým synem, udělat levou rotaci na otci a převést tak na předchozí případ.

Odebírání se provádí takto:

- Odstraním uzel stejně jako v předchozím případě. Opravdu odstraněný uzel (z přepojování) má max. jednoho syna. Pokud odstraňovaný uzel byl červený, neporuším vlastnosti stromů, stejně tak pokud jeho syn byl červený - to řeším jeho přebarvením načerno.
- V opačném případě (tj. syn odebíraného - - je černý) musím udělat násl. úpravy (přep. že je levým synem svého nového otce, v op. případě postupuji symetricky):
- prohlásím za dvojitě černý a této vlastnosti se pokouším zbavit.
- Pokud je bratr (buď ) červený, pak má 2 černé syny - provedu levou rotaci na rodiči , prohodím barvy rodiče a uzlu a převedu tak situaci na jeden z násl. případů:
- Je-li černý a má-li 2 černé syny, prohlásím za černý a přebarvím načerveno, rodiče přebarvím buď na černo (a končím) nebo na dvojitě černou a propaguji chybu (mohu dojít až do kořene, který lze přebarovat beztrestně).
- Je-li černý, jeho levý syn červený a pravý černý, vyměním barvy s jeho levým synem a na použiji pravou rotaci, čímž dostanu poslední případ:
- Je-li černý a jeho pravý syn červený, přebarvím pravého syna načerno, odstraním dvojitě černou z , provedu levou rotaci na a pokud měl původně (a ) červeného otce, přebarvím načerveno a tohoto (teď už levého syna ) přebarvím načerno.

Definice (AVL stromy (Adelson-Velsky & Landis))

AVL stromy jsou, podobně jako červeno-černé stromy, bin. vyhledávací stromy, které zaručují max. logaritmický nárůst výšky vzhledem k počtu prvků. Pro každý uzel se v AVL stromu definuje faktor vyvážení jako rozdíl výšky jeho levého a pravého podstromu: . Pro všechny uzly v AVL stromu platí, že .

Věta (Zaručení výšky AVL stromů)

Výška AVL stromu s vrcholy je . (Důkaz: buď AVL strom výšky s minimálním počtem uzlů. Ten má podstromy a atd., tj. velikost minimálního AVL stromu roste jako Fibonacciho posloupnost, tedy . Důkaz tohoto indukcí.)

Algoritmus (Operace na AVL stromech)

Vyhledávací operace se provádí stejně jako na obecných bin. vyhledávacích stromech, vkládání a odebírání prvků taky, ale pokud tyto operace poruší zákl. vlastnost AVL stromů ( ), je nutné provést vyvažování - pomocí rotací (které mohou být propagovány až ke kořeni). Při vkládání a odebírání je navíc nutné průběžně (nejhůře až ke kořeni) upravovat indikaci faktoru vyvážení jednotlivých uzlů.