Jacob Repp

Building algorithms in ruby is fun and rewarding. This binary tree doesn’t balance itself but it is simple and flexible using ruby blocks for visit and insert. Traversal style can be selected optionally to visit with :inorder, :preorder or :postorder.

Here’s your basic binary tree node representation, it holds a value and connects to a left and right node:

class Node
    # binary tree representation
    attr_accessor :value, :left, :right
    def initialize(value=nil, left=nil, right=nil)
        @value, @left, @right = value, left, right
    end
end

Insert receives a value and a block which is responsible for doing the comparison. Comparison would normally be done with the Ruby <=> operator (this is the case later when the chunkybacon is inserted into the tree). The block passed to insert receives two elements and should yield a -1 for less, 1 for greater or 0 for equal. This function is implemented in terms of itself, notable for it’s lack of any balancing.

def insert(node, v, &block)
    # binary tree insert without balancing, 
    # block performs the comparison operation
    return Node.new(v) if not node
    case block[v, node.value]
        when -1 
            node.left = insert(node.left, v, &block)
        when 1 
            node.right = insert(node.right, v, &block)
    end
    return node
end

Visit receives the order that the nodes should be visited as well as a block that will act as a visitor of the stored values. This function is also implemented in terms of itself.

def visit(n, order=:preorder, &block)
    # visit nodes in a binary tree, order can be determinied
    # block performs visit action
    return false unless (n != nil)

    case order 
        when :preorder 
            yield n.value
            visit(n.left, order, &block)
            visit(n.right, order, &block)
        when :inorder
            visit(n.left, order, &block)
            yield n.value
            visit(n.right, order, &block)
        when :postorder
            visit(n.left, order, &block)
            visit(n.right, order, &block)
            yield n.value
    end
end

And here is a simple example of inserting the string ‘chunkybacon’ into the binary tree. The result of visiting this tree using :inorder traversal is the string ‘abchknouy’.

if $0 == __FILE__
    # a simple test case
    root = nil
    "chunkybacon".scan(/./m) {|c| root = insert(root, c) {|a,b| a<=>b}}
    visit(root, :inorder) {|v| print v}
end

You may like it you will see, try it, try it and leave a comment for me.

Related posts:

• Build Huffman Compression in Ruby

Trackback URI | Comments RSS