www.main.lv

2010-07-20 Python MIT Binary Trees

After reading chapter form MIT Introduction in algorithms about trees I have implemented same algorithm in python
I haven't tryed to make best perfomance only easy to understund and one to one like is in pseudo-code

Tree python class that are used to represent BinaryTree.

class Tree:
	p = None
	left = None
	right = None
	key = 0

pseudo-code

Inorder_Tree_Walk( x )
if x != NIL
    then Inorder_Tree_Walk( left[x] )
        print key[x]
        Inorder_Tree_Walk( right[x] )

python code

def inorder_tree_walk( t ):
    if t != None:
        inorder_tree_walk( t.left )
        print t.key,
        inorder_tree_walk( t.right )

pseudo code

Tree_Search( x , k )
if x = NIL or k = key[x]
    then return x
if k < key[x]
    then return Tree_Search( left[x] , k )
    else return Tree_Search( right[x] , k )

python code

def tree_search( t , k ):
    if (t == None) or (k == t.key):
        return t
    if k < t.key:
        return tree_search( t.left, k )
    return tree_search( t.right, k )

pseudo code

Tree_Minimum( x )
while left[x] != NIL
    do x <- left[x]
return x

python code

def tree_minimum( t ):
    while t.left != None:
        t = t.left
    return t

pseudo code

Tree_Maximum( x )
while right[x] != NIL
    do x <- right[x]
return x

python code

def tree_maximum( t ):
    while t.right != None:
        t = t.right
    return t

python code

def tree_root( t ):
    while ( t.p != None):
        t = t.p
    return t

pseudo code

Tree_Successor( x )
if right[x] != NIL
    then return Tree_Minimum( right[x] )
y <- p[x]
while y != NIL and x = right[y]
    do  x <- y
        y <- p[y]
return y

python code

def tree_successor( t ):
    if t.right != None:
        return tree_minimum( t.right )
    y = t.p
    while (y != None) and (t == y.right):
        t = y
        y = y.p
    return y

pseudo code

Tree_Insert( T , z )
y <- NIL
x <- root[T]
while x != NIL
    do y <- x
        if key[z] < key[x]
            then x <- left[x]
            else x <- right[x]
p[x] <- y
if y = NIL
    then root[T] <- z
    else if key[z] < key[y]
        then left[y] <- z
        else right[y] <- z

python code

def tree_insert( t , z ):
    y = None
    x = tree_root( t )
    while x != None:
        y = x
        if z.key < x.key:
            x = x.left
        else:
            x = x.right
    z.p = y
    if y == None:
        r = tree_root( t )
        r = z
    else:
        if z.key < y.key:
            y.left = z
        else:
            y.right = z

           

def tree_insert_recrusive( t , z ):
    if t.left == None and t.right == None:
        if z.key < t.key:
            t.left = z
        else:
            t.right = z
        return
    if z.key < t.key:
        tree_insert_recrusive( t.left , z )
    else:
        tree_insert_recrusive( t.right , z )

pseudo code

Tree_Delete( T , z )
if left[z] = NIL or right[z] = NIL
    then y <- z
    else y <- Tree_Successor( z )
if left[y] != NIL
    then x <- left[y]
    else x <- right[y]
if x != NIL
    then p[x] <- p[y]
if p[y] = NIL
    then root[T] <- x
    else if y = left[p[y]]
        then left[p[y]] <- x
        else right[p[y]] <- x
if y != z
    then key[z] <- key[y]
return y

python code

def tree_delete( t , z ):
    if (z.left == None) or (z.right == None):
        y = z
    else:
        y = tree_successor( z )
    if y.left != None:
        x = y.left
    else:
        x = y.right
    if x != None:
        x.p = y.p
    if y.p == None:
        r = tree_root( t )
        r = x
        t = r
    else:
        if y == y.p.left:
            y.p.left = x
        else:
            y.p.right = x
    if y != z:
        z.key = y.key
    return y

Example of usage:
Now we can use out tree. There is some more functions like create_tree that creates binary tree from given array.
And print_tree that print all ree values.

keys = [10,6,1,0,3,8,7,9,21,15,11,17,25,23,46]
max_deep = log(len(keys),2)

def create_tree( n=0 , p=None):
    if (len(keys) == 0) or (n >= max_deep):
        return None
    t = Tree()
    t.p = p
    t.key = keys.pop(0)
    t.left = create_tree( n+1 , t )
    t.right = create_tree( n+1 , t)
    return t

   
   

def print_tree( t ):
    if (t != None) and (t.key != None):
        if t.left == t.right == None:
            print "Key:%d "%(t.key)
            return
        if t.left.key == None:
            print "Key:%d Right:%d"%(t.key,t.right.key)
            print_tree( t.right )
            return
        if t.right.key == None:
            print "Key:%d Left:%d"%(t.key,t.left.key)
            print_tree( t.left )
            return
        print "Key:%d Left:%d Right:%d"%(t.key,t.left.key,t.right.key)
        print_tree( t.left )
        print_tree( t.right )

t = create_tree()
r = tree_search( t, 10 )
n = Tree()
n.key = 150
tree_insert_recrusive( t , n )
inorder_tree_walk( t )
print ""
tree_delete( t , r )
inorder_tree_walk( t )
print ""
r = tree_root( t )
print r.key

Source