左倾红黑树
外观
左倾红黑树 | |||||||||||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
类型 | tree | ||||||||||||||||||||
发明时间 | 2008年 | ||||||||||||||||||||
发明者 | 罗伯特·塞奇威克 | ||||||||||||||||||||
用大O符号表示的时间复杂度 | |||||||||||||||||||||
|
左倾红黑树(英语:Left-leaning red–black tree,缩写:LLRB)是一种类型的自平衡二叉查找树。它是红黑树的变体,并保证对操作相同渐近的复杂性,但被设计成更容易实现。
外部链接
[编辑]论文
[编辑]- 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 |