Index / Reload

Comment on 2010-11-17

2010-11-17 について、コメントがあればどうぞ!
E-mail アドレスは公開されません。URL は公開されます。
なお、管理者の判断により予告なくコメントを削除することがあります。 ご了承下さい。

パスワードを入力すると後からコメントの修正が可能です。

確認:下の Check の項目に fuCLX8tC をコピーして入力してね。

お名前:
E-mail or URL:
Check: ← 上の方にある確認文字列を入力してね。
Password:
コメント:
* nminoru 2010-11-21 13:36:23 [Edit]

> uzakadeuさん
[2]のコメントでスタックと呼んだのは First-In First-Out の配列を想定していました。カーネルはスレッドスタックのサイズに制限があるので再帰関数呼び出しを使うのは難しいと思われます。

このスタックに red-black tree の各段の操作中のノードのポインタを保持しておくつもりでした。しかしよく考えると「rb_right と rb_left の両方が NULL なら free して親ノードに戻り、親側から自分を削除する」という処理を繰り返せばスタックも不要ですね。

* uzakadeu 2010-11-21 07:22:27 [Edit]

言われてみれば、巡回する方がずっとシンプルですね。失礼しました。

「スタック〜」とは再帰を使うということでしょうか?
確認してませんが、解放するだけならループでいけそうに思えます。

* nminoru 2010-11-21 03:01:41 [Edit]

> uzakadeuさん
はい。struct mytype 構造体に struct list_head を入れて「red-black tree のノード間の双方向リンク」を作っておいて、一括削除はそちらを使うという方法に逃げました。これだと計算量が O(N) のオーダーですし。

ただ最終的には black-red tree を巡回してリーフノードから削除するルーチンにしようと思っています。これも O(N) オーダーに収まりますし、余分なメモリ消費が押さえられますから。ツリーの深さ分のスタックが必要になりますが。

* uzakadeu 2010-11-20 14:52:41 [Edit]

各ノードをツリー以外の方法(配列,リスト,etc)で“も”管理しておいて、そちらを使って解放するのはどうですか?

Powered by くっつき BBS