木構造の基本用語や利用例、二分木・完全二分木・二分探索木・AVL木・B木・木の巡回まで、基本情報技術者試験の午前試験対策に必要な内容を図付きで学べます。
木構造
木構造とは
木構造(きこうぞう)は、さまざまなコンピュータの分野でよく使われています。
例えば、パソコンのフォルダー、やWebサイトのメニューは、親となる項目の下に子となる項目が並ぶ階層構造になっています。このような階層構造を表現するのに適しているのが木構造です。
基本情報技術者試験では、木構造の基本的な仕組みや用語、二分木や二分探索木などの種類、木の巡回方法がよく出題されます。まずは木構造の基本から理解していきましょう。
木構造とは何か
「木」という名前が付いていますが、実際の木とは逆さまの形で表現されることが多く、一番上にあるデータから枝分かれしていくような構造になっています。
配列との違い
配列はデータを横一列に並べて管理しますが、木構造は親子関係で管理します。
木構造の用語
ノード
親と子
他のデータにつながっている上側のノードを「親」、親から下につながっているノードを「子」といいます。
根
木構造の一番上にあるノードを根（Root）といいます。
葉
子を持たないノードを葉といいます。
木の葉が枝の先にあるように、一番末端にあるデータです。
二分木とは
二分木（にぶんぎ）とは、1つの親が持てる子が最大2つまでの木構造です。
二分木の特徴
- 1つの親が持てる子は最大2つ
- 左右の子を区別して管理する
- データを効率よく管理しやすい
この後出てくる二分探索木やAVL木など、多くの木構造の基本となります。
二分探索木とは
二分探索木（にぶんたんさくぎ、Binary Search Tree：BST）とは、二分木のルールに加えて、データの並び方にもルールがある木構造です。
- 左の子には親より小さい値を配置する
- 右の子には親より大きい値を配置する
AVL木とは
AVL木（エーブイエルぎ）は、二分探索木の一種で、左右の部分木の高さの差が大きくならないように自動で調整される木構造です。
下の例のように、左部分木と右部分木の高さの差が2以上となっている場合は、AVL木ではありません。
偏っている部分を移動して、左部分木と右部分木の高さの差が1以下になるようにします。
AVL木では、データを追加したり削除したりしたときに、木の形を自動で整えてバランスを保ちます。そのため、木が大きく偏ることがなく、効率よくデータを検索できます。
B木とは
B木（ビーぎ）は、1つのノードに複数のデータを格納できる木構造です。
- 1つのノードに複数のデータを格納できる
- 左の子には親より小さい値を配置、右の子には親より大きい値を配置する（二分探索木やAVL木と同じ）
- 子ノードには、それぞれ対応する範囲のデータが格納される
- 木の高さが高くなりにくいため、検索を効率よく行える
腕試し（理解テスト）
腕試し（理解テスト）に挑戦する場合はこちらをクリック。
コメント