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

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

関連記事

int型のオーバーフロー(桁あふれ)とは?実際の発生パターンと併せてご紹介

  <目次> (1) int型のオーバーフロー(桁あふれ)とは?実際の発生パターンと併せてご紹介  (1-1) int型のオーバーフローとは?  (1-2) int型のオーバーフローが発生す …

Linuxサーバ(CentOS6)にEclipse(OXYGEN)をインストールする

0.目次 (1) JDKの概要  (1-1) JDKの種類  (1-2) JDKのバージョン(2018年2月時点) (2) JDKのインストール  (2-1) wget コマンドでJDK の rpm …

JFreeChartを使ってJavaで様々なグラフを簡単に描画する方法

(0)目次&概説 (1) 記事の目的  (1-1) 目的 (2) JFreeChartの概要  (2-1) JFreeChartとは?  (2-2) JFreeChartのアーキテクチャについて (3 …

JavaのJDBC接続でjava.sql.SQLRecoverableException: Closed Connectionが発生した時の解決メモ

(0)目次&概説 (1) エラー事象の概要  (1-1) エラーの発生状況  (1-2) エラーメッセージ全文 (2) エラーの原因 (3) エラーの対処方法  (3-1) エラーの修正内容  (3- …

Javaのstatic変数とは?その特徴及び付けた場合と付けない場合の違いを解説

(0)目次&概説 (1) static修飾子  (1-1) staticメンバとは?  (1-2) static変数   (1-2-1) static変数の説明と特徴   (1-2-2) static …

  • English (United States)
  • 日本語
Top