スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

マルチパラダイム時代におけるデータ構造 第22回 ー 方向がある木。指向木(根付き木)

 この記事は、「マルチパラダイム時代におけるデータ構造 第21回 ー 自由な木とグラフは本当に閉じているのか問題」の続きです。前回は、自由木について解説しました。今回は、指向木(根付き木)について解説します。
 今まで紹介してきた木構造は、向きがありませんでした。しかしながら、方向がわかると便利な場面が多々あります。そんなときに使用するデータ構造が、指向木(根付き木)です。指向木を使用すれば、データに順番を持たせられます
 指向木は自由木とは違い、親子関係があります。ここでいうところの親とは、前にあるデータであり、子は後にあるデータです。また、データの代表(頂点)であるルートノードがあります。それで指向木は根付き木とも呼ばれています。
 より詳しく書くと、自由木に最終地点であるルートノードを設定することにより、閉路を生まないようにするのが指向木です。もちろん、ルートノードは、誰の子にもなりません。全てのデータの親となります。なぜ閉路にならないのかというと、最終地点であるルートノードは誰の子にもならないからです。といっても、完全に閉路が存在しないというのではなく、閉路にならないルートノードへ向かう道が必ずあるという意味です。ルートノードへの有向経路の存在は、無限ループを生まない手段になるのでその意義は大きいです。
 それでは、指向木を実装しましょう♪指向木を実装する際に注意するべきなのは、向きを表すために、親子の設定が必要だという点と、ルートノードの設定が必要だという点です。その点に注意すれば、それほど難しくありません。参考のために、簡潔な実装例を掲載します。

using System;

namespace DataStructure
{
    //方向(根)がある自由木。指向木/根付き木。
    public class RootedTree<T> : FreeTree<T>
    {
        //ルートノードか否か。
        private bool _isRoot;
        public bool IsRoot
        {
            get { return this._isRoot; }
        }

        //ルートノード。
        private RootedTree<T> _root;
        public RootedTree<T> Root
        {
            get { return this._root; }
        }

        //子
        private IDataFreeManager<RootedTree<T>> _child;
        public IDataFreeManager<RootedTree<T>> Child
        {
            get { return this._child; }
            protected set
            {
                this._child = value;
            }
        }

        //親
        private IDataFreeManager<RootedTree<T>> _parent;
        public IDataFreeManager<RootedTree<T>> Parent
        {
            get { return _parent; }
            protected set { this._parent = value; }
        }

        //繋がっているノード。
        public override IDataFreeManager<Graph<T>> Node
        {
            get
            {
                var result = new ConsCell<Graph<T>>();
                if ( this.Child != null ) {
                    for ( int i = 0 ; i < this.Parent.Count ; ++i )
                        result.Insert( this.Parent.Select( i ) );
                    for ( int i = 0 ; i < this.Child.Count ; ++i )
                        result.Insert( this.Child.Select( i ) );
                }
                return ( IDataFreeManager<Graph<T>> ) result;
            }
            protected set
            {
                base.Node = value;
            }
        }

        //繋がっていノードの数。
        public override int Count
        {
            get
            {
                return
                    this.Parent.Count +
                    this.Child.Count;
            }
        }

        //値を指定してルートノードのインスタンスを生成する。
        public RootedTree( T value )
            : base( value )
        {
            this._isRoot = true;
            this._root = null; //自身がルートの時はnull
            this._parent = new ConsCell<RootedTree<T>>();
            this._child = new ConsCell<RootedTree<T>>();
        }

        //ノードの値と識別子および、
        //隣接ノードを指定してインスタンスを生成する。
        protected RootedTree(
            T value,
            int id,
            Graph<T> next,
            RootedTree<T> root )
            : base( value, id, next )
        {
            this._root = root;
            this._parent = new ConsCell<RootedTree<T>>();
            this._parent.Insert(
                ( RootedTree<T> ) next );
            this._child = new ConsCell<RootedTree<T>>();
        }

        //ルートノードを取得する。
        private RootedTree<T> GetRoot( )
        {
            return this.Root == null ?
                this : this.Root;
        }

        //値を発生させる。
        public override void Insert( T value )
        {
            var newNode = new RootedTree<T>(
                        value,
                        this.ID + 1,
                        this,
                        this.GetRoot() );
            this.Child.Insert( newNode );
            if ( newNode.HasClosed() )
                throw new ArgumentException(
                    "閉路を生む値は指定できません。" );
        }

        //任意の位置へ値を発生させる。
        public override void Insert( T value, int index )
        {
            var newNode = new RootedTree<T>(
                        value,
                        this.ID + 1,
                        this,
                        this.GetRoot() );
            this.Child.Insert( newNode );
            if ( newNode.HasClosed() )
                throw new ArgumentException(
                    "閉路を生む値は指定できません。" );
        }

        //隣接ノードを消滅する。
        public override void Delete( )
        {
            this.Child.Delete();
        }

        //任意の位置の隣接ノードを消滅する。
        public override void Delete( int index )
        {
            this.Child.Delete( index );
        }
    }
}

別段難しいプログラムはないと思います。テストについては、自由木と同様のものを用意すればよいと思います。より完全なテストをしたい時には、ルートノードのテストをするとよいと思います。

//ルートプロパティをテストする。
private void RootTest( )
{
    int init = 0;
    int value = init;
    RootedTree g = new RootedTree<int>( value++ );
    g.Insert( value++ );
    var n1 =  (RootedTree) g.GetNode( 0 );
    if ( n1.Root.ID != 0 )
        throw new TestException(
            "RootTest",
            "ルートの設定が間違っています。" );
    n1.Insert( value++ );
    var n2 = ( RootedTree ) n1.GetNode( 1 );
    if ( n2.Root.ID != 0 )
        throw new TestException(
            "RootTest",
            "ルートの設定が間違っています。" );
}

また、子の実装はあくまでも学習用の簡潔なものですので、本格的に実装するときは、より多くのユーザーストーリーをテストとして実装します。そうすれば、特殊な状況にも耐えられる指向木が得られます。
 指向木も役に立つのですが、プログラミングでよく使用するのは、派生した木です。次回、より使用頻度が高い木構造について解説します。お楽しみに♪  
スポンサーサイト

テーマ : プログラミング
ジャンル : コンピュータ

トラックバック


この記事にトラックバックする(FC2ブログユーザー)

-

管理人の承認後に表示されます

コメントの投稿

非公開コメント

プロフィール

インドリ

Author:インドリ
みなさん、はじめまして、
コンニチハ。

ボクは、無限の夢(infinity dream)を持つネタ好きな虹色の鳥インドリ(in dre)です。
色々な情報処理技術を啄ばむから楽しみにしてね。

http://twitter.com/indori
は別人による嫌がらせ行為です。
私とは関係ないので注意して下さい。
次はなりすましブログなどをするかもしれませんが、ここ以外でブログをするつもりがないので、ここ以外にインドリのブログがあったとしても無視してください。


何度言っても分からない人がいるので、ここにコメント欄へ書き込むときの注意事項を書きます。


一、社会人としてのマナーをわきまえましょう。
一、妄想に基づく書き込みを止めてください。
一、暴言の類は書かないで下さい。
一、某誹謗中傷サイトの書き込みは彼らの妄想に基づく書き込みですから無視して、ここへ書き込まないで下さい。
一、コメント書く前に他のコメントよく読んでから行って下さい。
一、言いがかかり等の行為を禁止します。
一、その他常識的に考えて迷惑なコメントはしないで下さい。


以上のルールを守れない人のコメントは削除します。



利用上の注意
ここに紹介してある文章およびプログラムコードは正確であるように心がけておりますが、内容を保証するものではありません。当サイトの内容によって生じた損害については、一切の責任を負いませんので御了承ください。


執筆したCodeZineの記事


【VB.NETで仮想CPUを作ろう】

  1. VB.NETで仮想CPUを作ろう
  2. レジスタの実装
  3. 仮想CPUのGUI化
  4. テストドライバの改良
  5. CPUの基礎動作の実装
  6. MOV命令の実装
  7. ADD命令実装
  8. SUB命令実装
  9. INC命令&DEC命令の実装と命令長
  10. MLU命令の実装とModR/Mについて
  11. DIV命令の実装とイベント設計について
  12. 機械語駆動式 関数電卓を作ろう!
  13. 機械語駆動式 関数電卓を作ろう! 解答編(前半)
  14. 機械語駆動式 関数電卓を作ろう! 解答編(後半)


【仮想ネットワーク実装でTCP/IPを学ぼう】
  1. TCP/IPの基礎と勘所
  2. ネットワークアクセス層の勘所
  3. インターネット層の勘所
  4. トランスポート層の勘所
  5. アプリケーション層の勘所
  6. セキュリティの基礎と仮想ネットワークの仕様
  7. GDI+と独自プロトコルの定義



【並列化】
インテル Parallel Studioを使って並列化プログラミングを試してみた
並列プログラミングの効率的なデバッグを実現する「Parallel Inspector」


【TBBシリーズ】
  1. インテル スレッディング・ビルディング・ブロックの概要
  2. インテルTBBから学ぶループの並列化
  3. スレッドセーフとインテルTBBのコンテナ
  4. インテルTBBのスレッドクラス


【OpenMPシリーズ】
  1. OpenMPの基礎構文
  2. OpenMPの実行時ライブラリと並列ループ
  3. OpenMPのメモリモデルとfork- joinモデル

最近の記事
最近のコメント
月別アーカイブ
カテゴリ
Ada (9)
COBOL (5)
C (9)
C++ (11)
C# (370)
D (25)
Java (8)
Perl (1)
Ruby (14)
PHP (2)
Boo (2)
Cobra (2)
LISP (6)
F# (33)
HTML (0)
XHTML (0)
CSS (0)
XML (0)
XSLT (0)
Scala (4)
WPF (0)
WF (2)
WCF (0)
LINQ (4)
MONO (5)
Linux (0)
MySQL (0)
ブログ内検索
リンク
最近のトラックバック
RSSフィード
ブロとも申請フォーム

この人とブロともになる

QRコード
FC2カウンター
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。