Persistent Search Trees

Persistence in the context of data structures is divided into 4 different types. The particular code logic I implemented was a simple proof-of-concept for 'partial persistence'. For more information on the other three types - full, confluent, functional - please refer to details in Tarjan et. al. in [1].

In partial persistence, updates are always done on the latest version and time-travel only supports read-only queries on earlier versions back in time. In the following, we demonstrate an implementation of a persistent BST and the ability to "time-travel" back to earlier versions of itself.

See this zip file for the full implementation.

References

[1] Neil Sarnak, Robert E. Tarjan (1986). "Planar Point Location Using Persistent Search Trees" (PDF). Communications of the ACM. 29 (7): 669–679. doi:10.1145/6138.6151.

In [1]:
import persistent_tree
from   persistent_tree import PersistentBST

def make_tree():

    t = PersistentBST()
    l = [ 'E', 'C', 'M', 'O', 'A', 'I', 'G', 'K', 'J' ]

    for i, x in enumerate( l ):
        print 'Inserting item %s in version %s' % ( x, i )
        t.insert( x )
        
    for ii, x in enumerate(['M', 'E', 'A']):
        print 'Deleting item %s in version %s' % ( x, ii+i+1 )
        t.delete( x )

    return t

t = make_tree()

Inserting item E in version 0
Inserting item C in version 1
Inserting item M in version 2
Inserting item O in version 3
Inserting item A in version 4
Inserting item I in version 5
Inserting item G in version 6
Inserting item K in version 7
Inserting item J in version 8
Deleting item M in version 9
Deleting item E in version 10
Deleting item A in version 11
In [2]:
with persistent_tree.context( version=0 ):
    t.print_tree_dot( 'Tree structure (version=0)\nInorder traversal : %s' % t.inorder_traverse() )

Couldn't import dot_parser, loading of dot files will not be possible.
In [3]:
with persistent_tree.context( version=1 ):
    t.print_tree_dot( 'Tree structure (version=1)\nInorder traversal : %s' % t.inorder_traverse() )
In [4]:
with persistent_tree.context( version=2 ):
    t.print_tree_dot( 'Tree structure (version=2)\nInorder traversal : %s' % t.inorder_traverse() )
In [5]:
with persistent_tree.context( version=5 ):
    t.print_tree_dot( 'Tree structure (version=5)\nInorder traversal : %s' % t.inorder_traverse(), 
                      width=240, height=160 )
In [6]:
with persistent_tree.context( version=12):
    t.print_tree_dot( 'Tree structure (version=12)\nInorder traversal : %s' % t.inorder_traverse(), 
                      width=240, height=160 )