左倾红黑树
跳转到导航
跳转到搜索
Template:Copyedit Template:No footnotes Template:Infobox data structure 左傾紅黑樹（Template:Lang-en，縮寫：LLRB）是一種類型的自平衡二元搜尋樹。它是紅黑樹的變體，並保證對操作相同漸近的複雜性，但被設計成更容易實現。
外部連結
論文
- Robert Sedgewick. Left-leaning Red–Black Trees Template:Wayback. Direct link to PDF Template:Wayback.
- Robert Sedgewick. Left-Leaning Red–Black Trees (slides). Two versions:
- Linus Ek, Ola Holmström and Stevan Andjelkovic. May 19, 2009. Formalizing Arne Andersson trees and Left-leaning Red–Black trees in Agda Template:Wayback
- Julien Oster. March 22, 2011. An Agda implementation of deletion in Left-leaning Red–Black trees
- Kazu Yamamoto. 2011.10.19. Purely Functional Left-Leaning Red–Black Trees Template:Wayback
實現
| 作者 | 時間 | 語言 | 變體 | 附註 | 連結 |
|---|---|---|---|---|---|
| Robert Sedgewick, rkapsi | 2008 | Java | From this Sedgewick paper Template:Wayback | Left-leaning Red–Black Tree (LLRB)Template:Dead link -- this code has errors, see github comments | |
| David Anson | 2 Jun 2009 | C# | Maintaining balance: A versatile red-black tree implementation for .NET Template:Wayback | ||
| kazu-yamamoto | 2011 | Haskell | llrbtree Template:Wayback (Data.Set.LLRBTree) | ||
| gradbot | 2010 | F# | f-sharp-llrbt Template:Webarchive | ||
| Lee Stanza | 2010 | C | Includes discussion | Balanced Trees, Part 4: Left Leaning Red–Black Trees Template:Wayback | |
| Jason Evans | 2010 | C | 2-3 | rb.h | |
| Nicola Bortignon | December 8, 2010 | ActionScript 3 | AS3 implementation and discussion | ||
| william at 25thandClement.com | 2011 | C | 2-3 variant using iteration with parent pointers | llrb.h: Left-leaning Red–Black Tree Template:Wayback | |
| Maciej Piechotka | 2009 | Vala | Gee.TreeMap Template:Wayback | ||
| Petar Maymounkov | 2010 | Go | GoLLRB Template:Wayback | ||
| Sebastien Chapuis | 2015 | C | C - Left-leaning rbtree implementation |