-- --

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

03 31

赤黒木をがんばってみた。 javascript

こんにちは火頭です。

好きなメソッドは console.log()です。
ということでプログラミング関連のお話です。

赤黒木に魅せられたここ一ヶ月でした。
ルールを調べあげ、その複雑さに顔が赤黒くなりながらも、ようやくテストプログラムが完成しました。 

なぜ赤黒木かというと...いや自分でも全くわからないんですけど。

強いて言えば、
ルールを与えることで、自分でバランスを取り、頑なにデータを維持するその姿に、熟練の職人に通じる何かを感じたためでしょうか。(私が作ったテストプログラムはバグだらけで、データを簡単にロストするんですけど)

これを作ったからといって私の生活に何ら影響を与えないので、完全に趣味です。


まず赤黒木を知らない人のために簡単に説明します。

(Wikiより抜粋)
赤黒木(あかくろぎ)は、コンピュータ科学のデータ構造である平衡二分木の一種で、主に連想配列の実装に用いられている。 

赤黒木は、探索、挿入、削除などの操作における最悪時間計算量がO(log n) (nはツリーの要素数)と短く、複雑ではあるが実用的なデータ構造として知られている。


...だそうです。詳しく知りたい人は自分でググってもらいたいと思いますが、要はデータの格納や管理の仕方です。平衡二分木というものはこういう見た目をしています。↓
Binary_search_tree.png

例えば「6を探して」という命令を出した時、一番上にある「8」からチェックを開始して「6は8より小さい」→左へ→「6は3より大きい」→右へ→「6を発見」→ありましたよ。という具合に探索します。データが数万件とかの場合に、1、2、3、4、5、6…と探すより手間が省けるというお話です。

平衡二分木の一種である赤黒木、いざ制作に取り掛かったのは良いのですが、javascriptでの実装はコードが落ちてなくて他の言語のコードの意味を調べる必要が出てきてかなり大変でした。

さらに「回転」についての理解が甘かったり、葉はnullで扱っていたため「葉は黒である」という便利ルールを採用していないことになり例外処理を延々と書き続けるはめになったのです。

何はともあれ、とりあえず一段落しましたし、これ以上の実装は時間の問題ということで。

これから実装に挑戦する方は(よっぽどモノ好きだと思います)何よりルールをよぉ~く理解しておくことをおすすめします。

私はいきなり赤黒木から始めたのですが、2分探索木→AVL木→赤黒木 と順を追って学習しておくと効率が良いと思います。普通そうするでしょうけど。

特に気をつけることとして「左右の回転」。
回転の影響は、本人の「子世代~爺世代」までにおよびます。
私は「本人とその親」の視点だけに注目してたので、失敗が続きました。

「子の親を付け替える・爺の子を付け替える」これらを忘れるとエラーが出ると思います。これは意味上は「親の子をつけかえる・親の親をつけかえる」などと同じ意味になりますが、PCには関係ありません、きちんとプログラムに書いておかないと、関係がめちゃくちゃになります。

あとは挿入・削除の場合分け処理のときに、あるノードが木の内側なのか・外側なのかを調べる処理が必ず必要になります。親の右子の右子が黒だから外側で、その場合は親が爺に左回転で…等、頭がこんがらがるので、わかりやすくメモしておきましょう。

というわけで実際に画面を見ましょう。頭を左へ傾けながら見てください。RとBで赤と黒を表現しています。


1から順にループで数字を入れているので、やや右に傾いていますが、これでバランスがとれているということになります。
右と左どちら側から上に辿っても黒の数が同じということになります。(横には数えませんよ)

ここにノード(数字)を追加すると...

ほら


ほらぁ!!


数字の位置が移動して、できるだけ左右に均等に配置されるように、木が自動でバランスを取ります。なんと美しいことでしょう。

削除も同様、データを入れ替え、必要あればバランスを取ります。

こんな感じに。


制作はとても大変だったのですが、オブジェクト指向を考える良い機会になったかもしれません。アルゴリズムって素敵。

...
え?これが何の役に立つのかって?




Comment
Trackback
Comment form
 管理者にだけ表示を許可する

火頭

Author:火頭

火頭工房の中の人。 

ギター弾きます。
ゲームします。
お酒飲みます。

新ブログ


火頭工房のサイト

プロフィール
PR

Page Top
Powered by FC2 Blog | | Template Design by スタンダード・デザインラボ
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。