Levostranný červeno-černý strom - Left-leaning red–black tree - Wikipedia
| Levostranný červeno-černý strom | |||||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Typ | strom | ||||||||||||||||||||
| Vynalezeno | 2008 | ||||||||||||||||||||
| Vynalezl | Robert Sedgewick | ||||||||||||||||||||
| Časová složitost v velká O notace | |||||||||||||||||||||
| |||||||||||||||||||||
A levo-nakloněná červeno-černá (LLRB) strom je typ samovyvažující binární vyhledávací strom. Jedná se o variantu červeno-černý strom a zaručuje stejnou asymptotickou složitost pro operace, ale je navržen tak, aby se snáze implementoval.
Vlastnosti levostranně červeno-černého stromu
Všechny algoritmy červeno-černého stromu, které byly navrženy, se vyznačují nejhorším časem hledání omezeným malým konstantním násobkem log N na stromě N klíče a chování pozorované v praxi je obvykle stejný násobek rychleji než v nejhorším případě, blízký optimálnímu log N zkoumané uzly, které by byly pozorovány v dokonale vyváženém stromu.
Konkrétně v levostranně červeno-černém provedení 2–3 strom postaven z N náhodné klíče:
- Náhodné úspěšné vyhledávání prozkoumá log2 N − 0.5 uzly.
- Průměrná výška stromu je asi 2 log2 N
- Průměrná velikost levého podstromu vykazuje log-oscilační chování.
externí odkazy
Doklady
- Robert Sedgewick. Levostranné červeno-černé stromy. Přímý odkaz na PDF.
- Robert Sedgewick. Levostranné červeno-černé stromy (diapozitivy). Dvě verze:
- Linus Ek, Ola Holmström a Stevan Andjelkovic. 19. května 2009. Formalizace stromů Arne Andersson a levostranných červeno-černých stromů v Agda
- Julien Oster. 22. března 2011. Implementace odstranění Agda v levostranných červeno-černých stromech
- Kazu Yamamoto. 2011.10.19. Čistě funkční červeno-černé stromy se sklonem doleva
Implementace
| Autor | datum | Jazyk | Varianta | Poznámky | Odkaz |
|---|---|---|---|---|---|
| Robert Sedgewick | 2008 | Jáva | Z tento papír Sedgewick | ||
| David Anson | 2. června 2009 | C# | Udržování rovnováhy: Všestranná implementace červeno-černého stromu pro .NET | ||
| kazu-yamamoto | 2011 | Haskell | llrbtree (Data.Set.LLRBTree ) | ||
| Lee Stanza | 2010 | C ++ | Zahrnuje diskusi | Vyvážené stromy, část 4: Levé šikmé červeno-černé stromy | |
| Jason Evans | 2010 | C | 2-3 | rb.h | |
| Nicola Bortignon | 8. prosince 2010 | ActionScript 3 | Implementace AS3 a diskuse | ||
| william na 25thandClement.com | 2011 | C | 2-3 varianty využívající iteraci s nadřazenými ukazateli | llrb.h: Levostranný červeno-černý strom | |
| Maciej Piechotka | 2009 | Vala | Gee.TreeMap | ||
| Petar Maymounkov | 2010 | Jít | 2-3 | GoLLRB | |
| Sebastien Chapuis | 2015 | C | C - Implementace levého rbtree | ||
| Seungyoung Kim | 2015 | C | Varianta 2-3-4 | C implementace | |
| Robin Heggelund Hansen | 2018 | Jilm | Realizace jilmu | ||
| R Pratap Chakravarthy | 2019 | Rez | Realizace rezu |
jiný
- Robert Sedgewick. 20. dubna 2008. Animace operací LLRB
- Otevřené datové struktury - část 9.2.2 - Červeno-černé stromy, které se šikmo opírají, Pat Morin
- Levostranné červeno-černé stromy považovány za škodlivé
 | Tento algoritmy nebo datové struktury související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to. |