左倾红黑树
左傾紅黑樹(英語:Left-leaning red–black tree,縮寫:LLRB)是一種類型的自平衡二元搜尋樹。它是紅黑樹的變體,並保證對操作相同漸近的複雜性,但被設計成更容易實現。
左傾紅黑樹 | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
类型 | tree | ||||||||||||||||||||
发明时间 | 2008年 | ||||||||||||||||||||
发明者 | 羅伯特·塞奇威克 | ||||||||||||||||||||
用大O符号表示的时间复杂度 | |||||||||||||||||||||
|
外部連結
論文
- Robert Sedgewick. Left-leaning Red–Black Trees (页面存档备份,存于互联网档案馆). Direct link to PDF (页面存档备份,存于互联网档案馆).
- 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 (页面存档备份,存于互联网档案馆)
- 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 (页面存档备份,存于互联网档案馆)
實現
作者 | 時間 | 語言 | 變體 | 附註 | 連結 |
---|---|---|---|---|---|
Robert Sedgewick, rkapsi | 2008 | Java | From this Sedgewick paper (页面存档备份,存于互联网档案馆) | Left-leaning Red–Black Tree (LLRB)[永久失效連結] -- this code has errors, see github comments | |
David Anson | 2 Jun 2009 | C# | Maintaining balance: A versatile red-black tree implementation for .NET (页面存档备份,存于互联网档案馆) | ||
kazu-yamamoto | 2011 | Haskell | llrbtree (页面存档备份,存于互联网档案馆) (Data.Set.LLRBTree) | ||
gradbot | 2010 | F# | f-sharp-llrbt Archive.is的存檔,存档日期2012-12-17 | ||
Lee Stanza | 2010 | C | Includes discussion | Balanced Trees, Part 4: Left Leaning Red–Black Trees (页面存档备份,存于互联网档案馆) | |
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 (页面存档备份,存于互联网档案馆) | |
Maciej Piechotka | 2009 | Vala | Gee.TreeMap (页面存档备份,存于互联网档案馆) | ||
Petar Maymounkov | 2010 | Go | GoLLRB (页面存档备份,存于互联网档案馆) | ||
Sebastien Chapuis | 2015 | C | C - Left-leaning rbtree implementation |