Index / Reload
> uzakadeuさん[2]のコメントでスタックと呼んだのは First-In First-Out の配列を想定していました。カーネルはスレッドスタックのサイズに制限があるので再帰関数呼び出しを使うのは難しいと思われます。このスタックに red-black tree の各段の操作中のノードのポインタを保持しておくつもりでした。しかしよく考えると「rb_right と rb_left の両方が NULL なら free して親ノードに戻り、親側から自分を削除する」という処理を繰り返せばスタックも不要ですね。
言われてみれば、巡回する方がずっとシンプルですね。失礼しました。「スタック〜」とは再帰を使うということでしょうか？確認してませんが、解放するだけならループでいけそうに思えます。
> uzakadeuさんはい。struct mytype 構造体に struct list_head を入れて「red-black tree のノード間の双方向リンク」を作っておいて、一括削除はそちらを使うという方法に逃げました。これだと計算量が O(N) のオーダーですし。ただ最終的には black-red tree を巡回してリーフノードから削除するルーチンにしようと思っています。これも O(N) オーダーに収まりますし、余分なメモリ消費が押さえられますから。ツリーの深さ分のスタックが必要になりますが。
各ノードをツリー以外の方法（配列,リスト,etc）で“も”管理しておいて、そちらを使って解放するのはどうですか？
> uzakadeuさん
[2]のコメントでスタックと呼んだのは First-In First-Out の配列を想定していました。カーネルはスレッドスタックのサイズに制限があるので再帰関数呼び出しを使うのは難しいと思われます。
このスタックに red-black tree の各段の操作中のノードのポインタを保持しておくつもりでした。しかしよく考えると「rb_right と rb_left の両方が NULL なら free して親ノードに戻り、親側から自分を削除する」という処理を繰り返せばスタックも不要ですね。
言われてみれば、巡回する方がずっとシンプルですね。失礼しました。
「スタック〜」とは再帰を使うということでしょうか？
確認してませんが、解放するだけならループでいけそうに思えます。
> uzakadeuさん
はい。struct mytype 構造体に struct list_head を入れて「red-black tree のノード間の双方向リンク」を作っておいて、一括削除はそちらを使うという方法に逃げました。これだと計算量が O(N) のオーダーですし。
ただ最終的には black-red tree を巡回してリーフノードから削除するルーチンにしようと思っています。これも O(N) オーダーに収まりますし、余分なメモリ消費が押さえられますから。ツリーの深さ分のスタックが必要になりますが。
各ノードをツリー以外の方法（配列,リスト,etc）で“も”管理しておいて、そちらを使って解放するのはどうですか？