Red Black Treeから要素を削除するアルゴリズムの解説を探しています。

要素の挿入に関しては多くを見つけましたが
削除については見当たりません。

サンプルコード付だとよりいいです。

回答の条件
  • URL必須
  • 1人2回まで
  • 登録:2005/03/11 14:49:34
  • 終了:--

回答(3件)

id:Kumappus No.1

くまっぷす回答回数3784ベストアンサー獲得回数1852005/03/11 15:14:09

ポイント15pt

ここにちょっとだけremoveの例が出ています。

AVL木ですが、removeは最初は実装するな、と。

あとで木のバランスをとる必要があるとも書かれていますね。

ここがわりと詳しそうです。ただ言語がC#かな?これは。

id:aukjs

回答ありがとうございます。

> CodeGuru: Balanced Binary Tree

これ、Red Black Treeなんですか?

>AVL木ですが

Red Black Treeを質問しているのですが。

>removeは最初は実装するな、と。

いつかは実装しますよね。

> ここがわりと詳しそうです。ただ言語がC#かな?これは。

C#は私が対応していません。C/C++, JAVAでお願いします。

サンプルはあくまで補助的な意味で、主はアルゴリズムの解説を求めています。

バランスツリーに属する1ツリー構造のものでもなく

あくまで求めているのは、Red-Black-Treeの要素削除です。

2005/03/11 15:45:20
id:dasm No.2

dasm回答回数66ベストアンサー獲得回数02005/03/11 16:00:02

ポイント15pt

applet です。

class ファイルを手元にダウンロードして逆コンパイルすればソースも手に入らない事はないです。

id:aukjs

回答ありがとうございます

んー、それはもう見ているんですよね。

実をいうとred-black-treeの削除を含んだソースは手元にあることはあるんです。

なので、

 ***** コードだけというのは不要です ******

解析しろといえば解析できますが

理屈→コードが正しいあり方で

コード→理屈はちょっと違うと思います。

2005/03/11 16:07:38
id:dasm No.3

dasm回答回数66ベストアンサー獲得回数02005/03/11 16:30:36

ポイント40pt

英語ですがどうぞ。

英語を読まなくても図とコードを合わせて読みつつ翻訳サービスにでもかければわかるはずです。

http://www.amazon.co.jp/exec/obidos/ASIN/4797306947/hatena-q-22

Amazon.co.jp: Javaで学ぶアルゴリズムとデータ構造: Robert Lafore, 岩谷 宏: 本

日本語の解説だったら、図書館で本を借りてきて読んだほうが早いでしょう。タダですし。

Java を書くのでしたらこの本の内容ぐらいは一通り理解しておくとよいと思います。

id:aukjs

回答ありがとうございます。

> CS 660: Red-Black

私が求めていたのは、まさにこんな解説です。

英語ですが、なんとかします。

>Amazon.co.jp: 本: Javaで学ぶアルゴリズムとデータ構造

参考にします。まずは立ち読みから。。。

2005/03/11 16:35:21
  • id:dasm
    自分の日記と重複しますが

    http://puma.wellesley.edu/~cs231/fall01/red-black.pdf
    http://www.cs.usna.edu/~crabbe/2004-08/SI321/red-black/red-black.html
    http://www.personal.kent.edu/~mlu3/CSCourses/AdvAlgorithms/CLR-BOOK/books/book6/chap14.htm
    これらも参考になれば幸いです。
    このサイトの元ネタは「アルゴリズムイントロダクション」という三巻構成の本(原著は一冊で、 1,000 ページを越える)なので、そちらをあたるのもよろしいかと。
  • id:aukjs
    Re:自分の日記と重複しますが

    すばらしいです。
    逆に自分の勉強不足を痛感させられます。

    情報をありがとうございました。

この質問への反応(ブックマークコメント)

トラックバック

「あの人に答えてほしい」「この質問はあの人が答えられそう」というときに、回答リクエストを送ってみてましょう。

これ以上回答リクエストを送信することはできません。制限について

絞り込み :
はてなココの「ともだち」を表示します。
回答リクエストを送信したユーザーはいません