problem in redblack tree delete operation

See more:

Python

algorithm

here is my complete of redblack tree i have problem with delete operation which is not working problem . problem is i am getting idea how to update tree from delete_case functions which sort the within their scope but in main function on few changes appear. main problem em facing is about python send are returning values. i know python send object my reference but in my case i did not know why original tree remain unchanged even i had update node pointer and in delete_case function

class tree:
    def __init__(self):
        self.data=0
        self.left=None
        self.right=None
        self.parent=None
        self.color='r'


def rotate_right(node):
    newNode=node.left;
    nodeLeft=newNode.right;
    newNode.right=node
    node.left=nodeLeft
    newNode.parent=node.parent
    if node.parent!=None:
        if node==(node.parent).left:
       #     print "\nright parent is left",((node.parent).left).data
            (node.parent).left=newNode
      #      print "right parent is left",((node.parent).left).data
           # print newNode.data, (newNode.left).data,(newNode.right).data
        else:
     #       print " right parent is right"
            (node.parent).right=newNode
    node.parent=newNode
    if newNode.parent==None:
        root=newNode
    if nodeLeft!=None:
        nodeLeft.parent=node

    #print "node after",newNode.data,((newNode.parent).right).data
    return newNode



def rotate_left(node):
  #  print 'data',node.data
    newNode=node.right
    noderight=newNode.left
    newNode.left=node
    node.right=noderight
    newNode.parent=node.parent
    if node.parent!=None:
        if node==(node.parent).left:
           # print "parent is left"
            (node.parent).left=newNode
        else:
          #  print "parent is left"
            (node.parent).right=newNode
    node.parent=newNode
  #  if newNode.parent!=None:
   #     (newNode.parent).right=newNode
    if newNode.parent==None:
        root=newNode
    if noderight!=None:
        noderight.parent=node
   # print 'node',newNode.data
    return newNode



def insert(Root,data):
    newNode=tree()
    newNode.data=data

    parent=root=Root
 #   print  "Node",parent.getData(),"  data",data
    while parent.data!=data and root!=None:
        parent=root
#        print parent.data,data
        if  parent.data > data:
            root=parent.left
        else:
            root=parent.right

    if data == parent.data:
        print "data already exist"
        del newNode
        return
    elif data<parent.data:
        parent.left=newNode
      #  newNode.color='r'
        newNode.parent=parent
#        print  "left Node"
    else:
        parent.right=newNode
       # newNode.color='r'
        newNode.parent=parent
    #print newNode.data
#    print parent.data,newNode.data
    IsRootNode(newNode)
    while Root.parent!=None:
        Root=Root.parent
    #print "root",Root.data
    return Root
  #      print  "Right Node"


def grandparent(node):

 if (node != None) and node.parent != None: #IF     NODE and Parent IS NOT Node is not Node
    return (node.parent).parent             #return grandparent
 else:
  return  None          #return None


#this function is use to return uncle for current . sibling of parent node
def uncle(node):
 # print node.data
  grandp= grandparent(node)         #get grandparent node using function
  if grandp ==None:                 #if grandparent is  null return Node
    return None   # No grandparent means no uncle
  if node.parent == grandp.left:                #parent is left of grandparent
    return grandp.right                          #return right child of grandparent
  else:                                             #else return left child
    return grandp.left


#check the node. if it is root labeled with black color
def IsRootNode(node):
 if (node.parent == None):  #if parent is Node
   # print 'cchekd',node.data
    node.color = 'b'            #currnet node is root
 else:
    blackParent(node)       #check if root node parent is black


#this function is used to check parent of node.
#if node parent is black return tree is in RB form
def blackParent(node ):
 if ((node.parent).color == 'b'):   #if parent is red
  return #  Tree is still valid
 else:
    parentNuncleAreRed(node)     #check if uncle color is red


#this function will check uncle color.
#function will validate tree depend of color of uncle
def parentNuncleAreRed(node):
  #print 'here'
  Nodeuncle = uncle(node)       #get value of uncle node
  if Nodeuncle!=None and Nodeuncle.color =='r': # if uncle is red
  #    print "here"
      (node.parent).color = 'b'         #label uncle and parent with black
      Nodeuncle.color = 'b'
      grandp = grandparent(node)        #color of grandparent and node to red
      grandp.color = 'r'
   #   print grandp.data,grandp.parent
      IsRootNode(grandp)                #check if tree is root node change color of black
  else: #if uncle color is not red
    LR_RLcase(node)

#LR =left child of right parent
#RL= right child of left parent
#this case same like AVL free LR RL rotation
def LR_RLcase(node):
    #get grandparend node
    grandp = grandparent(node)
    #if current node is left child of right child of grandparend
    #right rotate parent
    if node == (node.parent).right and (node.parent == grandp.left) :
        node.parent=rotate_left(node.parent)
        node = node.left

        #if current node is rigt child of left child of grandparend
        #left rotate parent
    elif node == (node.parent).left and node.parent == grandp.right:
        node.parent=rotate_right(node.parent)
        node = node.right

    nodeRotation(node)  #else tree in LL and RR case

#in this function the case of left child of left subtree and right child of right
# is solved make making left roatation to right subtree and left rotation fo right subtree
def nodeRotation(node):
   #print node.data
   grandp = grandparent(node)       #geting grand parent
   (node.parent).color = 'b'        #set parent to black
   grandp.color = 'r'               #grand parent to red

   if node == (node.parent).left:   # if node is left child
        rotate_right(grandp)        #right rotate tree
   else:
     #    print 'must be here'
       #  print grandp.data
         rotate_left(grandp)        #left rotate  tree
    #     print 'after',node.data















def delete(root,node):
    '''delete
    deletion from red black tree is same from BST but after deletion we have check redblack tree condition
    deletion from BST is done my recusive call so we can add the fixing condition of redblack tree to delete
    function without making a new function call
    '''

    if node<root.data:              #if node is less the root then node will be deleted from left subtree
        leftnode=delete(root.left,node)
        root.left=leftnode

    elif node > root.data:          #if node is greater then root the node to be deleted will be in right subtree
        rightnode=delete(root.right,node)
        root.right=rightnode


    #else if root is same node then there are two main condition for deletion
    #case 1
    #if root == node and its left and right subtree is not Node
    #find the node with with minimum will in right subtree and replay with with root
    #node in the right subtree find that node and delete from tree
    elif node==root.data and(root.left!=None and root.right!=None):
        print "right",root.data
        minnode=min(root.right)
        root.data=(minnode.data)
        delnode=delete(root.right,minnode.data)
        root.right=delnode

    #case 1
    #if one of both subtree of root is Node
    #this is simple case if deletion replace root with subtree or None
    else:
        deletenode=root         #get pointer of root node
        if(root.right==None):       #if right subtree is Node replace root with left subtree
        #   print "\nif",root.data
           newnode=root.left

           if (root.color == 'b'):
                if newnode!=None and newnode.color == 'r':
                    (root.left).color='b'
                else:
                    delete_case1(root);
           root=root.left
       #    print 'root', root

        elif root.left==None:           #else replace with right subtree
           newnode=root.right
           if (root.color == 'b'):
                if newnode!=None and newnode.color == 'r':
                    (root.right).color='b'
                else:
                    delete_case1(root)
           root=root.right
        del deletenode
   # if root !=None:
    #   print 'here is ' ,root.data
       # pass     isLeafNode(root)    #validation red black tree
    return root

#function for finding sibling
def sibling(node):

 if node == (node.parent).left:         #if current node is left
     return (node.parent).right         #return right node
 else:
     return (node.parent).left          # return left node

def leafNode(root):

    if root.left==None and root.right ==None:
        return True
    return False



def delete_case1(node ):

    if node.parent != None:
        delete_case2(node)

def delete_case2( node):

    siblng = sibling(node)

    if (siblng.color == 'r'):
        (node.parent).color = 'r'
        siblng.color = 'b'
        if (node == (node.parent).left):
            rotate_left(node.parent)
        else:
            rotate_right(node.parent)

    delete_case3(node)

def delete_case3(node):

    sbling = sibling(node)

    if (node.parent).color == 'b' and (sbling.color == 'b') and (sbling.left).color == 'b' and (sbling.right).color == 'b':
        sbling.color = 'r'
        delete_case1(node.parent)
    else:
       # print "parent is red"
        delete_case4(node)


def delete_case4(node ):

    sblng= sibling(node)

    if (node.parent).color == 'r' and sblng.color == 'b' and (sblng.left).color == 'b' and (sblng.right).color == 'b':

        sblng.color ='r'
        (node.parent).color = 'b'
    else:
        delete_case5(node)



def delete_case5(node ):
    sbling = sibling(node)
    if sbling.color == 'b':
        if sbling.right!=None and node == (node.parent).left and (sbling.right).color == 'b' and (sbling.left).color == 'r':

            sbling.color = 'r'
            (sbling.left).color = 'b'
            rotate_right(sbling)

        elif node == (node.parent).right and  (sbling.left).color == 'b' and (sbling.right).color == 'r':
            sbling.color = 'r'
            (sbling.right).color = 'b'
            rotate_left(sbling)

    delete_case6(node)

def delete_case6(node ):
    siblng = sibling(node)
    print "\nthis is wi "
    siblng.color = (node.parent).color;
    (node.parent).color = 'b'
    #print (node.parent).data,siblng.data
    if node == (node.parent).left:
        if siblng.right==None:
            (node.parent).right=rotate_right(siblng)
        #(siblng.right).color = 'b'
        siblng=(node.parent).right
        print siblng.data,(siblng.parent).data
        grand=grandparent(siblng)
        if grand!=None:
            if node.parent==grand.left:

                grand.left=rotate_left(node.parent)
            else:
                grand.right=rotate_left(node.parent)
        print ((node.parent).parent).data,(grand.left).data
        print 'check for updation '
        sortTree(grand)
        print ''
    else :
        (siblng.left).color = 'b'
        rotate_right(node.parent)
#Have you created bots using Python













def sortTree(node):
    if node !=None:
        sortTree(node.left)
        print node.data,node.color,
        sortTree(node.right)






if __name__ == '__main__':
    root=tree()
    root.data=14
    root.parent=None;
    root.color='b'
    root=insert(root,15)
    root=insert(root,6)
    root=insert(root,5)
    root=insert(root,8)
    root=insert(root,7)
    print ''
    delete(root,5)
   # root=insert(root,8)
    #root=insert(root,-11)
    #sortTree(root)
    sortTree(root)