Extend binary trees to search neighbors

[nnseva]

One task frequently appears in the binary tree: search neighbors of non-existent key. The following code implements such algorithm for the BinarySearchTree:

(file extend_binary_tree.js)

var dsjslib = require('dsjslib');

dsjslib.BinarySearchTree.prototype.getNeighbors = function (key) {
        if (typeof key === 'undefined' || key === null)return null;
        var node = this.root;
        var compFn = this._compFn;
        var that = this;
        return recFind(key, node);
        function recFind(key, node) {
            if (!node) {
                return null;
            }
            var comp = compFn(node, key);
            if( comp === 0 ) return [{key : node.key, value : node.value}];
            if (comp === -1 && node.leftChild) return recFind(key, node.leftChild);
            if (comp === 1 && node.rightChild) return recFind(key, node.rightChild);
            var ret = [
                {key : node.key, value : node.value}
            ];
            var neighbor = null;
            if(comp === -1) neighbor = that.predecessor(node.key);
            if(comp ===  1) neighbor = that.successor(node.key);
            if( neighbor )
                ret.push(
                    {key : neighbor.key, value : neighbor.value}
                );
            return ret;
        }
};

some test cases are present below:

var _ = require("underscore");
var dsjslib = require('dsjslib');
var assert = require("assert");
var extend_binary_tree = require("./extend_binary_tree.js");

var test = new dsjslib.AVLTree();

var c1 = {id:'c1'}
var c2 = {id:'c2'}
var c5 = {id:'c5'}

test
    .put(c1.id,c1)
    .put(c2.id,c2)
    .put(c5.id,c5)

for(var i=10; i < 100; i++) {
    test.put('c1'+i,{id:'c1'+i});
}

//console.log("DEBUG:",test);

// to the left returns the only one leftmost node
assert.deepEqual(test.getNeighbors('c0'),[{key:'c1',value:{id:'c1'}}]);

// if found, returns the only one found node
assert.deepEqual(test.getNeighbors('c1'),[{key:'c1',value:{id:'c1'}}]);
assert.deepEqual(test.getNeighbors('c2'),[{key:'c2',value:{id:'c2'}}]);

// in the middle returns two nodes, to the left and to the right of non-existent key
assert.equal(test.getNeighbors('c3').length,2);
assert.deepEqual(_.findWhere(test.getNeighbors('c3'),{key:'c2'}),{key:'c2',value:{id:'c2'}});
assert.deepEqual(_.findWhere(test.getNeighbors('c3'),{key:'c5'}),{key:'c5',value:{id:'c5'}});

assert.equal(test.getNeighbors('c4').length,2);
assert.deepEqual(_.findWhere(test.getNeighbors('c4'),{key:'c2'}),{key:'c2',value:{id:'c2'}});
assert.deepEqual(_.findWhere(test.getNeighbors('c4'),{key:'c5'}),{key:'c5',value:{id:'c5'}});

// if found, returns the only one found node
assert.deepEqual(test.getNeighbors('c5'),[{key:'c5',value:{id:'c5'}}]);

// to the right returns the only one rightmost node
assert.deepEqual(test.getNeighbors('c6'),[{key:'c5',value:{id:'c5'}}]);

// check working between deep nodes
for(var i=10; i < 99; i++) {
    assert.deepEqual(_.findWhere(test.getNeighbors('c1'+i+'1'),{key:'c1'+i}),{key:'c1'+i,value:{id:'c1'+i}});
    assert.deepEqual(_.findWhere(test.getNeighbors('c1'+i+'1'),{key:'c1'+(i+1)}),{key:'c1'+(i+1),value:{id:'c1'+(i+1)}});
}

The same might be implemented for other types of tree

UPD: fixed algorithm and testcases have been extended

[nnseva]

fixed algorithm and testcases have been extended

[monmohan]

thanks for the feedback. I will take a look. Regards Monmohan

On Sat, Jan 3, 2015 at 10:09 PM, Vsevolod Novikov notifications@github.com wrote:

fixed algorithm and testcases have been extended

— Reply to this email directly or view it on GitHub https://github.com/monmohan/dsjslib/issues/9#issuecomment-68596007.

[akloeber]

+1