3

赤黒木への挿入と削除のための反復アルゴリズムへのポインタを教えてください。.Net/C# で利用可能なすべてのアルゴリズムは再帰に基づいており、非常に多数のデータを処理することは信頼できません (したがって、挿入/削除のための多数の再帰の深さ)。反復に基づいたものを持っている人はいますか?

注 : Goletas.Collection は、大量のデータに対して非常に効率的な AVL ツリーの反復アルゴリズムを使用します。Red-Black Tree にも同様のことが必要です。

4

3 に答える 3

9

ツリーベースのアルゴリズムは、本質的に再帰的です。

もちろん、それらを反復的に書き直すこともできますが、それは無駄な練習になります。理由は次のとおりです。

赤黒木や同様のデータ構造は自己均衡を保っており、その高さは格納されている値の数の対数になります。これは、再帰の上限に達することは決してないことを意味します。これには2000個の要素を挿入する必要がありますが、これは絶対に起こらないでしょう。コンピューターには十分なメモリがなく、今後も決してありません。

– 再帰にこだわる、それでいい。

于 2010-09-21T08:08:46.453 に答える
3

貴重なコメントをありがとうございました。見つけたばかりですが、VB6とCで。アイデアを理解するのに十分だと思います。ここにリンクがあります

  1. 記事
  2. Cソース
  3. VBソース

誰かがそれが役立つことを願っています。:)

于 2010-09-21T11:07:31.077 に答える
1

アルゴリズム入門には、 Thomas H Cormen、Charles E Leiserson、Ronald L Rivest、Clifford Stein によるバージョンがあります。

疑似コードは、 Google ブックス(270 ページ)でオンラインで入手できます。

コメントで指摘されているように、特にノードへのポインターが別の場所にある場合は、14/15 行zで置き換えるのではなくz、データをノードにコピーするアプローチは最適ではありません。yしたがって、13 ～ 16 行目は次のようになります。

do_fixup = y.color == BLACK

if y is not z:
    replace_parent(tree, y, z)
    y.left = z.left
    y.left.parent = y
    y.right = z.right
    y.right.parent = y
    y.color = z.color

if do_fixup:
    ...

wherereplace_parentは次のように定義されています (これは 7-12 行にも使用できます):

def replace_parent(tree, a, b):
    a.parent = b.parent
    if not b.parent:
        tree.root = a
    else:
        if b is b.parent.left:
            b.parent.left = a
        else:
            b.parent.right = a
于 2012-07-04T11:33:06.403 に答える