木構造って知ってる気はしていたけど実はちゃんと勉強したことなかったなあって思いました。
目次
概要#
グラフの一種。
一から説明するのは大変なのでこちらなどを参考にどうぞ。
ソースコード探検隊 » アルゴリズムとデータ構造 » データ構造 » ツリー
実装#
シンプルに実装するとこう
public class Tree
{
Node root;
public class Node{
Node parent;
Node[] children;
int value;
}
}ノードは親と子たちの参照とデータを持つ。
こうやってみると連結リストに似てますね。
親を持たない場合もあるらしいです。
種類いろいろ#
一口に木構造と言ってもいろいろと種類があります。
形の部#
まずは形の種類
二分木#
子が最大で二つの木。
つまり普通に木といった場合子が何個という縛りがない。100個あるかも。
アルゴリズムで木といえばだいたいこれなイメージ。
二分平衡木#
可能な限り高さが小さくなっている二分木。
簡単に言うとバランスの取れている木。
全二分木#
すべてのノードが0個か2個の子を持つ二分木。
CompleteBinaryTree（完全二分木）#
一番下のノード以外はすべてのノードが満たされている二分木。
一番下は左から詰められていないとダメ。
日本語訳がなぜかPerfectBinaryTree（完全二分木）と同じなのでどっちのことを言っているか注意が必要。
PerfectBinaryTree（完全二分木）#
全二分木とCompleteBinaryTreeの両方の条件を満たしたもの。
美しいピラミッド型。
日本語訳がなぜかCompleteBinaryTree（完全二分木）と同じなのでどっちのことを言っているか注意が必要。
値の部#
値がどう入っているかの種類
ヒープ（最小ヒープ・最大ヒープ）#
「子要素は親要素より常に大きいか等しい（最小ヒープ）、または常に小さいか等しい（最大ヒープ）」という制約のCompleteBinaryTree。
どのノードでも親より子の方が大きい（小さい）値が入っている。
左右の制約はないので左の子ノードと右の子ノードの値はどちらが大きくても小さくてもいい。
たいていの場合単にヒープというだけでヒープ二分木（バイナリヒープ）を表す。
メモリのヒープ領域もヒープって呼ぶ時があるので注意。
二分探索木（binary search tree）#
「左の子孫の値 ≤ 親の値 ≤ 右の子孫の値」」という制約を持つ二分木。
ヒープに更に左右の制約も足したもの。強い。
よく見る。
トライ木・プレフィックス木#
ノードが文字を持っていてなんか単語検索などに使われる木。
難しそうなのでまたの機会に。
こんな感じ。
混同しがちなのでまとめてみたらだいぶスッキリしました。よかったよかった。
ちなみに「にぶんき」だと思ってましたがどうやら「にぶんぎ」のようです。気をつけようね。
以上です。
ではまた。