Exciting your orbitals

Hi all – so I’ve been busy as hell but that’s ok, there’s always time for some fun.  In my earlier posts I described how one could construct a tree using balanced ternary – it’s implementation time!  Lets begin by creating a really simple binary search tree. First we make a node:

class BSTNode(list):
  def __init__(self, data, left=None, right=None):
    super(BSTNode, self).__init__([self, right, left])
    self.data = data

The most important part of this snippet is the call to list’s constructor.  By passing in [self, right, left] we have the following:

self[-1] == left child
self[0] == current node
self[1] == right child

A really handy method to visualize each node is:

def __str__(self):
  _dict = {'data':self.data, 'leftChild':self[-1], 'rightChild':self[1]}
  template = "Node Data = %(data)r\nLeft Child = %(leftChild)r\nRight Child = %(rightChild)r" % _dict
  return template

This will show the current node’s data, and the left and right children as lists.  One alternative is to print out the left and right child’s data instead of the nodes themselves.  Now for the binary tree’s constructor:

class BSTree(object):
  def __init__(self, root=None):
    super(BSTree, self).__init__()
    self.size = 0
    if root is not None:
     self.size = 1
    self.root = root

And the add method:

def add(self, node, nxt=None):
  if self.root is None:
    self.root = node
    self.size = 1
  else:
    if nxt is None:
      nxt = self.root
    val = cmp(node.data, nxt.data)
    if nxt[val] is None:
      nxt[val] = node
      self.size = self.size + 1
   elif val == 0:
     raise 'Cannot add duplicate nodes'
   else:
     self.add(node, nxt[val])

And that’s it!  I’ll be the first to admit that this tree is about as minimalist as it gets, but you get the point.  Lets build a tool that calculates the itinerary to a given node:

def itinerary(self, node):
  nxt = self.root
  while nxt is not None:
    val = cmp(node.data, nxt.data)
    yield val
    nxt = nxt[val]
    if val == 0:
      raise StopIteration

This handy method returns a generator.  Cool.  But what does this actually do?  Well, given a target node, the generator will start at the root node and return a series of ones and negative ones, indicating the path.  Once the target node is reached, the generator yields zero and throws a StopIteration.  From here the possibilities are endless.  We’ve constructed a simple binary search tree with very interesting mathematical properties.

Finally, a data structure isn’t very useful if you can’t extract data from it so here’s an extremely simple recursive inorder traversal:

def inorder(self, node=None):
  def recursive(node):
    if node[-1] is not None:
      recursive(node[-1])
    array.append(node)
    if node[1] is not None:
      recursive(node[1])
  array = []
  if node is None:
    node = self.root
  recursive(node)
  return array

There is a way to return a generator as opposed to a list but that’s for another day.