Rainbow Engine

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

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

関連記事

Javaの型とは?ジェネリクスの基本や使い方をご紹介

<目次> (1) Javaの型とは?ジェネリクスの基本や使い方をご紹介  (1-1) <T>とは?ジェネリクスとは?  (1-2) ジェネリクスを使う利点  (1-3) ジェネリクスをクラ …

TwitterのAPIでハッシュタグからツイートを探すJavaプログラムのご紹介

<目次> (1) TwitterのAPIでハッシュタグからツイートを探すJavaプログラムのご紹介  (1-1) プログラムの概要  (1-2) サンプルプログラム  (1-3) 操作イメージ (1) …

JSP/Servletで画面毎のアクセスカウンターを作成してみた(パート2:ソース解説編)

(1) 仕様について (2) ソースコード  (2-1) AccessCounter2.java   (2-1-1) サンプルPG   (2-1-2) サンプルPG解説  (2-2) DbConnec …

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

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

JSP Servletで共通のヘッダーを設定する方法

<目次> (1) JSP Servletで共通のヘッダーを設定する方法  (1-1) 構文  (1-2) サンプルプログラム  (1-3) 参考 (1) JSP Servletで共通のヘッダーを設定す …

  • English (United States)
  • 日本語
Top