lundi 13 février 2012

Binary Tree in JavaScript

Voici une méthode simple permattant de générer un Binary Tree en JScript. Pour l'instant on utilise que des valeurs de type numérique.
L'avantage étant qu'une recherche ne demande plus que n*log(n) plutôt que n*n...

// Simple Binary Tree
// This binary tree is containing a numeric value (or string)
// and is used to optimize search in list.
// Usage:
// tree = new BTree();
// tree.add(value);
//
// BTree.add() Method
// add a new value in the tree (if value is lesser than the current values a new child is created at the left,
// otherwise a new child is created at the right)
// INPUT: value : integer
// OUTPUT: true : if the value has been added (was not existing in the tree)
// false : value already exist in the Tree.

function BTreeNode (value, left, right) {
this._value=value;
this._left=left;
this._right=right;
}
function BTree() {
this.root=null;
this.add=function (value) {
var node;
if (this.root!=null) {
var lastNode=null;
lastNode=this.getNode(value, this.root);
if (lastNode._value==value)
return false; // if exist is not added
node=new BTreeNode(value, null, null);
if (valuenode._value) {
if (node._right!=null)
return this.getNode(value, node._right);
else
return node;
}

}
this.getNode=function (value, node) {
if (node==null)
return null;
if (valuenode._value) {
if (node._right!=null)
return this.getNode(value, node._right);
else
return node;
}

}

}