左倾红黑树

左傾紅黑樹（，縮寫：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 的理論最佳節點訪問數。

論文

• [http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.139.282 Robert Sedgewick. Left-leaning Red–Black Trees] . [http://www.cs.princeton.edu/~rs/talks/LLRB/LLRB.pdf Direct link to PDF] .
• Robert Sedgewick. Left-Leaning Red–Black Trees (slides). Two versions:

** [http://www.cs.princeton.edu/~rs/talks/LLRB/08Dagstuhl/RedBlack.pdf Robert Sedgewick. Left-Leaning Red–Black Trees (slides), from seminar at Dagstuhl in February 2008. Outdated.]
** [http://www.cs.princeton.edu/~rs/talks/LLRB/RedBlack.pdf Robert Sedgewick. Left-Leaning Red–Black Trees (slides), from April 2008; updated]

• [http://web.student.chalmers.se/groups/datx02-dtp/ Linus Ek, Ola Holmström and Stevan Andjelkovic. May 19, 2009. Formalizing Arne Andersson trees and Left-leaning Red–Black trees in Agda]
• [https://web.archive.org/web/20160304043338/http://www.reinference.net/llrb-delete-julien-oster.pdf Julien Oster. March 22, 2011. An Agda implementation of deletion in Left-leaning Red–Black trees]
• [http://www.mew.org/~kazu/proj/red-black-tree/ Kazu Yamamoto. 2011.10.19. Purely Functional Left-Leaning Red–Black Trees]

實現
其他

• [http://www.cs.princeton.edu/~rs/talks/LLRB/movies/ Robert Segdewick. 20 Apr 2008. Animations of LLRB operations]
• [http://opendatastructures.org/versions/edition-0.1e/ods-java/9_2_RedBlackTree_Simulated_.html#SECTION001222000000000000000 Open Data Structures - Section 9.2.2 - Left-Leaning Red–Black Trees]
• [http://read.seas.harvard.edu/~kohler/notes/llrb.html Left-Leaning Red-Black Trees Considered Harmful]