Rainbow Planet

IT技術を分かりやすく簡潔にまとめることによる学習の効率化、また日常の気付きを記録に残すことを目指します。

Java

木構造の探索における計算量の違いや木構造の種類について(B木/二分木/2-3探索木)

投稿日:2020年10月15日 更新日:

<目次>

(1) 木構造の探索における計算量の違いや木構造の種類について(B木/二分木/2-3探索木)
 (1-1) 木構造について
 (1-2) 「B木」構造
 (1-3) 「二分木」構造
 (1-4) 「2-3探索木」構造
 (1-5) 比較表①:計算量のオーダー
 (1-6) 比較表②:平衡の保ち方

(1) 木構造の探索における計算量の違いや木構造の種類について(B木/二分木/2-3探索木)

今回は「「B木」、「二分木」、「2-3探索木」の3つの木構造について、探索の計算量や特徴などを纏めます。

(1-1) 木構造について

木構造とはデータを探索するアルゴリズムを使用する際に、探索元のデータを格納するデータ構造の事です。見た目が「木」のように枝分岐しているため「木構造」と呼ばれています。
木はノード(点)とエッジ(線)から成り、次の条件を満たす必要があります。 ①ノードが環状になっていない事(輪になっていない)②全てのノードが連結されている(全てのノードが辿れる)③エッジは向きを持っていない

(図111)

目次にもどる

(1-2) 「B木」構造

■子ノードの規則
・全ての子ノードが同じ階層にいる必要があります。
・子ノードはM個持ち得ます(M≧3)
■使用シーン
データが「ストレージ」に格納されている状況で利用します。ツリーの高さを減らし、枝を増やす事で高速な探索を実現します。
■使用例
多くのデータベースのDBMSのインデックス構造として利用されています(OracleDB他)。

目次にもどる

(1-3) 「二分木」構造

■子ノードの規則
・0~2個の子ノートを持ちます(3つ以上は不可)
■使用シーン
データが「メモリ上」でソートされている条件下で利用します。主にアプリ開発の実装(プログラミング)で利用されます。

目次にもどる

(1-4) 3探索木」構造

■子ノードの規則
・最大3つの子ノードを持つ
・値が1つのノード ⇒ 子は2つ
・値が2つのノード ⇒ 子は3つ

目次にもどる

(1-5) 比較表①:計算量のオーダー

(表)

アルゴリズム 子ノード数 探索 データ追加・削除
二分探索
(木ではない)
logN

×
(データ増減がある場合は実用的でない)
2-3探索木 2~3 logN

logN

(赤黒木・AVL木)

B木 M
(M≧3)
logN

logN

平衡二分木 2 logN

logN

(赤黒木・AVL木)

目次にもどる

(1-6) 比較表②:平衡の保ち方

木構造には「バランス」の概念があり、探索を効率良く行うためには木の「平衡を保つ」必要があります。

「平衡」の条件は具体的には「全てのリーフノード(葉)の深さがおおよそ同じに保たれている事」になります。次の表では木構造の種類毎にどのように平衡を保つのか?の概要を記載しています。

(表)

アルゴリズム 平衡の保ち方
2-3探索木 ■Insertの流れ →★(図161)
①挿入ポイントを探索します(最下層に挿入する)
②追加位置の値が1つの場合は、その場所に追加する
③追加位置の値が既に2つある場合は、追加して3つになった際の中央の値を、1つ上のノードに格上げする
(※最悪のケース、根まで繰り返し伝播する)

B木 ■Insertの流れ →★(図161)
「2-3探索木」と同じ手順

平衡二分木 平衡木にもいくつか種類がありますが、次に紹介する平衡木は平衡を保つ仕組みを持っています。
①AVL木
②赤黒木

(図161)

(備考①)二分木について
・探索回数は二分を繰り返すためlogNであるが、これは完全二分木の時の話です(葉付近以外のノードで全て2つの子を持つ)
・二分木で平衡でない木(例:○―○―○―○の様な一直線)の場合は逐次探索と差が無くなってしまいます。
・そのため、表中で記載している「AVL木」や「赤黒木」といった平衡を保つ仕組みが必要となります。

目次にもどる

Adsense審査用広告コード


Adsense審査用広告コード


-Java

執筆者:


comment

メールアドレスが公開されることはありません。 * が付いている欄は必須項目です

関連記事

「サーブレットコンテナ」や「サーブレットのライフサイクル」とは?(サンプルプログラム付)

※本記事は「サーブレットとは?その役割やHelloWorldサンプルコードのご紹介」の続編です。 (0)目次&概説 (2) サーブレットコンテナの基本  (2-1) サーブレットコンテナとは?  (2 …

Javaのラッパークラスとは?使い方や一覧をご紹介

<目次> (1) Javaのラッパークラスとは?使い方や一覧をご紹介  (1-1) ラッパークラスとは?  (1-2) 構文(オブジェクト生成)  (1-3) 代表的なメソッド(Integerを例に) …

Javaのswitch-case文の構文や使い方を紹介+UFOキャッチャーの座標移動プログラムも紹介

<目次> (1) Javaのswitch-case文の構文や使い方を紹介  (1-1) switch-caseの構文  (1-2) else-if文との比較 (2) サンプルプログラムの紹介  (2- …

Javaの選択ソートとは?アルゴリズムの流れ+サンプルプログラムをご紹介

<目次> (1) バイナリ―サーチとは?Javaのサンプルプログラムを用いて解説  (1-1) バイナリ―サーチのアルゴリズム  (1-2) バイナリ―サーチの性能(処理回数)  (1-3) バイナリ …

Javaのアノテーションとは?種類や使い方についてご紹介

<目次> (1) Javaのアノテーションとは?自作の手順やフィールド値の取得方法もご紹介  (1-1) アノテーションとは?  (1-2) アノテーションの種類  (1-3) 自作アノテーションの作 …

  • English (United States)
  • 日本語
Top