Analysis of Binary Search Tree Insertion Time

tree.py

class Node:
	def __init__(self,val,parent=None):
		self.val = val
		self.parent = parent
		self.left = None
		self.right = None

	def setLeft(self,node):
		self.left = node

	def setRight(self,node):
		self.right = node	


class Tree:
	def __init__(self,val):
		self.root = Node(val,None)
		self.count_add = 0

	def add(self,val):
		
		if self.root.val == val:
			return False

		q1=self.root
		p1=self.root
		while q1 != None:
			self.count_add += 1
			p1 = q1
			if q1.val > val:
				q1 = q1.left
			elif q1.val < val:
				q1 = q1.right
			else:
				print 'duplicate' 
				return False

		node = Node(val)		
		if p1.val > val:
			p1.left = node
		else:
			p1.right = node  		

		return True

	def pre_order(self,root,cb):
		if root == None:
			return;
		
		cb(root)
		
		self.pre_order(root.left,cb)
		self.pre_order(root.right,cb)

	def post_order(self,root,cb):
		if root == None:
			return
		self.post_order(root.left,cb)
		self.post_order(root.right,cb)
		cb(root)

	def in_order(self,root,cb):
		if root == None:
			return
		self.in_order(root.left,cb)
		cb(root)
		self.in_order(root.right,cb)

tree_perm.py

import tree
import itertools
import pdb
import math

def calc_count_add(size):
	l = [i for i in xrange(size)]

	perms = itertools.permutations(l)
	count_total = 0
	while True:
		try:
			perm = perms.next()
			t=tree.Tree(perm[0])
			for i in perm[1::]:
				t.add(i)

			count_total += t.count_add
		except StopIteration:
			break; 

	return count_total


def calc_count_upto(upto):
	count_upto = []
	for i in xrange(1,upto+1):
		avg_count = calc_count_add(i)
		avg_count = avg_count*1.0/math.factorial(i)
		count_upto.append(avg_count)

	return count_upto

def calc_formula(size):
	if size == 1:
		return 0
	else:
		count = 0.0
		for i in xrange(1,size):
			count += calc_formula(i)
		count = count * 2/size
		count += size - 1
		return count

def calc_formula_upto(size):

	counts = []
	[counts.append(calc_formula(i)) for i in xrange(1,size+1)]
	return counts

Gist to find the average time to insert a node onto a binary search tree.

Reference: http://www.youtube.com/watch?v=KyMiqaA0ijM

Most interesting part:

Best Case Time = O(nlogn)
Average time = O(nlogn)
Worst Case Time = O(n^2)