class node:
n = 0
keys = []
p = []
root = None
class KeyStatus:
Duplicate = 0
SearchFailure =1
Success = 2
InsertIt = 3
LessKeys = 4
def insert(key):
global root
newnode = node()
upKey = 0
value, upKey, newnode = ins(root, key, upKey, newnode)
if (value == KeyStatus.Duplicate):
print "Key already available"
if (value == KeyStatus.InsertIt):
uproot = root
root = node()
root.n = 1
root.keys.append(upKey)
root.p.append(uproot)
root.p.append(newnode)
def ins(ptr, key, upKey, newnode):
newPtr = node()
lastPtr = node()
newKey = 0
if (ptr == None):
newnode = None
upKey = key
return KeyStatus.InsertIt, upKey, newnode
n = ptr.n
pos = searchPos(key, ptr.keys, n)
print pos
if (pos < n and key == ptr.keys[pos]):
return KeyStatus.Duplicate, upKey, newnode
value, newKey, newPtr = ins(ptr.p[pos], key, newKey, newPtr);
if (value != KeyStatus.InsertIt):
return value
if(n < (5-1)):
pos = searchPos(newKey, ptr.keys, n)
for i in range(pos, n, -1):
ptr.keys[i] = ptr.keys[i-1]
ptr.p.append(ptr.p[i])
ptr.keys.append(newKey)
ptr.p.append(newPtr)
ptr.n += 1
return KeyStatus.Success, upKey, newnode
if (pos == 5 - 1):
lastKey = newKey;
lastPtr = newPtr;
else:
lastKey = ptr.keys[5-2];
lastPtr = ptr.p[5-1];
for i in range(pos, 5-2, -1):
ptr.keys[i] = ptr.keys[i-1]
ptr.p.append(ptr.p[i])
ptr.keys.append(newKey)
ptr.p.append(newPtr)
splitPos = (5 - 1)/2
upKey = ptr.keys[splitPos]
newnode = node()
ptr.n = splitPos
newnode.n = 5-1-splitPos
for i in range(newnode.n):
newnode.p[i] = ptr.p[i + splitPos + 1]
if(i < newnode.n - 1):
newnode.keys[i] = ptr.keys[i + splitPos + 1]
else:
newnode.keys[i] = lastKey
newnode.p[newnode.n] = lastPtr
return KeyStatus.InsertIt, upKey, newnode
def display(ptr, blanks):
if (ptr):
for i in range(blanks):
print " "
for i in range(ptr.n):
print "%d " %ptr.keys[i],
print "\n"
for i in range(ptr.n):
display(ptr.p[i], blanks+10)
def searchPos(key, key_arr, n):
pos = 0
while(pos < n and key > key_arr[pos]):
pos += 1
return pos
def search(key):
global root
ptr = root
print "Search path: "
while(ptr):
n = ptr.n
for i in range(ptr.n):
print "%d" %ptr.keys[i]
print "\n"
pos = searchPos(key, ptr.keys, n);
if (pos < n and key == ptr.keys[pos]):
print "\nKey %d found in position %d of last dispalyed node\n" %(key,i)
return
ptr = ptr.p[pos]
print "Key %d is not available\n" %key
def my_del(ptr, key):
p = node()
lptr = node()
rptr = node()
if(ptr == None):
return SearchFailure;
n=ptr.n
key_arr = ptr.keys
p = ptr.p
min = (5 - 1)/2
pos = searchPos(key, key_arr, n)
if(p[0] == None):
if (pos == n or key < key_arr[pos]):
return KeyStatus.SearchFailure
for i in range(pos+1, n):
key_arr[i-1] = key_arr[i]
p[i] = p[i+1]
ptr.n -= 1
temp = 0
if(ptr == root):
temp = 1
else:
temp = min
if(ptr.n >= temp):
return KeyStatus.Success
else:
return KeyStatus.LessKeys
if (pos < n and key == key_arr[pos]):
qp = p[pos]
while(True):
nkey = qp.n
qp1 = qp.p[nkey]
if (qp1 == None):
break
qp = qp1
key_arr[pos] = qp.keys[nkey-1]
qp.keys[nkey - 1] = key
value = my_del(p[pos], key)
if (value != KeyStatus.LessKeys):
return value
if (pos > 0 and p[pos-1].n > min):
pivot = pos - 1
lptr = p[pivot]
rptr = p[pos]
rptr.p[rptr.n + 1] = rptr.p[rptr.n]
for i in range(0, ptr.n, -1):
rptr.keys[i] = rptr.keys[i-1];
rptr.p[i] = rptr.p[i-1];
rptr.n += 1
rptr.keys[0] = key_arr[pivot]
rptr.p[0] = lptr.p[lptr.n]
key_arr[pivot] = lptr .keys[--lptr.n];
return KeyStatus.Success
if (pos<n and p[pos+1].n > min):
pivot = pos
lptr = p[pivot]
rptr = p[pivot+1]
lptr.keys[lptr.n] = key_arr[pivot]
lptr.p[lptr.n + 1] = rptr.p[0]
key_arr[pivot] = rptr.keys[0]
lptr.n += 1
rptr.n -= 1
for i in range(rptr.n):
rptr.keys[i] = rptr.keys[i+1]
rptr.p[i] = rptr.p[i+1]
rptr .p[rptr.n] = rptr.p[rptr.n + 1]
return KeyStatus.Success
if(pos == n):
pivot = pos-1
else:
pivot = pos
lptr = p[pivot]
rptr = p[pivot+1]
lptr.keys[lptr.n] = key_arr[pivot]
lptr.p[lptr.n + 1] = rptr.p[0]
for i in range(rptr.n):
lptr.keys[lptr .n + 1 + i] = rptr.keys[i]
lptr.p[lptr.n + 2 + i] = rptr.p[i+1]
lptr.n = lptr.n + rptr.n +1
for i in range(pos+1, n):
key_arr[i-1] = key_arr[i]
p[i] = p[i+1]
ptr -= 1
temp = 0
if(ptr == root):
temp = 1
else:
temp = min
if(ptr.n >= temp):
return KeyStatus.Success
else:
return KeyStatus.LessKeys
def DelNode(key):
global root
uproot = node()
value = my_del(root,key)
if value == KeyStatus.SearchFailure:
print "Key %d is not available" %key
return
if value == KeyStatus.LessKeys:
uproot = root
root = root.p[0]
return
while(True):
print "1.Insert"
print "2.Delete"
print "3.Search"
print "4.Display"
print "5.Quit"
print "Enter your choice : ",
choice = int(raw_input())
if choice == 1:
print "\nEnter the key : ",
key = int(raw_input())
insert(key)
elif choice == 2:
print "\nEnter the key : ",
key = int(raw_input())
DelNode(key)
elif choice == 3:
print "\nEnter the key : ",
key = int(raw_input())
search(key)
elif choice == 4:
print "\nBtree is :\n"
display(root,0)
elif choice == 5:
import sys
sys.exit()
else:
print "Wrong choice"
break
def preorder(p):
stack = []
top = -1
if(p != None):
print p.info
if(p.rchild != None):
top += 1
stack[top] = p.rchild
p = p.lchild
while(top >= -1):
while ( p!= None):
print p.data
if(p.rchild != None):
top += 1
stack[top] = p.rchild
p = p.lchild
p = stack[top]
top -= 1
def inorder(p):
stack = []
top = -1;
if(p != None):
top += 1
stack[top] = p
p = p.lchild
while(top >= 0):
while ( p!= None):
top += 1
stack[top] = p
p = p.lchild
p = stack[top]
top -= 1
print p.data
p = p.rchild
if ( p != None):
top += 1
stack[top] = p
p = p.lchild
def postorder(p):
stack = []
sig = 0
sign = []
top = -1
if(p != None):
top += 1
stack[top] = p
sign[top] = 1
if(p.rchild != None):
top += 1
stack[top] = p.rchild
sign[top] = -1
p = p.lchild
while(top >= 0):
while(p != None):
top += 1
stack[top] = p
sign[top] = 1
if(p.rchild != None):
top += 1
stack[top] = p.rchild
sign[top] = -1
p = p.lchild
p = stack[top]
sig = sign[top]
top -= 1
while((sig > 0) and (top >= -1)):
print p.info
p = stack[top]
sig = sign[top]
top -= 1
import sys
class BST:
class node:
info = None
lchild = None
rchild = None
def __init__(self):
self.root = self.node()
def find(self, item, par, loc):
ptr = self.node()
ptrsave = self.node()
if(self.root==None):
loc = None
par = None
return
if(item == self.root.info):
loc = self.root
par = None
return
if(item < self.root.info):
ptr = self.root.lchild
else:
ptr = self.root.rchild
ptrsave = self.root
while(ptr!=None):
if(item == ptr.info):
loc = ptr
par = ptrsave
return
ptrsave = ptr
if(item<ptr.info):
ptr = ptr.lchild
else:
ptr = ptr.rchild
loc = None
par = ptrsave
return par,loc
def case_a(self, par, loc):
if(par == None):
self.root = None
else:
if(loc == par.lchild):
par.lchild = None
else:
par.rchild = None
def case_b(self, par, loc):
child = self.node()
if(loc.lchild != None):
chile = loc.lchild
else:
child = loc.rchild
if(par == None):
self.root = None
else:
if(loc == par.lchild):
par.lchild = child
else:
par.rchid = child
def case_c(self, par, loc):
ptr = self.node()
ptrsave = self.node()
suc = self.node()
parsuc = self.node()
ptrsave = loc
ptr = loc.lchild
while(ptr.lchild != None):
ptrsave = ptr
ptr = ptr.lchild
suc = ptr
parsuc = ptrsave
if(suc.lchild == None and suc.rchild == None):
self.case_a(parsuc, suc)
else:
self.case_b(parsuc, suc)
if(par==None):
self.root = suc
else:
if(loc==par.lchild):
par.lchild = suc
else:
par.rchild = suc
suc.lchild = loc.lchild
suc.rchild = loc.rchild
def insert(self, item):
tmp = self.node()
parent = self.node()
location = self.node()
parent,location = self.find(item, parent, location)
if(location != None):
print "Item already present"
raw_input()
return
tmp.info = item
tmp.lchild = None
tmp.rchild = None
if(parent.info==None):
self.root = tmp
else:
if(item<parent.info):
parent.lchild=tmp
else:
parent.rchild=tmp
def my_del(self, item):
parent = self.node()
location = self.node()
if(self.root==None):
print "Tree is empty"
raw_input()
return
self.find(item, parent, location)
if(location==None):
print "Item not present in tree"
return
if(location.lchild==None and location.rchild==None):
self.case_a(parent,location)
if(location.lchild!=None and location.rchild==None):
self.case_b(parent,location)
if(location.lchild==None and location.rchild!=None):
self.case_b(parent,location)
if(location.lchild!=None and location.rchild!=None):
self.case_c(parent,location)
delete(location)
def preorder(self, ptr):
if(self.root==None):
print "Tree is empty"
raw_input()
return
if(ptr!=None):
print ptr.info
self.preorder(ptr.lchild)
self.preorder(ptr.rchild)
def inorder(self, ptr):
if(self.root==None):
print "Tree is empty"
raw_input()
return
if(ptr!=None):
self.inorder(ptr.lchild)
print ptr.info
self.inorder(ptr.rchild)
def postorder(self, ptr):
if(self.root==None):
print "Tree is empty"
raw_input()
return
if(ptr!=None):
self.postorder(ptr.lchild)
self.postorder(ptr.rchild)
print ptr.info
def display(self, ptr, level):
#print ptr.info
if (ptr!=None):
self.display(ptr.rchild, level+1);
for i in range(level):
print " "
print ptr.info
self.display(ptr.lchild, level+1)
bo = BST()
while(1):
print "\n1.Insert"
print "2.Delete"
print "3.Inorder Traversal"
print "4.Preorder Traversal"
print "5.Postorder Traversal"
print "6.Display"
print "7.Quit"
print "\nEnter your choice: ",
choice = int(raw_input())
if choice == 1:
print "Enter the number to be inserted: ",
num = int(raw_input())
bo.insert(num)
elif choice == 2:
print "Enter the number to be deleted: ",
num = int(raw_input())
bo.my_del(num)
elif choice == 3:
bo.inorder(bo.root)
raw_input()
elif choice == 4:
bo.preorder(bo.root)
raw_input()
elif choice == 5:
bo.postorder(bo.root);
raw_input()
elif choice == 6:
bo.display(bo.root,1);
raw_input()
elif choice == 7:
sys.exit()
else:
print "Wrong choice..."
raw_input()