左倾红黑树

左傾紅黑樹
类型	tree
发明时间	2008年
发明者	羅伯特·塞奇威克
用大O符号表示的时间复杂度 算法 平均 最差 搜索 $O(\log n)$ $O(\log n)$ 插入 $O(\log n)$ $O(\log n)$ 删除 $O(\log n)$ $O(\log n)$ 用大O符号表示的空间复杂度 空间 $O(n)$ $O(n)$

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

左傾紅黑樹（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

其他

• 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 （页面存档备份，存于互联网档案馆）