木構造:C#でLet’sデルゴリ(データ構造とアルゴリズム)

木構造って知ってる気はしていたけど実はちゃんと勉強したことなかったなあって思いました。

概要

グラフの一種。

一から説明するのは大変なのでこちらなどを参考にどうぞ。

ソースコード探検隊 » アルゴリズムとデータ構造 » データ構造 » ツリー

実装

シンプルに実装するとこう

ノードは親と子たちの参照とデータを持つ。

こうやってみると連結リストに似てますね。

親を持たない場合もあるらしいです。

種類いろいろ

一口に木構造と言ってもいろいろと種類があります。

形の部

まずは形の種類

二分木

子が最大で二つの木。

つまり普通に木といった場合子が何個という縛りがない。100個あるかも。

アルゴリズムで木といえばだいたいこれなイメージ。

二分平衡木

可能な限り高さが小さくなっている二分木。

簡単に言うとバランスの取れている木。

参考サイト

全二分木

すべてのノードが0個か2個の子を持つ二分木。

CompleteBinaryTree(完全二分木)

一番下のノード以外はすべてのノードが満たされている二分木。

一番下は左から詰められていないとダメ。

日本語訳がなぜかPerfectBinaryTree(完全二分木)と同じなのでどっちのことを言っているか注意が必要。

PerfectBinaryTree(完全二分木)

全二分木とCompleteBinaryTreeの両方の条件を満たしたもの。

美しいピラミッド型。

日本語訳がなぜかCompleteBinaryTree(完全二分木)と同じなのでどっちのことを言っているか注意が必要。

値の部

値がどう入っているかの種類

ヒープ(最小ヒープ・最大ヒープ)

「子要素は親要素より常に大きいか等しい(最小ヒープ)、または常に小さいか等しい(最大ヒープ)」という制約のCompleteBinaryTree。

どのノードでも親より子の方が大きい(小さい)値が入っている。

左右の制約はないので左の子ノードと右の子ノードの値はどちらが大きくても小さくてもいい。

たいていの場合単にヒープというだけでヒープ二分木(バイナリヒープ)を表す。

メモリのヒープ領域もヒープって呼ぶ時があるので注意。

二分探索木(binary search tree)

「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」」という制約を持つ二分木。

ヒープに更に左右の制約も足したもの。強い。

よく見る。

トライ木・プレフィックス木

ノードが文字を持っていてなんか単語検索などに使われる木。

難しそうなのでまたの機会に。

こんな感じ。

混同しがちなのでまとめてみたらだいぶスッキリしました。よかったよかった。

ちなみに「にぶんき」だと思ってましたがどうやら「にぶんぎ」のようです。気をつけようね。

以上です。

ではまた。

にほんブログ村 IT技術ブログへ
おすすめ一覧

おすすめのサーバ

ミニバード :初心者向け。安くて簡単でWordPressブログ5個まで作れます。250円。

ロリポップ :初心者向け。250円~使えてお安い。500円のがかなり強くておすすめ。老舗で安心。

Conoha:中級者向け。安くクラウドを使ってみたい人におすすめ。時間定額なのでクラウド破産の心配なし。

おすすめのドメイン会社

スタードメイン ミニバード とセットで管理が楽。ついでにポイントももらえてお得。

名づけてねっと :キャンペーンやってておとく

その他おすすめ

Udemy :ビデオ講座は本当に捗るのでマジでおすすめです。

スポンサーリンク

コメントをどうぞ

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