Method __fixNodeRemove

recipes/Python/577898_23_Tree/recipe-577898.py:288–384

Fix deletion

(self, node, parent = -1)

            node1.values[idx1], node2.values[idx2] = node2.values[idx2], node1.values[idx1]

    def __fixNodeRemove(self, node, parent = -1):
        
        """ Fix deletion """
      
        if node.isEmptyNode():

            if node is not self.root:

                if parent == -1:
                    parent = node.parent

                if node.isEmptyNode() or not node.isConsistent():

                    lS, lCnt, rS, rCnt = self.__getSiblings(node)
                    rSS, lSS = self.__getRightSibling(rS), self.__getLeftSibling(lS)

                    redistribute = True
                    
                    if (rS or lS) is not None:
                        if   rCnt == 2 or (rCnt == 1 and rSS != None and rSS.valcnt == 2):
                            sib = rS
                        elif lCnt == 2 or (lCnt == 1 and lSS != None and lSS.valcnt == 2):
                            sib = lS
                        elif lCnt == 1:
                            sib, redistribute = lS, False
                        elif rCnt == 1:
                            sib, redistribute = rS, False

                    if redistribute:
                        # case 1: redistribute
                        # left and right case
                        if parent.valcnt == 1:
                            if node == parent.getLink(0):
                                parent_val, sib_val = parent.values[0], sib.values[0]
                                child = sib.chooseChild(sib_val - 1)
                            elif node == parent.getLink(1):                                
                                parent_val, sib_val = parent.values[parent.valcnt - 1], sib.values[sib.valcnt - 1]
                                child = sib.chooseChild(sib_val + 1)  
                        else:
                            if sib == parent.getLink(1):
                                # left
                                if node == parent.getLink(0):
                                    parent_val, sib_val = parent.values[0], sib.values[0]
                                    child = sib.chooseChild(sib_val - 1)
                                # right
                                elif node == parent.getLink(2):
                                    parent_val, sib_val = parent.values[parent.valcnt - 1], sib.values[sib.valcnt - 1]
                                    child = sib.chooseChild(sib_val + 1)
                            # middle
                            elif sib == parent.getLink(2):
                                parent_val, sib_val = parent.values[parent.valcnt - 1], sib.values[0]
                                child = sib.chooseChild(sib_val - 1)
                            elif sib == parent.getLink(0):
                                parent_val, sib_val = parent.values[0], sib.values[sib.valcnt - 1]
                                child = sib.chooseChild(sib_val + 1)

                        node.insertValue(parent_val)
                        parent.removeValue(parent_val)