木構造早わかり集 http://els.ai-plus.com/ 木構造の基本ルール 木構造の一番上の節点を、 根（ルート）という 根 節点 葉 http://els.ai-plus.com ○印を節点（ノード）と いい、ここにデータが 入っている 節点 葉 葉 これ以上先がない節点を、 葉（リーフ）という • データの入っている ○印の部分が、節 点（ノード） • 頂上にある節点のこ とを、根（ルート）と 呼ぶ • これ以上先がない節 点のことを、葉（リー フ）と呼ぶ 2分木 • 根（ルート）や節点（ノード）が、3本以上に分 岐しない木構造 根や節点からの 分岐が1本か2本 根 2分木でない例 根 節点 節点 節点 葉 葉 葉 葉 こんな形であれば、すべて2分木 http://els.ai-plus.com 節点 葉 葉 葉 一つの節点から3つ分岐している ので、2分木とはいわない 2分探索木 • 2分木の一種 • 左へ分岐すると小さい値、右へ分岐すると大 きい値が入っている 28を探索する例（スライドショー参照） 26は、32より 小さい 32 26 45は、32より 大きい 45 根から探索開始 28は、32より小さ いので左へ 32 26 17 28 50 28は、26より大きい 17は、26より小さい http://els.ai-plus.com 45 50は、45より大きい 17 28は、26より大 きいので右へ 28 50 上から順にたどれば、 目的の値に到着 完全2分木 • 2分木の一種 • 分岐が必ず2本で、深さがすべて同じ 完全2分木でない例 根 根 節点 葉 節点 葉 葉 節点 葉 根や節点から、必ず2本に分岐 http://els.ai-plus.com 葉 節点 葉 葉 1本しか分岐していない節点がある ので、完全2分木とはいわない バランス木 • 完全2分木が理想的な形だが、節点の数が 2n-1個でないといけないので、現実的にはか なり作りにくい • そこで、なるべく左右のバランスが良くなるよ う、節点の位置を調節した木 • バランスの取り方によって、完全バランス木、 AVL木、B木がある http://els.ai-plus.com 完全バランス木 • バランス木の一種 • 左右の節点の個数の差が1個以下 正しい完全バランス木の例 1個 1個 1個 1個 3個 3個 7個 完全バランス木ではない例 1個 1個 3個 1個 2個 6個 どの節点から数えても、左右の節点の 個数の差が0、または1個 http://els.ai-plus.com 1個 1個 1個 1個 3個 3個 7個 1個 1個 2個 2個 5個 1つでも左右の節点の個数の差が2個 以上なら、完全バランス木とは呼ばな い AVL木 • バランス木の一種 • 左右の節点の深さの差が1以下 正しいAVL木の例 AVL木ではない例 根からの 根からの 深さ1 深さ1 根からの 深さ2 深さの差 1 根からの 深さ3 どの節点から数えても、根に到達する までの節点の個数（深さ）の差が0、ま たは1個 http://els.ai-plus.com 深さの 差2 根からの 深さ2 根からの 深さ3 1つでも深さの差が2個以上なら、AVL 木とは呼ばない B木 • バランス木の一種 • 左右の節点の深さが同じ 正しいB木の例 B木ではない例 根からの 根からの 深さ1 深さ1 根からの 根からの 深さ2 深さ2 根からの 根からの 深さ3 深さ3 どの節点から数えても、根に到達する までの節点の個数（深さ）が同じ http://els.ai-plus.com 深さが異なる部分があれば、B木とは 呼ばない ヒープ木 • 親節点の値は、どの子節点よりも大きい • 根（ルート）が、最大値 データの追加（スライドショー参照） 50 50が最大値 32は、17や26 より大きい 50 32 17 http://els.ai-plus.com 45は、28より 大きい 17 45 26 32 28 45 26 28 55 親節点のほうが小さければ、入れ替え
© Copyright 2024 ExpyDoc
