赤黒木

【 あかくろぎ (red black tree) 】

平衡二分探索木の一種で，(1) すべての頂点は赤か黒，(2) 赤い頂点は必ず黒い親をもつ，(3) 根とすべての葉は黒，(4) 根から葉へのどのパスも同数の黒い頂点を含む，という4つの条件を満たす．この条件より，根から葉へのどのパスも，長さが2倍以上違わなくなり，ゆえに要素数構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle n \, } の赤黒木の高さは構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathrm{O}(\log n) \,} になる．赤黒木は，木の形の変化に対して再平衡化を行うことにより，要素の挿入・削除・ある要素が含まれるかの確認を構文解析に失敗 (MathML、ただし動作しない場合はSVGかPNGで代替（最新ブラウザーや補助ツールに推奨）: サーバー「https://en.wikipedia.org/api/rest_v1/」から無効な応答 ("Math extension cannot connect to Restbase."):): {\displaystyle \mathrm{O}(\log n) \,} で実行できる．