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

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

外部链接

编辑

论文

编辑

实现

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

其他

编辑