Skip to content

Instantly share code, notes, and snippets.

@naiquevin
Created August 15, 2012 15:27
Show Gist options
  • Save naiquevin/3361020 to your computer and use it in GitHub Desktop.
Save naiquevin/3361020 to your computer and use it in GitHub Desktop.
Tuple based tree implementation in Erlang (from LYSE) and Python
The no. of lines in erlang implementation is half that in python!
Observe how pattern matching alone gets rid of the selector functions
-module(tree).
-export([empty/0, insert/3, lookup/2]).
%% build an empty node
empty() -> {node, 'nil'}.
%% insert will take 3 args - key, value and a node
%% and add a new node with the Key and Value to the Node
insert(Key, Val, {node, 'nil'}) ->
{node, {Key, Val, {node, 'nil'}, {node, 'nil'}}};
insert(NewKey, NewVal, {node, {Key, Val, Smaller, Larger}}) when NewKey < Key ->
{node, {Key, Val, insert(NewKey, NewVal, Smaller), Larger}};
insert(NewKey, NewVal, {node, {Key, Val, Smaller, Larger}}) when NewKey > Key ->
{node, {Key, Val, Smaller, insert(NewKey, NewVal, Larger)}};
insert(Key, Val, {node, {Key, _, Smaller, Larger}}) ->
{node, {Key, Val, Smaller, Larger}}.
%% lookup function
lookup(_, {node, 'nil'}) ->
undefined;
lookup(Key, {node, {Key, Val, _, _}}) ->
{ok, Val};
lookup(Key, {node, {NodeKey, _, Smaller, _}}) when Key < NodeKey ->
lookup(Key, Smaller);
lookup(Key, {node, {_, _, _, Larger}}) ->
lookup(Key, Larger).
#!/usr/bin/env python
def empty():
return ('node', None)
def is_empty(node):
return len(node) == 2 and node[1] is None
def create_node(key, val, smaller, larger):
return ('node', (key, val, smaller, larger))
def get_key(node):
return node[1][0]
def get_val(node):
return node[1][1]
def get_smaller(node):
return node[1][2]
def get_larger(node):
return node[1][3]
def insert(key, val, node):
# if node is empty, create a new node with smaller and larger
if is_empty(node):
return ('node', (key, val, empty(), empty()))
# else if key < key of node, add a node to smaller
nodekey, nodeval, smaller, larger = get_key(node), get_val(node), get_smaller(node), get_larger(node)
if key < nodekey:
return create_node(nodekey, nodeval, insert(key, val, smaller), larger)
# else if key > key of node, add a node to larger
if key > nodekey:
return create_node(nodekey, nodeval, smaller, insert(key, val, larger))
# else if key = key of node, replace with latter
if key == nodekey:
return create_node(nodekey, val, smaller, larger)
def lookup(key, node):
if is_empty(node):
return None
if key == get_key(node):
return ('ok', get_val(node))
if key < get_key(node):
return lookup(key, get_smaller(node))
if key > get_key(node):
return lookup(key, get_larger(node))
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment