C++ 赤黒木のチェック関数

LLVMで使用されている平衡二分探索木である赤黒木のチェック関数についてのメモです。チェック関数を見ることで、赤黒木のルールの必然性が見えてきます。

二分探索木とは

赤黒木の前に二分探索木の説明を軽く行います。

二分探索木はノードごとに値が割り振られているとしたとき、枝を持つ全てのノードで下記の条件を満たします。

左ノード値  <  任意のノード値  <  右ノード値

二分探索木は二分探索¹をする際、再帰的なコーディングが可能なデータ構造です。

平衡二分探索木とは

平衡二分探索木とは、二分探索木の一種で木の高さ（根からの階層の数）を自動的にできるだけ小さく維持しようとするものを言います。赤黒木の他にも様々なアルゴリズムが存在します。

赤黒木とは

赤黒木は、各ノードに「赤」または「黒」という「色」をつけた二分探索木です。
通常の二分探索木としての条件のほか、以下の条件を適応することで平衡を維持します。

1. 各ノードは赤か黒の色をもつ
2. 根は黒である
3. 葉はすべて黒である
4. 赤のノードは黒ノードを2つ子に持つ
5. 根から葉までの道に含まれる黒いノードの数は、葉によらず一定である

赤黒木のチェック関数

値の大小関係のチェックは行いません。構造的に赤黒木のルールを満たしているのかのみ、チェックします。

rootノードのチェック

llvmの赤黒木では、Iteratorを扱う都合上、rootノードの親としてend_nodeが存在します。赤黒木のチェック関数では、赤黒木の構造チェックに合わせて、end_nodeのチェックも行います。

• end_nodeのチェック
  • ルートの親にend_nodeが存在する
  • ルートは親のend_nodeの左ノードである
• 赤黒木のチェック
  • ルートは黒である
  • ルートの持つノードがサブノードの条件を満たしている

ルートがNULLである場合は正しいノードとして、そこでチェックを終了します。

template <class _NodePtr>
bool __tree_invariant(_NodePtr __root) {
  if (__root == nullptr)
    return true;
  if (__root->__parent_ == nullptr)
    return false;
  if (!__tree_is_left_child(__root))
    return false;
  if (!__root->__is_black_)
    return false;
  return __tree_sub_invariant(__root) != 0;
}

サブノードのチェック

木の構造に問題がないか、赤が黒の子を2つ持っているかのチェックのみ、行います。

• 親子関係のチェック
  • 親子関係が適切につながっている
  • 左右のノードが同じではない
• 色のチェック
  • サブノードが赤ノードの場合は、左右が共に黒である
• 再帰的チェック
  • サブノードは、適切なサブノードを持つ

template <class _NodePtr>
unsigned __tree_sub_invariant(_NodePtr __x) {
  if (__x == nullptr)
    return 1;
  if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x)
    return 0;
  if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x)
    return 0;
  if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr)
    return 0;
  if (!__x->__is_black_) {
    if (__x->__left_ && !__x->__left_->__is_black_)
      return 0;
    if (__x->__right_ && !__x->__right_->__is_black_)
      return 0;
  }
  unsigned __h = __tree_sub_invariant(__x->__left_);
  if (__h == 0)
    return 0;
  if (__h != __tree_sub_invariant(__x->__right_))
    return 0;
  return __h + __x->__is_black_;
}

参考

---

1. ソート済みのデータを値の大小関係を用いて左右の値を見ていく手法。$O(\log{n})$の計算時間で実行できます。 ↩