データ構造の基礎知識　後編　木構造

データベースの学習をしていたときの復習です。

データ構造の基礎知識　前編　メモリとポインタ、配列と連結リスト

データ構造の基礎知識　中編　ハッシュ

今回はもう少し複雑な「木構造」について考えてみます。

木構造とは？

下記のような特徴があります。

• 要素同士に親子関係がある
• 親は複数の子を持てる
• 子から親へ循環して親子関係になることはない

２分木構造

• 親は０～2個の子供を持つ
• 大小関係は左の数<親<右の数となる

下記リンクが一番イメージしやすい。

メリット

• キーが常にソート済み
• 各要素へのアクセスがO(logn)
• 要素を追加してもハッシュのようなrehashは不要
• ハッシュと違い、無駄になるメモリがないためメモリ効率が良い

デメリット

• 偏った木構造(枝が一本のみ)の場合,O(n)になる

そこでこのデメリットを補うために、B木という構造が使われます。

B木

• 各ノード内では値はソート済みの状態で保存されている
• 各値の左側から生えている枝からたどれる値はその値よりも小さい値
• 各値の右側から生えている枝からたどれる値はその値よりも大きい値