Derevo

[kostyria]

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

class BinarySearchTree:
def init(self):
self.root = None

def add_list(self, l):
    self.root = self.add_data(l, 0, len(l)-1)

def add_data(self, l, left, right):
    if left > right:
        return None

    mid = (left + right) // 2
    node = Node(l[mid])

    node.left = self.add_data(l, left, mid-1)
    if node.left is not None:
        node.left.parent = node

    node.right = self.add_data(l, mid+1, right)
    if node.right is not None:
        node.right.parent = node

    return node

def find(self, value):
    if self.root.value is None:
        return False
    
    if self.root.value == value:
        return True
    
    node = self.find_node(self.root, value)
    if node is None:
        return False
    
    return True

def find_node(self, cn, value):
    if cn is None:
        return None
    if cn.value == value:
        return cn
    if cn.value > value:
        res = self.find_node(cn.left, value)
        return res
    else:
        res = self.find_node(cn.right, value)
        return res
    
def find_min(self):
    node = self.find_min_node(self.root)
    return node.value

def find_min_node(self, cn):
    if cn.left is None:
        return cn
    node = self.find_min_node(cn.left)
    return node

def find_max(self):
    node = self.find_max_node(self.root)
    return node.value

def find_max_node(self, cn):
    if cn.right is None:
        return cn
    node = self.find_max_node(cn.right)
    return node

def delete(self, value):
    if (self.root.left is None and
            self.root.right is None and
            self.root.value == value):
        self.root.value = None
        return

    if (self.root.left is not None and
           self.root.right is None and
           self.root.value == value):
        self.root = self.root.left
        self.root.parent = None
        return

    if (self.root.left is None and
           self.root.right is not None and
           self.root.value == value):
        self.root = self.root.right
        self.root.parent = None
        return

    node = self.find_node(self.root, value)
    if node is None:
        raise Exception('Не могу найти узел для удаления')
    self.delete_data(node)

def delete_data(self, node):
    if (node.left is None and node.right is None):
        if node.parent.left == node:
            node.parent.left = None
        else:
            node.parent.right = None
        return
    
    if (node.left is not None and node.right is None):
        if node.parent.left == node:
            node.parent.left = node.left
        else:
            node.parent.right = node.left
        return

    if (node.left is None and node.right is not None):
        if node.parent.left == node:
            node.parent.left = node.right
        else:
            node.parent.right = node.right
        return
       
    if (node.left is not None and node.right is not None):
        if node.parent is None:
            self.root = self.find_min_node(node.right)
            self.root.left = node.left
            self.root.right = node.right
            return
        min_node_of_right = self.find_min_node(node.right)
        min_node_of_right.left = node.left
        if node.parent.left == node:
            node.parent.left = min_node_of_right
        else:
            node.parent.right = min_node_of_right
        return
    raise Exception('Что-то пощло не так. Не могу удалить узел')
    
def print_tree(self, node, level=0):
    if node is not None:
        print(' ' * 4 * level + f'- {node.value}')
        self.print_tree(node.left, level + 1)
        self.print_tree(node.right, level + 1)

nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]
bst = BinarySearchTree()
bst.add_list(nums)
bst.print_tree(bst.root)
bst.delete(8)
bst.print_tree(bst.root)