Červené a černé stromy: popis, rysy

Rudolf Bayer vyvinul systém "červenohnědých stromů" již počátkem 70. let. Jméno bylo dáno L. Gimpasovi a R. Sedgwickovi.

Jaký červeno-černý strom

Mělo by být poznamenáno, že jde o jeden druh self-balancing binárních stromů, které poskytují počítat velikost výšky z počtu uzlů a produkovat primární a základní procesy hledání stromu v krátkém čase. Takové operace zahrnují připojení, vyloučení a vyhledávání uzlu. Zůstatek je poskytován na základě vyplnění atributu označení aplikace uzlu, barvy. Tato vlastnost přebírá jeden z možných konceptů a je označena jednou z uvedených barev.

Počet černých jednotek na větvi od počátku (kořen) až po poslední (list) se nazývá černá výška stromu.

Vznik termínu

Při popisu vlastního vyvažovacího vyhledávacího stromu v jeho tvorbě autoři článku asi ani neočekávali, že se stanou zakladateli nového termínu. Osud však přikázal, aby tiskárna měla pouze dvě barvy. Označují také každý bit, který se připojí k dalšímu uzlu.

Aplikace

V počítačové vědě se používají červeno-černé stromy ke generování srovnatelných dat, které mohou obsahovat různé výňatky a části nápisů nebo čísel.

Můžete vytvořit červeně-černý strom ActionScript, Python, C ++ a téměř jakýkoli jiný programovací jazyk. Je to velmi jednoduché. Červeno-černý strom Java je také docela rozšířená.

Vlastnosti

Černé a červené stromy jsou vyhledávací stromy v binárním souřadnicovém systému. V těchto systémech má každý uzel určitou hodnotu barev. Může trvat na jednom z výše uvedených zápisů. Vedle všech použitých podmínek na binární stromy a u zvažovaných odrůd se tato pravidla používají také:

• Barva uzlu je výhradně jedna z výše uvedených dvou. Neexistují žádné další možnosti, ale také se odráží ve jménu termínu.
• Kořen stromu by měl být vždy černý. Výjimky jsou možné, ale taková odchylka od pravidla přispívá k riziku, že strom bude vyvážen.
• Všechny listy mají nulovou hodnotu (NIL) a jsou označeny černou barvou.
• Je důležité zajistit, aby dva potomci každého červeného nadřazeného uzlu byli černí.
• Jakákoli snadná cesta z určitého uzlu k libovolnému dětskému uzlu poskytuje přesně stejný počet černých strukturních jednotek.

Někdy jsou červeno-černé stromy interpretovány jako banální binární vyhledávací stromy. Jejich rozdíly jsou určeny pouze skutečností, že namísto určitých barevných uzlů jsou žebra vyfarbena ve výše uvedených hodnotách.

Proč zvolit přesně červeno-černé stromy

Černé a červené stromy jsou jednou z nejběžnějších variant samo-vyvažujících binárních vyhledávacích stromů, které jsou nejčastěji řešeny prakticky.

Co vysvětluje jejich popularitu? Praxe je líná a stojí za to přijmout. Cokoliv, co je příliš těžkopádné a obtížně použitelné, a současně produkuje srovnatelný výsledek podobně jako jednodušší metody, zemře nebo jde do vzdálené budoucnosti. Taková prevalence u lidí červenohnědých stromů je vysvětlena skutečností, že nejčastěji poskytují optimální rovnováhu mezi kvalitou a úrovní rovnováhy a lstivostí její údržby.

Například, jestliže je porovnáme s těmi, které jsou dokonalé v míře jejich rovnováhy stromy, pak může vzniknout situace, kdy je pozorováno, že "ideální" zástupci kladou příliš nekompromisní požadavky. A v podmínkách provádění akcí vyloučení ze stromu nebo zvratu se věnuje příliš mnoho času a úsilí na stabilizaci rovnováhy v dané situaci.

Procesy

Proces korektury černo-červených binárních stromů je téměř stejný pro všechny ostatní binární vyhledávací větve. To je pravda, protože jakýkoli černý a červený strom je jednou z konkrétních variant klasického binárního vyhledávacího stromu.

Při práci s nimi je však třeba vzít v úvahu, že je pravděpodobné, že přímá produkce akce zahrnující nebo vyloučená data může způsobit poškození struktury černo-červených stromů. Obrovská výhoda spočívá v tom, že pro rekonstrukci nemovitostí je třeba relativně malý počet akcí, jako je změna barvy a často méně než tři otáčky stromu. Ve skutečnosti všechny tyto operace netrvají dlouho.

Chcete-li pokračovat v akci vložení nebo zapnutí prvku, je nutné zvýšit další uzel. Tato funkce je podobná ve všech binárních vyhledávacích stromech. Dalším krokem je zbarvení uzlu červeně. Jediným rozdílem je to, že pokud přidáte list nejprve při vkládání do binárního vyhledávacího stromu, pak černá a červená neposkytují žádné informace. Proto místo nich je přidán vnitřní uzel, který má červenou barvu a dva černé potomky.

Dále naše akce jsou přímo podmíněny barvou přilehlých uzlů. Pro ně je použit termín "strýc". Přímá analogie s genealogickým stromem. Proto:

• Vlastnost, že všechny listy si uchovávají černé barvy, musí být vždy realizována.
• Sekvence skutečnosti, že dva deriváty každého červeného uzlu si zachovávají černou barvu, může být přerušena. Ale k tomu dochází pouze při přidání červeného uzlu, při změně barvy černé na červenou nebo při otáčení celého stromu.
• Mějte také na paměti, že může být porušena sekvence od uzlu k listu, včetně stejného počtu černých uzlů. K tomu dojde pouze tehdy, když je černý uzel zapnutý, červený prvek se změní na černé a také v opačném případě přebarvení černé na červenou. To lze provést i při otáčení stromu.

Když jsme studovali všechny výše uvedené skutečnosti, není těžké pochopit, jak je vyhledávání prováděno v červeno-černém stromu.

Interpretace takového jednoduchého konceptu jako stromu je zajímavá s popisem jeho barvy - červeno-černá nebo černě hnědá. Nyní jste si toho také vědomi.