Метод удаления двоичного дерева поиска не работает

Вот BST, который я пытался реализовать, но метод удаления не удаляет узел с заданным значением. Я пытался сделать так:

  1. Сначала проверьте, есть ли у текущего узла (узел, который я хочу удалить) правильный дочерний элемент.

1.1) Если это не так, то я заменяю текущий узел его левым дочерним элементом.

1.2) И если у текущего узла есть правый дочерний элемент, то проверьте, есть ли у правого дочернего элемента текущего узла левый дочерний элемент

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

1.2.2) Если нет, то я заменяю текущий узел его правым дочерним элементом. Но код не удаляет выбранный узел. Где я сделал ошибку?

class BinarySearchTree:
    def __init__(self):
        self.root = None
    def insert(self,value):
        node = {'value':value,'left':None,'right':None}
        if self.root == None:
            self.root = node 
        else:
            
            current = self.root
            while True:
                if value > current['value']:
                    if current['right'] == None:
                        current['right'] = node
                        break
                    else:
                        current = current['right']
                else:
                    if current['left'] == None:
                        current['left'] = node
                        break
                    else:
                        current = current['left']
    def lookup(self,value):
        if self.root == None:
            return
        else:
            current = self.root
            while True:
                if value > current['value']:
                    if current['right'] == None:
                        return None
                    current = current['right']
                elif value < current['value']:
                    if current['left'] == None:
                        return None
                    current = current['left']
                else:
                    return current

    def remove(self,value):

        if not self.root:
            return False
        parent = None
        current = self.root
        while current:
            if value < current['value']:
                parent = current
                current = current['left']
            elif value > current['value']:
                parent = current
                current = current['right']
            elif value == current['value']:

                # 1)no right child
                if current['right'] == None:
                    if parent == None:
                        self.root = current['left']
                    else:
                        if current['value'] < parent['value']:
                            parent['left'] = current['left']
                        elif current['value'] > parent['value']:
                            parent['right'] = current['left']
                # 2) right child that doesnt have a left child
                elif current['right']['left'] == None:
                    current['right']['left'] = current['left']
                    if parent == None:
                        self.root= current['right']
                    else:
                        if parent['value'] > current['value']:
                            parent['left'] = current['right']
                        elif parent['value'] < current['value']:
                            parent['right'] = current['right']
                # 3)Right child that has a left child
                else:
                    #finding the right child's leftmost child
                    leftmost = current['right']['left']
                    leftmostParent = current['right']
                    while leftmost['left'] != None:
                        leftmostParent = leftmost
                        leftmost = leftmost['left']
                    leftmostParent['left'] = leftmost['right']
                    leftmost['left'] = current['left']
                    leftmost['right'] = current['right']

                    if parent == None:
                        self.root = leftmost
                    else:
                        if current['value'] < parent['value']:
                            parent['left'] = leftmost
                        elif current['value'] > parent['value']:
                            parent['right'] = leftmost
            return True   
                
    def get(self):
        my_bst = {
            'root':self.root,
        }
        return my_bst
        
      

bst = BinarySearchTree()
bst.insert(9)
bst.insert(4)
bst.insert(6)
bst.insert(20)
bst.insert(170)
bst.insert(15)
bst.insert(1)
bst.insert(150)
print(bst.remove(150))
print(bst.get())

person proger23    schedule 18.10.2020    source источник
comment
Пожалуйста, опубликуйте код, который печатает неправильный вывод, а также опубликуйте ожидаемый вывод.   -  person pts    schedule 18.10.2020


Ответы (1)


Ваш цикл while current: на самом деле никогда не зациклится, потому что вы return True в конце цикла. Я думаю, что отступ return True вправо сделает свое дело.

person Mark    schedule 18.10.2020