跳转到内容

左倾红黑树

维基百科,自由的百科全书
左傾紅黑樹
类型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

其他

[编辑]