問題の記述

各二分木のノードが並列オブジェクトで表されている 二分木探索アルゴリズムを考える. 各ノードはキーと, そのキーにつけられた値を持つ. ノードのキーは 左の子のキーよりも大きく, 右の子のキーよりも小さいという invariant を維持する. ノードの定義は次のようになる.

template 
class bintree_node
{
  /* associates KEY with VALUE */
  int key; T value;
  /* pointers to children */
  bintree_node * left, * right;
public:
  /* create a leaf node */
  bintree_node (int k, T val) { 
    key = k; value = val; left = right = 0; }
  /* find value associated with K */
  T lookup (int k);
  /* establish a new association between K and VAL */
  void insert (int k, T val);
};

二分木に新しい関係を加える insert メソッドの記述を考える. それはもしキーが木にすでに加えられていれば 0 を返し, そうで なければ 1 を返す. 可能な自然な記述は次のようになる.

/* establish a new association between K and VAL, maintaining the
   following invariant: 
   "(KEY of LEFT) < (KEY of THIS) < (KEY of RIGHT)" */
int insert (int k, T val)
{
  if (k < key) {
    /* If THIS already has LEFT child, delegate to 
       the child, otherwise create a new leaf node */
    if (left) return left->insert (k, val);
    else { left = new bintree_node (k, val); return 1; }
  } else if (k == key) {
    /* K has already been associated with another value */
    conflicting_key (k); return 0;
  } else {
    if (right) return right->insert (k, val);
    else { right = new bintree_node (k, val); return 1; }
  }
}

このメソッドはまず二分探索によって関係を挿入する適当な場所を見つけ, その後その場所に新しいノードを加える.

一つのオブジェクトへのメソッドを serialize する 並列オブジェクト指向言語においては, 木へのアクセスは 各ノードベースではなく, 木全体ベースで serialize される これは ルートノードでの insert メソッドは 再帰呼び出しの鎖全体が終了した時その時に限り終了するからである.

もしデータ構造が 木(やアサイクリックグラフ)ではなくサイクリックなグラフになっている場合は 再帰呼び出しがデッドロックに陥るかもしれないため, この種の serialization はずっとさらに問題が大きい. これは [2] での自己再帰呼びだしのアドホックな 扱いによっては避けられないことに注意してほしい.