左傾紅黑樹(英語: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

其他

編輯