#=====================================================================
# Author: Isai Damier
# Title: Delete
# Project: geekviewpoint
# Package: algorithms
#
# Time Complexity of Solution:
# Best = const; Average = O(log(n)); Worst = O(n).
#
# Technical Details:
# 1] find node to be removed and track its parent
# 2] if node is None then return None (element is not in tree)
# 3] declare 'replacement' Node
# 4] if node has both children
# - delete node's successor
# - give custody of node's children to successor
# - set 'replacement' to successor
# 5] if node has fewer than two children
# - set 'replacement' to node's child
# 6] if node is self.root then set 'replacement' to self.root
# (new self.root)
# 7] else 'replacement' becomes child of node's parent
#
#=====================================================================
class BST( object ):
def __init__( self ):
self.root = None
def getRoot( self ):
return self.root
def delete( self, el ):
# find node and it's parent
node, parent = self.root, None
while node is not None and el != node.data:
parent = node
if el > node.data:
node = node.right
else:
node = node.left
# if node is None return None
if node is None:
return None
# declare replacement
replacement = None
# if node has two children
if node.left is not None and node.right is not None:
replacement = self.removeSuccessor( node )
replacement.left = node.left
replacement.right = node.right
# if node has one or no child
elif node.left is None:
replacement = node.right
else:
replacement = node.left
# replace node
if node == self.root:
self.root = replacement
elif parent.left == node:
parent.left = replacement
else:
parent.right = replacement
return node
def removeSuccessor( self, n ):
# it is known that n has a right child
succ, parent = n.right, n
while succ.left is not None:
parent = succ
succ = succ.left
# a successor has no left child
if succ == parent.right:
parent.right = succ.right
else:
parent.left = succ.right
return succ
