左倾红黑树

左倾红黑树（英语：Left-leaning red–black tree，缩写：LLRB）是一种类型的自平衡二叉查找树。它是红黑树的变体，并保证对操作相同渐近的复杂性，但被设计成更容易实现。^[1]

左倾红黑树
类型	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)}$

左倾红黑树（LLRB） 是 Robert Sedgewick 在 〈Left-Leaning Red-Black Trees〉（2008） 一文中提出，其核心理念是强制所有红边只能出现在左边，透过这个限制，把原本需要处理的对称情况“砍掉一半”，以此简化红黑树的实作复杂度，但仍保有与 2–3 树等价的平衡性

特性

左倾红黑树（Left-Leaning Red-Black Tree, LLRB）满足红黑树的所有性质：

• 每个节点不是红色就是黑色。
• NIL 节点（空节点）视为黑色。
• 红色节点不能有红色子节点（即不能连续红）。
• 从任一节点到其所有后代 NIL 节点的所有路径，都经过相同数量的黑色节点。
• 根节点依惯例视为黑色。

此外，左倾性质（left-leaning property）还规定：

• 如果一个节点只有一个红色子节点，这个红色子节点必须是左子节点。

左倾性质的好处是：能减少实作搜寻树操作时需要考虑的情况数量，让实作更简单。

与 2-3 树和 2-3-4 树的关系

LLRB（左倾红黑树）与 2–3–4 树是同构的（isomorphic）。 与传统红黑树不同的是，LLRB 强制 所有 3-node 都向左倾，因此 LLRB 与 2–3–4 树之间存在一对一的对应关系。 这表示：每一棵 LLRB 树，都唯一对应到一棵 2–3–4 树，反之亦然。

如果再额外加上一条限制：任一节点不得同时有两个红色子节点，那么 LLRB 树就会变得与 2–3 树同构，因为这个限制会禁止 4-node 的存在。

分析

所有已提出的红黑树算法，其特点都是： 在含有 N 个键的树中，最坏情况的搜寻时间会被限制在某个小常数倍的 log N。 而实际观察到的效能表现，通常也比这个最坏界限快上相同的倍数，接近一棵完全平衡树（perfectly balanced tree）中 log 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 （页面存档备份，存于互联网档案馆）

实现

作者	时间	语言	变体	附注	连结
罗伯特·塞奇威克, rkapsi	2008	Java		From this Sedgewick paper （页面存档备份，存于互联网档案馆）	Left-leaning Red–Black Tree (LLRB)[永久失效链接] -- this code has errors, see github comments
David Anson	2009年6月2日	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	2010年12月8日	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