Skip to content

Instantly share code, notes, and snippets.

@pixyj
Created October 6, 2012 16:06
Show Gist options
  • Save pixyj/3845327 to your computer and use it in GitHub Desktop.
Save pixyj/3845327 to your computer and use it in GitHub Desktop.
Analysis of Binary Search Tree Insertion Time
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)
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
@pixyj
Copy link
Author

pixyj commented Oct 6, 2012

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)

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment