I was inspired to write a binary search tree program in Lua. I was
surprised at how pleasantly compact and simple it came out, although
it’s probably fairly useless.

A high-performance binary-search tree in Lua (for LuaJIT) would
probably eschew method calls in favor of straight function calls.

    -- a binary search tree
    function treenode()
       -- Constructs and returns a treenode.
       -- A treenode can either be a leaf node or an internal node.
       -- Internal nodes always have two children.
       -- Treenodes are initially leaf nodes. Leaf nodes are distinguished by 
having no key.
       -- When you insert a value into a leaf node, it becomes an internal node.
       -- The children of internal nodes are called “left” and “right”.
       -- The left subtree descended from an internal node contains only
       -- keys strictly less than that node’s key.
       -- The right subtree contains only keys strictly greater.
       return ({
          search = function(self, key)
                      if self.key == nil then return nil end -- leafnode case
                      if key == self.key then return self.value end
                      if key  < self.key then return self.left:search(key) end
                                              return self.right:search(key) 
          insert = function(self, key, value)
                      if self.key == nil then -- morph into an internal node
                         self.key, self.value, self.left, self.right = key, 
value, treenode(), treenode()
                      if key == self.key then 
                         self.value = value
                      if key < self.key then return self.left:insert(key, 
value) end
                                             return self.right:insert(key, 

This software is available via

    git clone http://canonical.org/~kragen/sw/inexorable-misc.git

(or in <http://canonical.org/~kragen/sw/inexorable-misc>) in the file

Like everything else posted to kragen-hacks without a notice to the
contrary, this software is in the public domain.

To unsubscribe: http://lists.canonical.org/mailman/listinfo/kragen-hacks

Reply via email to