binaryTree.py

#!/usr/bin/python
# A testing implementation of binary trees
# Very primitive (key = value, no duplicates, only integers)
# http://www.algolist.net/Data_structures/Binary_search_tree/Insertion
# http://stackoverflow.com/questions/2598437/how-to-implement-a-binary-tree-in-

class Node:
    def __init__(self, val):
        self.l = None
        self.r = None
        self.v = val

class Tree:
    def __init__(self):
        self.root = None

    def add(self, value):
        if(self.root == None):
            self.root = Node(value)
        else:
            self.addChild(value, self.root)

    def addChild(self, value, node):
        if(value == node.v):
            print "Duplicate value found, not adding"
        elif(value < node.v):
            if(node.l == None):
                node.l = Node(value)
            else:
                self.addChild(value, node.l)
        elif(value > node.v):
            if(node.r == None):
                node.r = Node(value)
            else:
                self.addChild(value, node.r)

    def walk(self):
        if(self.root != None):
            self.printTree(self.root)

    def printTree(self, node):
        if(node != None):
            self.printTree(node.l)
            print node.v
            self.printTree(node.r)

    # return true if value exists in tree, otherwise false
    # iterative approach as opposed to recursive
    def find(self, value):
        current_node = self.root
        while current_node is not None:
            if(current_node.v == value):
                return True
            elif(value < current_node.v):
                current_node = current_node.l
            else:
                current_node = current_node.r
        return False

tree = Tree()
tree.add(10)
tree.add(9)
tree.add(9)
tree.add(40)
tree.add(11)
tree.add(10)
tree.add(8)
tree.add(13)
tree.add(38)
tree.walk()
print "-------------"
print tree.find(38)
print tree.find(12)
print "-------------"
tree.walk()

binaryTree2.py

#!/usr/bin/python

class Node(object):

    def __init__(self, key, data):
        self.key = key
        self.data = data
        #self.color = 'RED'
        #self.N = 1
        #self.height = 1
        self.left = None
        self.right = None

    def __repr__(self):
        return "Node with Data: %s" % self.data

    def minKey(self, node):
        if(self.left == None):
            return self.key
        else:
            return minKey(self.left)

    def maxKey(self, node):
        if(self.right == None):
            return self.key
        else:
            return maxKey(self.right)

    def find(self, key, node=None):
        if node == None:
            node = self
        if key == node.key:
            return node
        elif key < node.key:
            if node.left == None:
                return None
            else:
                return node.find(key, node.left)
        else:
            if node.right == None:
                return None
            else:
                return node.find(key, node.right)

    def insert(self, key, data):
        if(key < self.key):
            if(self.left == None):
                self.left = Node(key, data)
            else:
                self.left.insert(key, data)
        elif(key > self.key):
            if(self.right == None):
                self.right = Node(key, data)
            else:
                self.right.insert(key, data)


root = Node(4, "fish")
root.insert(5, "dog")
root.insert(1, "cat")
root.insert(40, "dolphin")
root.insert(2, "shark")
print root.find(4)
print root.find(40)
print root.find(2)
print "Syntax OK"

bst.js

// see Robert Sedgewick :: Left-leaning Red-Black Trees

//const RED   = true;
//const BLACK = false;

var Node = function(key, value) {
  this.key    = key;
  this.value  = value;
  //this.color  = RED;
  this.left   = null;
  this.right  = null;
};

// -- helpers

function minKey(node) {
  if (node.left === null) return node.key;
  else return minKey(node.left);
}

function maxKey(node) {
  if (node.right === null) return node.key;
  else return maxKey(node.right);
}

function minNode(node) {
  if (node.left === null) return node;
  else return minNode(node.left);
}

function maxNode(node) {
  if (node.right === null) return node;
  else return maxNode(node.right);
}

// -- search

function getValue(node, key){
  if (node === null) return null;
  if (key === node.key) {
    return node.value;
  }
  if (key < node.key) return getValue(node.left,  key);
  else return getValue(node.right, key);
}

// -- insert

function insert(node, key, value) {
  if (node === null) return new Node(key, value);
  else if (key < node.key) node.left = insert(node.left, key, value);
  else node.right = insert(node.right, key, value);
  return node
}

// -- delete

function remove(node, key) {
  if (node === null) return null;
  // we look at grandchildren, to avoid creating parent pointers, and to maintain downward check logic
  // alas, this duplicates our code, fixit
  if (node && node.left) {
    if (key === node.left.key) node.left = removeChild(node.left);
    if (key < node.key) return remove(node.left, key);
  }
  if (node && node.right ) {
    if (key === node.right.key) node.right = removeChild(node.right);
    else if (key > node.key) return remove(node.right, key);
  }
}

function removeChild(child) {
  // node has no children, just remove reference to it; let GC do the rest
  if (child.left === null && child.right === null) child = null;
  // one child, remove node and promote that child in its place
  else if (child.left === null && child.right) child = child.right
  else if (child.left && child.right === null) child = child.left
  // two children, replace with minimal value in right subtree and remove original min value
  // else could be used, but writing it out explicitly for dev
  else if (child.left && child.right) child = replaceNodeWithTwoChildren(child)
  return child
}

function replaceNodeWithTwoChildren(node) {
  // find smallest value from right subtree of child
  newval = minNode(node.right);
  // create temp pointers for child right and left subtrees
  tmpleft = node.left;
  tmpright = node.right;
  // use remove() to drop found element
  remove(node.right, newval.key);
  // set that element as new value for deleted node
  node = newval
  // restore child pointers
  if (node.left === null) node.left = tmpleft
  if (node.right === null) node.right = tmpright

  return node
}

// --- Main/testing

var T = new Node(13, 'mermaid')
insert(T, 7, 'sabel')
insert(T, 4, 'asdfasf')
insert(T, 3, 'bfdb')
insert(T, 2, 'yjf')
insert(T, 1, 'erter')
insert(T, 5, 'lib')
insert(T, 6, 'awdegr')
insert(T, 9, 'mnbmbnmbnmbn')
insert(T, 99, 'asdewgvxc')
insert(T, 77, 'rdgdgrdg')
insert(T, 61, 'ildrgmar')
insert(T, 113, 'pcap')
insert(T, 115, 'pcap2')
insert(T, 114, 'pcap22')
insert(T, 116, 'pcap3')
insert(T, 117, 'pcap4')
insert(T, 107, 'log')
insert(T, 105, 'json')
insert(T, 109, 'netflow')
console.log(JSON.stringify(T, null, 4));
//console.log(getValue(T, 1));
remove(T, 116);
//remove(T, 105);
//remove(T, 77);
//remove(T, 61);
console.log(JSON.stringify(T, null, 4));
console.log(getValue(T, 114));

rbt.js

// see Robert Sedgewick :: Left-leaning Red-Black Trees

const RED   = true;
const BLACK = false;

var Node = function(key, value) {
  this.key    = key;
  this.value  = value;
  this.color  = RED;
  this.left   = null;
  this.right  = null;
};

// -- helpers

function minKey(node) {
  if (node.left === null) return node.key;
  else return minKey(node.left);
}

function maxKey(node) {
  if (node.right === null) return node.key;
  else return maxKey(node.right);
}

function minNode(node) {
  if (node.left === null) return node;
  else return minNode(node.left);
}

function maxNode(node) {
  if (node.right === null) return node;
  else return maxNode(node.right);
}

// -- search

function getValue(node, key){
  if (node === null) return null;
  if (key === node.key) {
    return node.value;
  };
  if (key < node.key) return getValue(node.left,  key);
  else return getValue(node.right, key);
}

// -- insert

function insert(node, key, value) {
  if (node === null) return new Node(key, value);
  if (key === node.key) {
    node.value = value;
    return node;
  }
  else if (key < node.key) node.left = insert(node.left, key, value);
  else node.right = insert(node.right, key, value);
  return node;
}

// -- delete

function remove(node, key) {
  if (node === null) return null;
  // we look at grandchildren, to avoid creating parent pointers, and to maintain downward check logic
  if (node && node.left) {
    if (key === node.left.key) node.left = removeChild(node.left);
    else if (key < node.key) return remove(node.left, key);
  }
  if (node && node.right ) {
    if (key === node.right.key) node.right = removeChild(node.right);
    else if (key > node.key) return remove(node.right, key);
  }
}

function removeChild(child) {
  // node has no children, just remove reference to it; let GC do the rest
  if (child.left === null && child.right === null) return null;
  // one child, remove node and promote that child in its place
  else if (child.left === null && child.right) return child.right;
  else if (child.left && child.right === null) return child.left;
  // two children, replace with minimal value in right subtree and remove original min value
  // else could be used, but writing it out explicitly for dev
  else if (child.left && child.right) return replaceNodeWithTwoChildren(child);
}

function replaceNodeWithTwoChildren(node) {
  // find smallest value from right subtree of child
  newval = minNode(node.right);
  // create temp pointers for child right and left subtrees
  // smallest is in left subtree, thus right is special
  // if no children, then do not create variabl, otherwise will become child to self (circular reference)
  if (node.left !== null) var tmpleft = node.left;
  if (node.right !== null && node.right.right !== null) var tmpright = node.right;
  // use remove() to drop found element
  remove(node.right, newval.key);
  // set that element as new value for deleted node
  node = newval;
  // restore child pointers
  // if left then just replace
  // if right with subelements then replace and set right children as node subtree
  // if right with no subelements then
  if (tmpleft != null) node.left = tmpleft;
  if (tmpright != null) node.right = tmpright;
  return node;
}

// --- Main/testing

var T = new Node(13, 'mermaid');
insert(T, 7, 'sabel');
insert(T, 4, 'asdfasf');
insert(T, 3, 'bfdb');
insert(T, 2, 'yjf');
insert(T, 1, 'erter');
insert(T, 5, 'lib');
insert(T, 6, 'awdegr');
insert(T, 9, 'mnbmbnmbnmbn');
insert(T, 99, 'asdewgvxc');
insert(T, 77, 'rdgdgrdg');
insert(T, 61, 'ildrgmar');
insert(T, 117, 'pcap4');
insert(T, 113, 'pcap');
insert(T, 115, 'pcap2');
insert(T, 114, 'pcap22');
insert(T, 116, 'pcap3');
insert(T, 107, 'log');
insert(T, 105, 'json');
insert(T, 109, 'netflow');
insert(T, 1, 'newval');
console.log(JSON.stringify(T, null, 4));
//console.log(getValue(T, 1));
remove(T, 107);
insert(T, 113, 'newval');
insert(T, 116, 'newschool');
//remove(T, 105);
//remove(T, 77);
//remove(T, 61);
console.log(JSON.stringify(T, null, 4));
console.log(getValue(T, 114));