Удаление бинарного дерева поиска в Python Рекурсивное

Question

Я знаю, что этот вопрос задавался сотни раз, но я не смог найти вопрос, точно похожий на мою реализацию бинарных деревьев поиска. Я реализовал базовый класс бинарного дерева поиска в Python c; единственная функция, которая в данный момент не завершена, это функция удаления. Я понимаю алгоритм, как это делается, и три разных случая удаления. Единственное ограничение, которое у меня есть, заключается в том, что я не хочу использовать родительские указатели, и я не уверен, как отслеживать предыдущий узел, чтобы я мог установить его соответствующим образом на основе удаления.

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

Я не хочу использовать родительские указатели для каждого узла в этой функции удаления

    def delete(self, value):
        if self.root:
            self.__delete(value, self.root)

    def __delete(self, value, curr_node):
        #How do I keep track of previous (parent) node here?
        if curr_node:
            if value < curr_node.value:
                self.__delete(value, curr_node.left)
            elif value > curr_node.value:
                self.__delete(value, curr_node.right)
            elif value == curr_node.value:
                #Case 1: Node is leaf (no children)
                #Case 2: Node has one child: the parent node has its child updated to the deleted node's children
                #Case 3: Node has two children 
                pass

Полный код

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

    def __str__(self):
        return str(self.value)

class BST:
    def __init__(self):
        self.root = None

    def insert(self, value):        
        if not self.root:
            self.root = Node(value)
        else:
            self.__insert(value, self.root)

    def __insert(self, value, curr_node):
        if value < curr_node.value:
            if not curr_node.left:
                curr_node.left = Node(value)
            else:
                self.__insert(value, curr_node.left)
        elif value > curr_node.value:
            if not curr_node.right:
                curr_node.right = Node(value)
            else:
                self.__insert(value, curr_node.right)
        else:
            print("Node already exists!")

    def lookup(self, value):
        if value == self.root.value:
            return self.root
        else:
            self.__lookup(value, self.root)

    def __lookup(self, value, curr_node):
        if value < curr_node.value:
            if value == curr_node.left.value:
                return curr_node.left
            else:
                self.__lookup(value, curr_node.left)
        elif value > curr_node.value:
            if value == curr_node.right.value:
                return curr_node.right
            else:
                self.__lookup(value, curr_node.right)
        else:
            print("Value doesn't exist!")

    def height(self):
        if not self.root:
            return 0
        else:
            return self.__height(self.root)

    def __height(self, curr_node):
        if not curr_node:
            return 0 
        return 1 + max(self.__height(curr_node.left), self.__height(curr_node.right))

    def min_value(self):
        if self.root:
            return self.__min_value(self.root)

    def __min_value(self, curr_node):
        if not curr_node.left:
            return curr_node

        return self.__min_value(curr_node.left)

    def max_value(self):
        if self.root:
            return self.__max_value(self.root)

    def __max_value(self, curr_node):
        if not curr_node.right:
            return curr_node
        return self.__max_value(curr_node.right)

    def count_nodes(self):
        if not self.root: 
            return 0 
        else:
            return self.__count_nodes(self.root)

    def __count_nodes(self, curr_node):
        if not curr_node:
            return 0 

        return 1 + self.__count_nodes(curr_node.left) + self.__count_nodes(curr_node.right)

    def inorder_traversal(self):
        if self.root:
            return self.__inorder_traversal(self.root)

    def __inorder_traversal(self, curr_node):
        path = []

        if curr_node:
            path.extend(self.__inorder_traversal(curr_node.left))
            path.append(curr_node.value)
            path.extend(self.__inorder_traversal(curr_node.right))

        return path

    def __num_children(self, curr_node):
        if not curr_node.left and not curr_node.right:
            return 0
        elif curr_node.right or curr_node.left:
            return 1
        elif curr_node.right and curr_node.left:
            return 2

    def delete(self, value):
        if self.root:
            self.__delete(value, self.root)

    def __delete(self, value, curr_node):
        #How do I keep track of previous (parent) node here?
        if curr_node:
            if value < curr_node.value:
                self.__delete(value, curr_node.left)
            elif value > curr_node.value:
                self.__delete(value, curr_node.right)
            elif value == curr_node.value:
                #Case 1: Node is leaf (no children)
                #Case 2: Node has one child: the parent node has its child updated to the deleted node's children
                #Case 3: Node has two children 
                pass