Skip to content

Instantly share code, notes, and snippets.

@tahia-khan tahia-khan/bst.py
Last active Nov 8, 2015

Embed
What would you like to do?
class Node:
def __init__(self, data):
self.data = data
self.lchild = None
self.rchild = None
def insert(self, key):
if key < self.data:
if self.lchild:
self.lchild.insert(key)
else:
self.lchild = Node(key)
elif key > self.data:
if self.rchild:
self.rchild.insert(key)
else:
self.rchild = Node(key)
def inorder_traversal(self):
if self.lchild:
self.lchild.inorder_traversal()
print self.data
if self.rchild:
self.rchild.inorder_traversal()
class BST:
def __init__(self):
self.root = None
def insert(self, key):
if not self.root:
self.root = Node(key)
else:
self.root.insert(key)
def inorder(self):
if self.root:
self.root.inorder_traversal()
def find_parent(self, key):
cur = self.root
while (cur.lchild or cur.rchild):
if key < cur.data:
if cur.lchild:
if key == cur.lchild.data:
return cur
else:
cur = cur.lchild
else: break
elif key > cur.data:
if cur.rchild:
if key == cur.rchild.data:
return cur
else:
cur = cur.rchild
else: break
# splice out leftmost node of right subtree
# this node might have at most one rchild
def splice_successor(self, node):
cur = node.rchild
if not node.rchild.lchild:
node.rchild = None
return cur
while (cur.lchild.lchild):
cur = cur.lchild
succ = cur.lchild
if succ.rchild:
cur.lchild = succ.rchild
else:
cur.lchild = None
succ.rchild = None
return succ
def remove_node(self, k):
p = self.find_parent(k)
n = p.lchild if p.lchild.data == k else p.rchild
if not n.lchild and not n.rchild:
if p.lchild == n:
p.lchild = None
elif p.rchild == n:
p.rchild = None
elif n.lchild and n.rchild:
succ = self.splice_successor(n)
succ.lchild = n.lchild
succ.rchild = n.rchild
if p.lchild == n:
p.lchild = succ
elif p.rchild ==n:
p.rchild = succ
else:
child = n.lchild if n.lchild else n.rchild
if p.lchild == n:
p.lchild = child
elif p.rchild == n:
p.rchild = child
n = None
return
t = BST()
t.insert(19)
t.insert(67)
t.insert(13)
t.insert(25)
t.insert(100)
t.insert(80)
t.inorder()
n = t.remove_node(67)
t.inorder()
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.