JavaScriptで2分探索木

JavaScriptで双方向連結リストと似たような感じで書いてみる。
毎度のことながら、まだまだ初心者なので、アドバイス等いただけると喜びます。

JavaScriptの勉強中なので書いてみる(2)

2分探索木 - Wikipedia
これ見ながらやってました。
あぁ、なんとかできた。
ルートノードを削除した時にいろいろ起きて最終的にごちゃごちゃしてしまいました。

Treeオブジェクト概要

property
root	ルートのノードを保持します
numOfNode	ノードの数を保持します

method
insert(value, node)	valueにツリーに挿入したい値(nodeは使わない)
find(value)	valueを探索し、そのノードを返す
remove(value)	valueを削除します
forEach(func, node)	node以下の値を照準で列挙します nodeを指定しなければルートから探索
getBiggestNode(node)	node以下のノードから最大の値を持つノードを返します nodeを指定しなければルートから
getSmallestNode(node)	node以下のノードから最小の値を持つノードを返します nodeを指定しなければルートから

利用例

数値でしか試してません

var Tree = new Tree();

// 適当に挿入
Tree.insert(50);
Tree.insert(9);
Tree.insert(60);
Tree.insert(12);
Tree.insert(5);
Tree.insert(15);
Tree.insert(8);
Tree.insert(2);
Tree.insert(6);
Tree.insert(70);

/*
            50
          /   \
        9      60
      /   \     \
    5      12    70
  /  \      \
2     8      15
    /
  6 
*/

// 探索
Tree.find(15);  // TreeNode {value:15,leftNode:null,rightNode:null}

Tree.find(999); // null

// 昇順に列挙
Tree.forEach(function(value){
    console.log(value);     // 2, 5, 6, 8, 9, 12, 15, 50, 60, 70
});

// 削除 (50はルートノード)
Tree.remove(9)
/*
削除する9の場所に8、8の場所に6
            50
          /   \
        8      60
      /   \     \
    5      12    70
  /  \      \
2     6      15
*/

Tree.remove(50);
/*
削除する50(ルート)の場所に15
            15
          /   \
        8      60
      /   \     \
    5      12    70
  /  \
2     6
*/

Tree.insert(100);
Tree.insert(51);
/*
            15
          /    \
        8        60
      /   \     /   \
    5      12  51    70
  /  \                 \
2     6                 100
*/

Tree.forEach(function(value){
    console.log(value);     // 2, 5, 6, 8, 12, 15, 51, 60, 70, 100
});

// 最大値の取得
Tree.getBiggestNode();      // {value: 100, leftNode: null, rightNode: null}

var startNode = Tree.find(8);
Tree.getBiggestNode(startNode);
// {value: 12, leftNode: null, rightNode: null}

なんとか普通に使えます。
妙なことするとすぐに壊れます。

ソース

もっと綺麗に書きたい。
今現在、昇順列挙しかありませんが、forEachメソッドのleftNode,rightNodeを入れ替えれば降順列挙になります。

/**
*JavaScriptでツリー構造
*/
var Tree = function(){
    // ルートノード
    this.root = null;

    // 探索時に親ノードの場所を示す
    this.parentNode = null;
    this.direction = null;

    // ルートノードの上に存在するダミーノード
    this.dummy = new TreeNode(null);

    // ノードの数を保持します
    this.numOfNode = 0;
}
Tree.prototype = {
    /**
    *Tree.insert(value, node)
    *   ツリーにデータを追加します
    *@param {Object} value
    *@param {Node}   node 
    */
    insert: function(value, node){
        // 最初はルートに追加
        if(!this.root){
            this.root = new TreeNode(value);
            this.dummy.leftNode = this.root;
            this.dummy.rightNode = this.root;

            this.numOfNode++;

            return;
        }

        // nodeがnullであれば最初の探索
        node = node || this.root;

        // ノードの値より小さければ左、大きければ右
        if(node.value > value){
            nodeCheck.call(this, node, 'leftNode');
        } else {
            nodeCheck.call(this, node, 'rightNode');
        }

        /**
        *nodeCheck(node, nodeName)
        *   探索の処理をまとめた関数
        */
        function nodeCheck(node, nodeName){
            if(node[nodeName] === null){
                node[nodeName] = new TreeNode(value);
                this.numOfNode++;
            } else {
                this.insert(value, node[nodeName]);
            }
        }
    },
    /**
    *Tree.find(value, node)
    *   ツリーのデータを探索します
    *@param {object Object} value
    *@param {object Node}   node 
    */
    find: function(value, node){

        // ノードが指定されていなければルートから
        node = node || this.root;

        // ノードの値より小さければ左ノード、大きければ右ノードを再探索
        // 探索ノードがこれ以上ない場合はnullが返ってきます
        if(node.value > value){
            node = nodeSearch.call(this, node, 'leftNode');
        } else if(node.value < value) {
            node = nodeSearch.call(this, node, 'rightNode');
        }

        /**
        *nodeSearch(node, nodeName)
        *   探索の処理をまとめた関数
        */
        function nodeSearch(node, nodeName){
            // 探索すべきノードは存在するのか
            // 存在しなければ、値は見つからなかった
            if(node[nodeName] === null){
                return null;
            } else {
                // 再帰で再探索
                this.parentNode = node;
                this.direction  = nodeName;
                return this.find(value, node[nodeName]);
            }
        }

        // 大きくも小さくもなければ、その値が見つかった
        return node;
    },
    /**
    *Tree.remove(value)
    *   ツリーのデータを削除し、再構成します
    *@param {object Object} value
    */
    remove: function(value){

        // 削除対象のノードを探索する
        var node = this.find(value, this.root);

        // なければ終了
        if(!node){
            return;
        }
        if(this.dummy.leftNode === node){
            this.parentNode = this.dummy;
            this.direction = 'leftNode';
        }

        // ノードの削除と再構成
        if(node.isLeaf()){
            // そのノードが葉であれば、そのまま削除
            delete this.parentNode[this.direction];
            rootCheck.call(this,this.parentNode);

        } else if(node.leftNode && !node.rightNode){
            // 子ノードが一本ならそのまま置き換え
            this.parentNode[this.direction] = node.leftNode;
            rootCheck.call(this,node.leftNode);

        } else if(!node.leftNode && node.rightNode){
            // 子ノードが一本ならそのまま置き換え
            this.parentNode[this.direction] = node.rightNode;
            rootCheck.call(this,node.rightNode);

        } else {
            // 子ノードが２つあるといろいろ大変
            // 削除ノードの左のノードの中から最大値を探索
            var maxNode = this.getBiggestNode(node.leftNode);

            // 最大値ノードの位置にターゲットノードの左を設定しておく
            if(maxNode.parentNode.rightNode){
                maxNode.parentNode.rightNode = maxNode.leftNode;
            } else {
                // 参照を削除
                delete maxNode.parentNode.rightNode;
            }

            // 削除対象のノードと最大値ノードを入れ替え
            this.parentNode[this.direction] = maxNode;
            maxNode.leftNode = node.leftNode;
            maxNode.rightNode = node.rightNode;

            rootCheck.call(this,node);

            // 親の参照を削除
            delete maxNode.parentNode;
        }

        this.numOfNode--;
        this.parentNode = null;
        this.direction = null;

        // ダミーノードが引数のノードを示していたらルートノード
        function rootCheck(node){
            if(this.dummy.leftNode === node){
                this.root = node;
            }
        }
    },
    /**
    *Tree.forEach(func);
    *   引数のノード以下のノードを昇順で探索します
    *@param {object Function} func(value)
    *@param {object Node}     node
    */
    forEach: function(func, node){
        // 探索の初期ノードが選択されていなければルートノード
        node = node || this.root;

        //  左側を再帰的に探索
        if(node.leftNode){
            this.forEach(func, node.leftNode);
        }
        // 左ノードがなければ値を引数として与えられた関数に渡す
        func(node.value);

        // 右側を再帰的に探索
        if(node.rightNode){
            this.forEach(func, node.rightNode);
        }
    },
    /***
    *Tree.getBiggestNode(node)
    *   引数のノード以下の最大のノードを探索
    *@param  {object Node} node
    *@param  {object Node} parentNode
    *@return {object Object}  {node: node, parentNode: parentNode}
    */
    getBiggestNode: function(node, parentNode){
        node = node || this.root;
        if(node.rightNode){
            return this.getBiggestNode(node.rightNode, node);
        } else {
            node.parentNode = parentNode;
            return node;
        }
    },
    /***
    *Tree.getSmallestNode(node)
    *   引数のノード以下の最小のノードを探索
    *@param  {object Node} node
    *@param  {object Node} parentNode
    *@return {object Object}  {node: node, parentNode: parentNode}
    */
    getSmallestNode: function(node, parentNode){
        node = node || this.root;
        if(node.leftNode){
            return this.getSmallestNode(node.leftNode, node);
        } else {
            node.parentNode = parentNode;
            return node;
        }
    }
}

// １つ分のノード
var TreeNode = function(value){
    this.value = value;
}
TreeNode.prototype = {
    leftNode: null,
    rightNode: null,
    /**
    *Node.isLeaf();
    *   自身が葉であるかを返します
    *@return {Boolean} 真偽値
    */
    isLeaf: function(){
        return !this.leftNode && !this.rightNode ;
    }
}

最後に

JavaScriptの MV* についての本とか読んでみたいです。