B木 - naoyaのはてなダイアリー
昨年から続いているアルゴリズムイントロダクション輪講も、早いもので次は18章です。18章のテーマはB木(B Tree, Bツリー) です。B木はマルチウェイ平衡木(多分木による平衡木)で、データベースやファイルシステムなどでも良く使われる重要なデータ構造です。B木は一つの木の頂点にぶら下がる枝の本数の下限と上限を設けた上、常に平衡木であることを制約としたデータ構造になります。 輪講の予習がてら、B木を Python で実装してみました。ソースコードを最後に掲載します。以下は B木に関する考察です。 B木がなぜ重要なのか B木が重要なのは、B木(の変種であるB+木*1など)が二次記憶装置上で効率良く操作できるように設計されたデータ構造だからです。データベースを利用するウェブアプリケーションなど、二次記憶(ハードディスク)上の大量のデータを扱うソフトウェアを運用した経験がある方なら、いかにディ
SimpleBoxes | ツリー構造 (多分木 : N 分木) の実装
多分木と呼ばれるツリー構造は、親となるノードに、複数の子ノードがぶら下がるような形になっています。 この時、ひとつのノードに下に最大 2 つの子ノードしか存在できないようなツリー構造を「二分木」と言います。 Windows や Mac OS X で利用できるディレクトリ構造もツリーで表現できますし、JavaScript などで利用する DOM もツリー構造になっています。 root n1 n1-1 n1-1-1 n1-2 n2 n2-1 n2-2 n2-2-1 n3 n3-1 ツリー構造を表現する構造体 ここでは、C 言語で実装してみます。 perl, javascript や php などのスクリプト言語への変換はそれほど難しくないでしょう。 ノードの構造は、以下のように記述できます。 typedef struct node { struct node* child; struct no
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
