赤黒木
赤黒木というデータ構造は、最悪のケースにおける計算量が、データの挿入・削除・検索のいずれにおいても、データ構造のうちで最善のものの一つである。このため、リアルタイム・コンピューティングのような時間計算量に敏感なアプリケーションにおいて有益である。また、計算幾何学で用いるデータ構造など、最悪のケースでの計算量を保証する必要のあるデータ構造の基礎としても有用なことが多い。 赤黒木と同様に平衡二分木であるAVL木は、赤黒木に比べて平衡性についての条件が厳しく、そのためAVL木では最悪のケースを想定すると挿入や削除の際の回転操作の回数が赤黒木より多くなってしまう。
赤黒木は関数型プログラミングにおいても部分的に重要であり、永続的データ構造を実現するデータ構造の一つとして、変更後も以前の値を保持し続けるような連想配列や集合を実装する際に広く用いられるものの一つである。なお、このような永続性をもったタイプの赤黒木では、挿入や削除のたびに、時間だけでなく O ( log  n ) {\displaystyle {\mathcal {O}}(\log n)} のオーダーの空間が必要となる。
赤黒木は2-3-4木にアイソメトリックである。すなわち、任意の2-3-4木に対して、少なくとも一つの赤黒木でその2-3-4木と同じデータを同じ順序でもつものが存在する。このとき、2-3-4木における挿入および削除の各操作は、赤黒木におけるカラー・フリッピングおよび回転の各操作に等価であり、そのため、2-3-4木を考えることは赤黒木の背景にある理論を理解する上で重要である。実用性の高くない2-3-4木が、アルゴリズムの入門書において赤黒木の直前によく紹介されているのは、このためである。