Program to insert contents of file in bst or avl

# Program to insert contents of file in bst or avl
# It calculates total time it took for the insertion of all the elements
# It also calcultaes average height of the tree formed and height of any particaluar node
# Average height is the average of lenghts of all the paths from root to leaves
# Functions for inorder traversals for the both are given
# A sample file may be inculded with the project named "input.txt" which contains 1000000 numbers
# So make sure to have a file named "input.txt" in the same directory as the code (having some numbers)

import time
class node:
left = right = parent = data = height = None

class bst:
root = None
max_height = 0
ttime = 0

def insert1(self,number):
if self.root is None:
self.root = node()
self.root.data = number
self.root.height = 0

else:
p = None
current = self.root
h = 0
while (current is not None):
p = current
h = h + 1
if number > current.data:
current = current.right
else:
current = current.left

if number > p.data:
p.right = node()
p.right.data = number
p.right.height = h
p.right.parent = p
if h > self.max_height:
self.max_height = h

else:
p.left = node()
p.left.data = number
p.left.height = h
p.left.parent = p
if h > self.max_height:
self.max_height = h

def insert(self,file_name):
start_tick = time.time()
with open(file_name) as openfileobject:
for line in openfileobject:
self.insert1(int(line))
end_tick = time.time()
diff = end_tick - start_tick
self.ttime = diff

def inorder_body(self,current):
if current:
self.inorder_body(current.left)
print current.data
self.inorder_body(current.right)

def inorder(self):
self.inorder_body(self.root)

def avg_height(self):
class avg:
avh = 0
number_nodes = 0
average_height_reference = avg()
self.inorder_height(self.root,average_height_reference)
avgheight = (1.0*average_height_reference.avh)/average_height_reference.number_nodes
return avgheight

def inorder_height(self,current,avg):
if current:
self.inorder_height(current.left,avg)
if current.left is None and current.right is None:
avg.avh = avg.avh+current.height
avg.number_nodes = avg.number_nodes + 1
self.inorder_height(current.right,avg)

def t(self):
return self.ttime

def height(self,number=None):
if number is None:
return self.max_height
else:
current = self.root
while (current is not None):
if current.data == number:
break
elif current.data > number:
current = current.left
else:
current = current.right
if current is None:
print "Number not found"
else:
return current.height

class avl_node:
left = right = parent = None
height = 1

class avl:
root = None

def node_height(self,current):
if current == None:
return 0
else:
return current.height

def balance_factor(self,current):
return self.node_height(current.left) - self.node_height(current.right)

def setheight(self,current):
if current==None:
return
else:
left = self.node_height(current.left)
right = self.node_height(current.right)
current.height = max(left,right) + 1
factor = self.balance_factor(current)
if (factor > 1 and self.node_height(current.left.left) > self.node_height(current.left.right)):
current = self.right_rotate(current)
elif (factor > 1):
self.left_rotate(current.left)
current = self.right_rotate(current)
elif(factor < -1 and self.node_height(current.right.right) > self.node_height(current.right.left)):
current = self.left_rotate(current)
elif(factor < -1):
self.right_rotate(current.right)
current = self.left_rotate(current)
self.setheight(current.parent)

def right_rotate(self,current):
if current is None:
return
else:
l = current.left
z = l.right
l.right = current
l.parent = current.parent
if (current.parent is not None):
if (current == current.parent.left):
current.parent.left = l
else:
current.parent.right = l
else:
self.root = l
current.left = z
current.parent = l
if z is not None:
z.parent = current
current.height = max(self.node_height(current.left),self.node_height(current.right)) + 1 ;
l.height = max(self.node_height(l.left),self.node_height(l.right)) + 1 ;
return l

def left_rotate(self,current):
if current is None:
return
else:
r = current.right
z = r.left
r.left = current
r.parent = current.parent
if (current.parent is not None):
if (current == current.parent.left):
current.parent.left = r
else:
current.parent.right = r
else:
self.root = r
current.right = z
current.parent = r
if z is not None:
z.parent = current
current.height = max(self.node_height(current.left),self.node_height(current.right)) + 1 ;
r.height = max(self.node_height(r.left),self.node_height(r.right)) + 1 ;
return r

def insert1(self,number):
if self.root is None:
self.root = avl_node()
self.root.data = number

else:
p = None
current = self.root
while (current is not None):
p = current
if number > current.data:
current = current.right
else:
current = current.left

if number > p.data:
p.right = avl_node()
p.right.data = number
p.right.parent = p
self.setheight(p.right)
else:
p.left = avl_node()
p.left.data = number
p.left.parent = p
self.setheight(p.left)

def inorder(self):
self.inorder_body(self.root)

def inorder_body(self,current):
if current:
self.inorder_body(current.left)
print current.data, " ", current.height
self.inorder_body(current.right)

def insert(self,file_name):
start_tick = time.time()
with open(file_name) as openfileobject:
for line in openfileobject:
self.insert1(int(line))
end_tick = time.time()
diff = end_tick - start_tick
self.ttime = diff

def height(self,number=None):
if number is None:
return self.root.height
else:
current = self.root
current_height = 0
while (current is not None):
if current.data == number:
break
elif current.data > number:
current_height = current_height + 1
current = current.left
else:
current_height = current_height + 1
current = current.right
if current is None:
print "Number not found"
else:
return current_height

def avg_height(self):
class avg:
avh = 0
number_nodes = 0
average_height_reference = avg()
self.inorder_height(self.root,average_height_reference,0)
avgheight = (1.0*average_height_reference.avh)/average_height_reference.number_nodes
return avgheight

def inorder_height(self,current,avg,number):
if current:
self.inorder_height(current.left,avg,number+1)
if current.left is None and current.right is None:
avg.avh = avg.avh+number
avg.number_nodes = avg.number_nodes + 1
self.inorder_height(current.right,avg,number+1)

def insert_time(self):
return self.ttime

def main():
bst1 = bst()
print "Insertion in Bst started..."
bst1.insert("input.txt")
print "Insertion in Bst finished"
bst_insert_time = bst1.t()
print "Time taken for insertion is ", bst_insert_time, " seconds"
bst_height = bst1.height()
print "Height of Bst formed is ", bst_height
bst_average_height = bst1.avg_height()
print "Average height of Bst formed is ", bst_average_height
nodes_height = bst1.height(61913013)
print "Height of node(61913013) is ", nodes_height

# bst1.inorder() will print the nodes of bst as encountered in inorder traversal

print

avl1 = avl()
print "Insertion in AVL started..."
avl1.insert("input.txt")
print "Insertion finished."
avl_insert_time = avl1.insert_time()
print "Time for insertion is ", avl_insert_time," seconds"
avl_tree_height = avl1.height()
print "Height of AVL tree formed is: ", avl_tree_height
avl_average_height = avl1.avg_height()
print "Average height of tree is ", avl_average_height
node_height = avl1.height(61913013)
print "Height of node(61913013) is ", node_height

# avl1.inorder() will print the nodes of avl as encountered in inorder traversal
main()