Tree.py

class NilNode:
    def __init__(self):
        self.value = None
        self.parent = None
        self.left = None
        self.right = None
NIL = NilNode()


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

    def leaf(self):
        return (self.left, self.right) == (NIL, NIL)

    def __str__(self):
        s =  f'Node:\n'
        s += f'  value: {self.value}\n'
        s += f'  parent: {self.parent.value}\n'
        s += f'  left: {self.left.value}\n'
        s += f'  right: {self.right.value}\n'
        s += f'  leaf: {self.leaf()}'
        return s


class Tree:
    def __init__(self, root):
        self.root = root

    def minimum(self, x=None):
        if x is None:
            x = self.root
        while not x.left == NIL:
            x = x.left
        return x

    def transPlant(self, u, v):
        if u.parent == NIL:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else:
            u.parent.right = v
        if not v == NIL:
            v.parent = u.parent

    def insert(self, z):
        if self.root == NIL:
            self.root = z
            return
        x = self.root
        while not x.leaf():
            if z.value < x.value:
                x = x.left
            else:
                x = x.right
        z.parent = x
        if z.value < x.value:
            x.left = z
        else:
            x.right = z

    def delete(self, z):
        if z.left == NIL:
            self.transPlant(z, z.right)
        elif z.right == NIL:
            self.transPlant(z, z.left)
        else:
            y = self.minimum(z.right)
            if not y.parent == z:
                self.transPlant(y, y.right)
                y.right = z.right
                y.right.parent = y
            self.transPlant(z, y)
            y.left = z.left
            y.left.parent = y



if __name__ == '__main__':
    node = Node(7)
    print(node)

    tree = Tree(root=node)
    inserted_node = Node(6)
    tree.insert(inserted_node)
    print(node)
    print(inserted_node)

    tree.delete(inserted_node)
    print(node)