左倾红黑树

左倾红黑树（英语：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 （页面存档备份，存于互联网档案馆）