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.
#!/usr/bin/lua
-- 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)
end;
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()
return
end
if key == self.key then
self.value = value
return
end
if key < self.key then return self.left:insert(key,
value) end
return self.right:insert(key,
value)
end;
})
end
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
`bst.lua`.
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
