左に傾いた赤黒の木

左傾斜赤黒木（LLRB ）は、ロバート・セジウィックによって導入された自己平衡二分探索木の一種です。これは赤黒木の変種であり、操作の漸近的複雑性は同じですが、実装が容易になるように設計されています。^{[ 1 ]}

左傾赤黒木は、赤黒木のすべての特性を満たします。

1. すべてのノードは赤か黒のいずれかです。
2. NILノードは黒色とみなされます。
3. 赤いノードには赤い子ノードがありません。
4. あるノードからその子孫であるNILノードへのすべての経路は、同じ数のブラックノードを経由する。
5. 根は（慣例として）黒色である。

さらに、左派寄りの不動産会社は次のように述べている。

6. ノードに赤い子ノードが1つしかない場合、それは左の子ノードでなければならない。

左寄りの特性により、探索木操作を実装する際に考慮しなければならないケースの数を減らすことができる。

LLRBツリーは、2-3-4ツリーと同型です。従来の赤黒木とは異なり、3ノードは常に左に傾いているため、この関係は1対1の対応となります。つまり、すべてのLLRBツリーには、対応する2-3-4ツリーが一意に存在し、その逆もまた同様です。

ノードが2つの赤い子ノードを持たないという追加要件を課すと、4ノードが禁止されるため、LLRBツリーは2-3ツリーと同型になります。セジウィックは、LLRB 2-3ツリーとLLRB 2-3-4ツリーの実装は、1行のコードの位置だけが異なると指摘しています。^{[ 1 ]}

提案されているすべての赤黒木アルゴリズムは、 N個のキーを持つ木において、最悪の場合の探索時間がlog Nの小さな定数倍に制限されるという特徴があり、実際に観察される動作は通常、最悪の場合の制限よりも同じ定数倍速く、完全にバランスのとれた木で観察されるであろう最適なlog N個のノードの探索に近いものとなっています。

具体的には、 N個のランダムなキーから構築された左寄りの赤黒2-3木において、セジウィックの実験は次のようなことを示唆している。

• ランダムに検索が成功すると、log ₂ N − 0.5 個のノードが調べられます。
• 樹木の平均高さは約2 ln Nです。
• 左部分木の平均サイズは対数振動的な挙動を示す。

• ロバート・セジウィックによる、2008年の論文に基づくLLRBのJava実装
• ロバート・セジウィック。2008年4月20日。LLRBの運用アニメーション。
• オープンデータ構造 - セクション 9.2.2 - 左傾赤黒木、パット・モリン

• ロバート・セジウィック。「左傾化した赤黒の木々」。PDFへの直接リンク。
• ロバート・セジウィック。「左派寄りの赤黒樹」2008年10月のスライド。
• Linus Ek、Ola Holmström、Stevan Andjelkovic。2009年5月19日。「AgdaにおけるArne Anderssonツリーと左寄りの赤黒ツリーの形式化」
• ジュリアン・オスター。2011年3月22日。左傾赤黒木における削除処理のAgda実装。
• 山本和。2011年10月19日。純粋機能主義的左傾赤黒木
• 左傾化した赤黒樹は有害とみなされている