トリッキーコードネット トップへ戻る   C/C++, Java, Perl, PHP, JavaScript, アルゴリズム, ショートコーディング, IOCCCコードの解説, 等々

サイト情報

トリッキーなコード

7行プログラミング

物凄いコード集

アルゴリズム

データ構造

C/C++な話題

コードサンプル

ツール/環境構築

開発ノウハウ 等

ネタ/ジョーク集

おススメ書籍/サイト

サイトTOP >> データ構造 >> 二分探索木(Binary Search Tree)とは? (C言語)

二分探索木(Binary Search Tree)とは?

連結リストと並ぶ最も有名なデータ構造である、二分探索木(二分木と略す場合もある)について説明します ^^;)
(連結リストについては、こちらを参照して下さい)

「構造体へのポインタ」をメンバ中に持つ構造体 (これをノードという) があり、
その各ノードが繋がって一つのデータ集合体をなす
という点では、二分探索木も連結リストと考え方は同じです。

しかし、各ノードの繋がり方は、連結リストと大きく異なります。


連結リストのノード繋がりを図に表すと、以下の様になります。(双方向連結リストを例に挙げています)
連結リスト(Linked-List)のノード繋がり


一方、二分探索木のノード繋がりを図に表すと、以下の様になります。
二分探索木(Binary Search Tree)のノード繋がり


1つのノードが最大2つの下位ノードと繋がりながら、ピラミッド状の階層構造を築きます。

見方を変えるならば、
頂点のノードをroot(根)とした、逆さまの木(ツリー)が構成されています。
各ノードが最大2つのノードへと枝分かれをする木構造の為、二分木という名前がついたワケです^^;)


二分探索木の用語説明

下の図を用い、幾つか用語の説明をします。 二分探索木の用語説明 まず、図の○にあたるデータの1つ1つをノード(NODE:節)と言います。 そして、ノードは最大2つの下位ノードを指しているわけですが、これらをと言い、 さらには2つある子同士を区別する為、左の子右の子と言う言い方をします。 ex) 「A」の右の子は「C」、「A」の左の子は「B」。「B」の右の子は「D」、「B」の左の子はいない。 また、あるノードの1つ上にあたるノードを、と言います。 そして、親ノードのない、ツリー階層構造の頂点に当たるノードをルート(root:根)と言います。 ex) 「E」の親は「C」、「F」の親も「C」。「A」は親がいないのでルート。 そして、子を1つも持たないノードの事を、リーフ(葉:leaf)と言います。 ex) 「D」「G」「H」「F」がリーフノードです。 ルートノードでもリーフノードでもないノードを、ブランチ(Branch:枝)と言います。 1つのノードから上方向にさかのぼった際に通過したノードは 先祖(ancestor)、 1つのノードから下方向に下った際に通過したノードは 子孫(descendant)と言います。 ex) 「H」の先祖は「E」「C」「A」。「C」の子孫は「E」「F」「G」「H」。 子孫ノードの最高階層数を深さと言い、自ノードを含む子孫の数を大きさと言います。 ex) このツリーの深さは「3」、大きさは「8」

二分探索木の特徴

(連結リストと比較した場合の)二分探索木の特徴を、表にまとめました。
連結リスト二分探索木
挿入O(N) (*1)O(logN)
検索O(N)O(logN)
削除O(N)O(logN) (*2)
全ノードアクセスO(N)O(N) (*3)
*1 : ソートして挿入させる場合 *2 : 速度は高速だが、アルゴリズムは少々複雑 *3 : ただし、連結リストに比べて二分探索木の方が、ヒープ領域を非常に多く必要とする。 これを見れば分かるとおり、二分探索木は、挿入・検索・削除が高速です。 しかし、アルゴリズムが少々複雑な為、実装に手間がかかる(特に削除機能)点と、 再帰を多用する為、ヒープ領域を非常に多く必要とする点には、注意が必要です。 それでは早速、二分探索木アルゴリズムの詳細 & コードの実装に入っていきます~~♪ 二分探索木 - ノード定義 に続く
         このエントリーをはてなブックマークに追加   


作業効率化・ライフハックのオススメ記事




コンピュータ・テクノロジーのオススメ記事





恋愛・人間関係のオススメ記事




※ 当サイトは、トップページからリンクで辿る事の出来るページに限り、リンクフリーです。
※ 当サイトの閲覧/利用によって生じた如何なる損害も、当サイト管理人は責任を負いません。
※ 当サイトの内容を転載される場合は、当サイトへのリンクをお願い致します。