ツリー

スポンサーリンク
スポンサーリンク
ライフスタイル関連のコンテンツ
お金 | 仕事 | 勉強 | プライベート | 健康 |
プログラミング関連のコンテンツ
C言語/C++入門 | Ruby入門 | Python入門 | プログラミング全般

リンクリストの場合、要素を検索したり追加する際に、目的とする要素を1つずつ確認する必要があるため時間がかかります。
ツリーというデータ型を使用すると、比較の回数を減らせ速度アップとなります。

スポンサーリンク

ツリーはノードから構成され、先頭のノードがルートノード、ルートノード(根)から枝分かれしていくノードをリーフノード(葉)と言います。
バイナリツリー(2分木)のデータ構造は、ルートノードから左方向と右方向へと枝が2つに分岐する構造です。

参考:3. バイナリーツリー

各ノードは、左方向の枝をポイントする左ポインタと、右方向の枝をポイントする右ポインタという2つのポインタを持ちます。

class tree {
private:
    // ツリーの基本ノード
    class node {
    private:
        node *right;    // 右方向の枝
        node *left;        // 左方向の枝
    public:
        std::string word;    // このノードの単語
 
        friend class tree;
    };
 
    // ツリーの先頭
    node *root;
 
    // コンストラクタ
    tree() {root = NULL;}
    
    // その他のメンバ
};

バイナリツリーのデータ構造は、上記のようなクラスで表せます。
右方向には、ノードの数字や文字列と比較して、大きいものを格納していく。
左方向には、小さいものを格納していく。
扱う要素とノードに格納されたものの大小を比べることで、検索範囲を大幅に減らせるので、スピードが早いデータ構造となります。

ツリーは、2分岐のバイナリーツリーでなければならないわけではありません。
分岐する枝は何本でも良いですが、複雑なデータ構造となっていきます。
裏を返せば、複雑な構造のデータを扱うことができると言えます。

スポンサーリンク
 
スポンサーリンク