跳转到内容

左倾红黑树

维基百科,自由的百科全书
左倾红黑树
类型tree
发明时间2008年
发明者罗伯特·塞奇威克
大O符号表示的时间复杂度
算法 平均 最差
空间
搜索
插入
删除

左倾红黑树(英语:Left-leaning red–black tree,缩写:LLRB)是一种类型的自平衡二叉查找树。它是红黑树的变体,并保证对操作相同渐近的复杂性,但被设计成更容易实现。

外部链接

[编辑]

论文

[编辑]

实现

[编辑]
作者 时间 语言 变体 附注 连结
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

其他

[编辑]