二分木の要素の削除の仕方

Program Debug

二分木でキーを元にそれに対応する葉を探し出して削除するのは簡単だ。
しかし、葉へのポインタを元にO(1)で削除する方法が思いつかない。ナカナカ難しい。
私は考えていた。カクカクシカジカ、3日間くらいだった。出来ると思っていた。*1

だが、私の扱っている二分木の葉のデータ構造ではO(1)で削除する事は絶対に出来ないことに気が付いた。
ハッシュ法と同じく*2 バカな物思いにふけっていた・・・。
何故なら、親の葉へのポインタが葉の構造体に宣言していなかったのだ。
何故かメモリリークやAccess Violationがでる・・・*3と、思っていたら、親の葉を更新していなかったのが問題だった。
私は「C言語によるアルゴリズム辞典」*4に書いている二分木を参考に*5組んでいた。
これは、葉の右左の幹（ left ポインタと right ポインタ ）へのポインタを受け取って
それを元に、ポインタ先及び自分自身を更新しているプログラムなのだ。
なので、葉へのポインタのみではO(1)でそれ自身を削除する事は出来ない。
それを実現するには前述のように「親の葉へのポインタ」を宣言してやらなければならない。
例：

typedef struct dkc_2TreeNode{

  ///左ノード

  struct dkc_2TreeNode *left;

  ///右ノード

  struct dkc_2TreeNode *right;

  ///親ノード(これが足りなかった)

  struct dkc_2TreeNode *parent;

  

  //以下は御自由に・・・

  

  ///キーへのポインタ

  void *key;

  ///データへのポインタ

  void *data;

  ///データのサイズ

  size_t data_size;

}DKC_2TREE_NODE;


それに気づかず、3日間も悩んだ時間は何だ!!!ヽ(‘Д´)ノムキィ
またしても、○|￣|＿＿|￣|○ {デースケドガー} である。

*1:何故なら、STLでのstd::mapのeraseにはerase(iterator)メンバ関数が存在したからだ。しかし、今になって考えてみると、Red Black treeで実装されているのだから、親の葉を参照していなければ実装できないのでこれはこれで当たり前のような気もする。

*2:http://d.hatena.ne.jp/studiokingyo/20050208

*3:ちなみに、こう言う時に 即 原因がわからないときは机上デバッグ(または騎乗位でバック)を行うと速くバグが見つかる。事実、私も机上デバッグでバグに気づいた。

*4:http://studiokingyo.fc2web.com/dxlib/shiryou/book.html

*5:ちなみに、http://oku.edu.mie-u.ac.jp/~okumura/algo/archive/からダウンロードできるアーカイブ内にあるtree.cがそれ