【G検定まとめ】要点整理&当日用カンペの項目別詳解ページです。

詳細な知識や実装は試験には必ずしも必須ではありませんが、試験対策として理解を深めたい方はぜひ最後までご覧ください。

G検定まとめはこちら

探索木

計算機科学において特定のキーを特定するために使用される木構造のことで、学習結果を木構造で表現できるため解釈性が高い。場合分けを続けていけばいつか目的の条件に合致するという考え方に基づく。不純度が最も減少(情報利得が最も増加)するようにデータを振り分けることを繰り返す。不純度とはクラスの混ざり具合を表す指標でジニ係数やエントロピーがある。バギングを組み合わせた手法をランダムフォレストという。探索方法は大別すると以下の通りとなる。

検索木は、情報を効率的に検索および取得できるように、データを階層的に編成および格納するためにコンピュータ サイエンスで使用されるデータ構造です。ツリーの各ノードはデータ項目を表し、各ノードには 0 個以上の子があり、ノード間に親子関係が形成されます。ツリーは通常、ルート ノードが階層の最上位ノードであり、ノードの子がそのノードの親によって表されるデータのサブカテゴリまたはサブ項目を表すように編成されます。

検索木の構造により、バイナリ検索や深さ優先検索などの効率的な検索アルゴリズムが可能になります。検索ツリーでは、検索アルゴリズムが検索に関係のないツリーの大部分をすばやく除外できるようにデータが編成され、検索する必要があるデータの量が削減され、検索プロセスが高速化されます。

探索木には、二分探索木・三分探索木・B木・a-b木など、いくつかの種類があります。

以下は二分探索木のイメージ図です。

幅優先探索

出発点に近いノード(探索木の各要素)順に検索する。出発点から遠いノードほど検索は後回しになる。最短距離でゴールにたどり着く解を見つけることができる。
探索の途中で立ち寄ったノードをすべて記憶しておく必要がありメモリが多く必要となる。

木構造にある各ノードを1度だけ訪問することを探索(走査)と呼び、全探索の代表例として、深さ優先探索(DFS)と幅優先探索(BFS)があります。

幅優先探索は、深さごとに浅い順かつ左側から探索していく方式です。

最短距離でゴールにたどり着く解を見つけやすくなりますが、探索の途中で立ち寄ったノードをすべて記憶しておく必要がありメモリが多く必要となります。

深さ優先探索

あるノードから行けるところまで行って、行き止まりになったら1つ手前のノードに戻って探索を行うということを繰り返す。1つ手前のノードに戻って探索するため大きなメモリは要らない。
最短距離でゴールにたどり着く解であるとは限らない(運次第)。「縦型探索」とも呼ばれる。

深さ優先探索は、行きがけ順(先行順 / 前順 / preorder)、通りがけ順(中間順 / 間順 / inorder)、帰りがけ順(後行順 / 後順 / postorder)の3つに分類することができます。

以下の図は行きがけ順の例となります。

その他の探索木

二分探索木: BST は、ノードの左側のサブツリーの各ノードの値がノードの値より小さく、右側のサブツリーの各ノードの値がノードの値より大きいツリーです。BST は、ソートされたリスト内の値を効率的に検索するために使用されます。BST で値を検索するには、平均で O(log n) 時間がかかります。ここで、n はツリー内のノードの数です。

バランス探索木: バランス探索木は、ツリーの高さがツリーに格納されている要素数の対数になるようにバランス プロパティを維持する検索ツリーの一種です。このプロパティにより、BST と比較して検索、挿入、および削除操作が高速になります。BST では、ツリーの高さが格納された要素の数に比例するため、操作が遅くなる可能性があります。バランス検索木の例には、AVL木、Red-Black木、および B木が含まれます。

AVL木: AVL木は自己均衡二分探索ツリーです。任意のノードの左右のサブツリーの高さの差を最大 1 に維持することで、バランスを確保します。このプロパティにより、ツリーの高さが、ツリーに格納されている要素の数の対数になることが保証されます。

赤黒木: 赤黒木は、別の種類の自己平衡二分探索木です。ツリーのノードを赤または黒に色付けすることでバランスを維持し、ツリーが特定のプロパティ (ルートからリーフ ノードへのすべてのパスの黒いノードの数が同じであるなど) を満たすようにします。

B木: B木は、ディスクベースのデータ ストレージ システムに使用される一種の平衡検索ツリーです。二分探索木とは異なり、B木では複数のキーと値を各ノードに格納できます。これにより、値を見つけるために必要なディスク アクセスの回数を減らすことができるため、B木は大規模なデータセットに特に役立ちます。

G検定学習法

最後までご覧いただきありがとうございました。

当サイトではG検定に役立つ情報をまとめています。

ぜひご覧ください。

本サイトの活用方法

①G検定の概要と試験のポイント

「G検定の概要と試験のポイント」について紹介します。

Read more
②シラバスでみるG検定の試験内容

「G検定の試験内容」について紹介します。

Read more
③G検定合格体験記 〜学習方法と受験体験〜

学習方法と受験当日について紹介します。

Read more
④要点整理&当日用カンペ

G検定の要点をシラバスから抜粋してまとめました。
これから学習する方も、復習したい方にもお使いいただけます。
試験当日用のG検定カンニングペーパーとしてもお役立てください。

Read more

参考書籍

教科書として使用する書籍

体系的に知識を整理することができます。

まずは、この1冊を読んでG検定の学習を進めましょう。

検索機能が使用できるので、Kindle版が特におすすめです。

②問題集として使用する書籍

ある程度学習が進んだら、本番を意識して問題集に取り組みましょう。

本番の試験環境を意識して、このページ「要点整理&当日用カンペ」を使用しながら解答してみましょう。

よろしければおすすめ書籍もご覧ください。 ※これ以降は広告です