Как дерево бинарного поиска Python обрабатывает удаление узла с обоими дочерними элементами? - PullRequest
Новая
       25

Как дерево бинарного поиска Python обрабатывает удаление узла с обоими дочерними элементами?

0 голосов
/ 23 января 2019

Если я правильно понял, при удалении узла, у которого есть оба потомка, мы можем переключить его с его преемником (у которого есть следующее большее значение в дереве).

В следующем коде, который направлен на удаление наследника. Я думаю, что это не удаляет преемника, но также может быть одной из сторон преемника. 

def spliceOut(self):
  if self.isLeaf():
        if self.isLeftChild():
               self.parent.leftChild = None
        else:
               self.parent.rightChild = None
    elif self.hasAnyChildren(): # Leaves out the hasBothChildren situation?
        if self.hasLeftChild():
               if self.isLeftChild():
                  self.parent.leftChild = self.leftChild
               else:
                  self.parent.rightChild = self.leftChild
               self.leftChild.parent = self.parent
        else:
               if self.isLeftChild():
                  self.parent.leftChild = self.rightChild
               else:
                  self.parent.rightChild = self.rightChild
               self.rightChild.parent = self.parent

Это код из Решение проблем с помощью алгоритмов и структур данных с использованием дерева поиска Python.

Соответствующий код: 

if currentNode.hasBothChildren():
    succ = currentNode.findSuccessor()
    succ.spliceOut()
    currentNode.key = succ.key
    currentNode.payload = succ.payload
...