左傾紅黑樹

左傾紅黑樹（英語：Left-leaning red–black tree，縮寫：LLRB）是一種類型的自平衡二元搜尋樹。它是紅黑樹的變體，並保證對操作相同漸近的複雜性，但被設計成更容易實現。

左傾紅黑樹
類型	tree
發明時間	2008年
發明者	羅伯特·塞奇威克
用大O符號表示的時間複雜度 算法 平均 最差 搜尋 ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ 插入 ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ 刪除 ${\displaystyle O(\log n)}$ ${\displaystyle O(\log n)}$ 用大O符號表示的空間複雜度 空間 ${\displaystyle O(n)}$ ${\displaystyle O(n)}$

外部連結

論文

• Robert Sedgewick. Left-leaning Red–Black Trees （頁面存檔備份，存於網際網路檔案館）. Direct link to PDF （頁面存檔備份，存於網際網路檔案館）.
• Robert Sedgewick. Left-Leaning Red–Black Trees (slides). Two versions:
  • Robert Sedgewick. Left-Leaning Red–Black Trees (slides), from seminar at Dagstuhl in February 2008. Outdated. （頁面存檔備份，存於網際網路檔案館）
  • Robert Sedgewick. Left-Leaning Red–Black Trees (slides), from April 2008; updated （頁面存檔備份，存於網際網路檔案館）
• Linus Ek, Ola Holmström and Stevan Andjelkovic. May 19, 2009. Formalizing Arne Andersson trees and Left-leaning Red–Black trees in Agda （頁面存檔備份，存於網際網路檔案館）
• Julien Oster. March 22, 2011. An Agda implementation of deletion in Left-leaning Red–Black trees
• Kazu Yamamoto. 2011.10.19. Purely Functional Left-Leaning Red–Black Trees （頁面存檔備份，存於網際網路檔案館）

實現

作者	時間	語言	變體	附註	連結
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.today的存檔，存檔日期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

其他

• Robert Segdewick. 20 Apr 2008. Animations of LLRB operations （頁面存檔備份，存於網際網路檔案館）
• Open Data Structures - Section 9.2.2 - Left-Leaning Red–Black Trees （頁面存檔備份，存於網際網路檔案館）
• Left-Leaning Red-Black Trees Considered Harmful （頁面存檔備份，存於網際網路檔案館）