跳至內容

左傾紅黑樹

維基百科,自由的百科全書
左傾紅黑樹
類型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

其他