赤黒木
赤黒木は、各ノードに「赤」または「黒」という「色」をつけた二分探索木であり、赤黒木として有効なものであるためには、通常の二分探索木としての条件のほか、以下の条件が要求される。
各ノードは赤か黒の色をもつ。
根は黒である (この条件はしばし省かれる。根は赤から黒に変えることはできるので、解析にはほとんど影響しない)。
葉 (NIL) はすべて黒である。葉はすべて根と同じ色である。
赤のノードは黒ノードを2つ子に持つ(したがって、赤のノードの親ノードは黒である)。
任意のノードについて、そのノードから子孫の葉までの道に含まれる黒いノードの数は、選んだ葉によらず一定である(この条件は、「根から葉までの道に含まれる黒いノードの数は、葉によらず一定である」と言い換えることができる)。
これらの条件から、次の赤黒木の重要な性質が導かれる。
根から葉まで道で最長のものの長さは、根から葉までの道で最短のものの長さの二倍を超えない。
これは、赤黒木がある程度の平衡性をもっているということである。挿入・削除・検索といった操作は最悪のケースでは木の高さに比例した時間を要するので、このような赤黒木の性質から理論的に最悪時間計算量の見積もりが立つことになる。これは通常の二分探索木と異なる赤黒木の特徴である。
先ほどの条件からなぜ今の性質が導かれるのかを確認するには、条件4からわかる「赤黒木の根から葉までの道において赤のノードが2つ続くことはない」という性質がカギになる。すなわち、条件をみたす最短の道というのはすべて黒のノードからなる道であり、条件を満たす最長の道というのは赤と黒のノードが交互に現れるような道となる。
そして、条件5より、根から葉までの道がすべて同じ個数の黒のノードを含むことから、最長の道の長さは最短の道の長さの二倍を超えないという上記の性質が導かれる。(ここで、根と葉は黒のノードである。)
一般に、データの木構造 (データ構造)による表現では、ノードが一つだけの子をもつことや、葉ノードがデータをもつこと(言い換えれば、データをもつノードが子をもたないこと)を可能としている場合も多い。赤黒木においてもそのような考え方を導入することができないわけではないが、それをすると先ほどの性質をいくつかの点で修正する必要が生じ、またアルゴリズムが複雑になってしまう。そのため、この記事においては、今まで説明したように「空の葉」(nil leaf、null leaf)を用い、葉はデータをもたずただ木の終端を意味するだけのノードであるとした。なお、このような葉ノードは図をかく際には省略することも多く、その結果、赤黒木が先ほどの条件をみたさないように見えることがある。しかしもちろん、実際には内部の(つまり、葉ではない)ノードはすべて、空の葉を含めて2つの子をもっているわけである。
ところで、赤黒木について、二分木の(ノードではなく)辺に色がついたものであるという説明がなされていることもある。これは、この記事における「ノードの色」を「ノードとその親とを連結する辺の色」に読み替えたものである(ただし、「根ノードの色」に対応するものはないため、この記事での条件2にあたる条件が不要となる)。