左倾红黑树

左傾紅黑樹（，縮寫：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  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 

Category:搜索树