<reponame>jeli-t/algorithms
# binary search tree
# author: D1N3SHh
# https://github.com/D1N3SHh/algorithms


class Red_black_tree():
    def __init__(self):
        self.nil = Node(0, 'black', None, None)
        self.root = self.nil
 

    def __repr__(self):
        return str(self.root)

    def left_rotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.nil:
            y.left.parent = x
        y.parent = x.parent
        if x.parent == self.nil:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else: x.parent.right = y
        x.left = x
        x.parent = y

    def right_rotate(self, x):
        y = x.left
        x.left = y.right
        if y.right != self.nil:
            y.right.parent = x
        y.parent = x.parent
        if x.parent == self.nil:
            self.root = y
        elif x == x.parent.right:
            x.parent.right = y
        else: x.parent.left = y
        x.right = x
        x.parent = y

    def insert(self, z):
        y = self.nil
        x = self.root
        while x != self.nil:
            y = x
            if z.key < x.key:
                x = x.left
            else: x = x.right
        z.parent = y
        if y == self.nil:
            self.root = z
        elif z.key < y.key or y.key == None:
            y.left = z
        else: y.right = z
        z.left = self.nil
        z.right = self.nil
        z.color = 'red'
        self.insert_fixup(z)

    def insert_fixup(self, z):
        while z != self.root and z.parent.color == 'red':
            if z.parent == z.parent.parent.left:
                y = z.parent.parent.right
                if y.color == 'red':
                    z.parent.color = 'black'
                    y.color = 'black'
                    z.parent.parent.color = 'red'
                    z = z.parent.parent
                else:
                    if z == z.parent.right:
                        z = z.parent
                        self.left_rotate(z)
                    z.parent.color = 'black'                
                    z.parent.parent.color = 'red'
                    self.right_rotate(z.parent.parent)
            else:
                y = z.parent.parent.left
                if y.color == 'red':
                    z.parent.color = 'black'
                    y.color = 'black'
                    z.parent.parent.color = 'red'
                    z = z.parent.parent
                else:
                    if z == z.parent.left:
                        z = z.parent
                        self.right_rotate(z)
                    z.parent.color = 'black'
                    z.parent.parent.color = 'red'
                    self.left_rotate(z.parent.parent)
        self.root.color = 'black'

    def transplant(self, u, v):
        if u.parent == self.nil:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else: u.parent.right = v
        v.parent = u.parent

    def delete(self, z):
        y = z
        y_original_color = y.color
        if z.left == self.nil:
            x = z.right
            self.transplant(z, z.right)
        elif z.right == self.nil:
            x = z.left
            self.transplant(z, z.left)
        else:
            y = self.minimum(z.right)
            y_original_color = y.color
            x = y.right
            if y.parent == z:
                x.parent = y
            else:
                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
            y.color = z.color
        if y_original_color == 'black':
            self.delete_fixup(x)

    def delete_fixup(self, x):
        while x != self.root and x.color == 'black':
            if x == x.parent.left:
                w = x.parent.right
                if w.color == 'red':
                    w.color = 'black'
                    x.parent.color = 'red'
                    self.left_rotate(x.parent)
                    w = x.parent.right
                if w.left.color == 'black' and w.right.color == 'black':
                    w.color = 'red'
                    x = x.parent
                else:
                    if w.right.color == 'black':
                        w.left.color = 'black'
                        w.color = 'red'
                        self.right_rotate(w)
                        w = x.parent.right
                    w.color = x.parent.color
                    x.parent.color = 'black'
                    w.right.color = 'black'
                    self.left_rotate(x.parent)
                    x = self.root
            else:
                w = x.parent.left
                if w.color == 'red':
                    w.color = 'black'
                    x.parent.color = 'red'
                    self.right_rotate(x.parent)
                    w = x.parent.left
                if w.right.color == 'black' and w.left.color == 'black':
                    w.color = 'red'
                    x = x.parent
                else:
                    if w.left.color == 'black':
                        w.right.color = 'black'
                        w.color = 'red'
                        self.left_rotate(w)
                        w = x.parent.left
                    w.color = x.parent.color
                    x.parent.color = 'black'
                    w.left.color = 'black'
                    self.right_rotate(x.parent)
                    x = self.root
        x.color = 'black'

    def minimum(self, x):
        while x.left.left != None:
            x = x.left
        return x.key

    def maximum(self, x):
        while x.right.right != None:
            x = x.right
        return x.key 

    def search(self, x, key):
        if x == None or key == x.key:
            return x
        if key < x.key:
            return self.search(x.left, key)
        else: return self.search(x.right, key)


class Node():
    def __init__(self, key, color = 'red', parent = None, left = None, right = None):
        self.key = key
        self.color = color
        self.parent = parent
        self.left = left
        self.right = right

    def __repr__(self) -> str:
        return '{|%s%s|:%s,%s}' % (self.color, self.key, self.left, self.right)


def example_usage():
    rb_tree = Red_black_tree()
    node_1 = Node(6)            #          6
    node_2 = Node(4)            #        /   \
    node_3 = Node(8)            #       4     8
    node_4 = Node(2)            #      /
    rb_tree.insert(node_1)      #     2
    rb_tree.insert(node_2)
    rb_tree.insert(node_3)
    rb_tree.insert(node_4)
    print('Tree text reprezentation:', rb_tree)
    print('Searching for key = 4:', rb_tree.search(rb_tree.root, 4))
    print('Minimum:', rb_tree.minimum(rb_tree.root))
    print('Maksimum:', rb_tree.maximum(rb_tree.root))
    rb_tree.delete(node_2)
    print('Tree text reprezentation after removing node 2 (key=4):', rb_tree)

    
if __name__ == "__main__":
    example_usage() # run an example on start
# binary search tree
# author: D1N3SHh
# https://github.com/D1N3SHh/algorithms


class Red_black_tree():
    def __init__(self):
        self.nil = Node(0, 'black', None, None)
        self.root = self.nil
 

    def __repr__(self):
        return str(self.root)

    def left_rotate(self, x):
        y = x.right
        x.right = y.left
        if y.left != self.nil:
            y.left.parent = x
        y.parent = x.parent
        if x.parent == self.nil:
            self.root = y
        elif x == x.parent.left:
            x.parent.left = y
        else: x.parent.right = y
        x.left = x
        x.parent = y

    def right_rotate(self, x):
        y = x.left
        x.left = y.right
        if y.right != self.nil:
            y.right.parent = x
        y.parent = x.parent
        if x.parent == self.nil:
            self.root = y
        elif x == x.parent.right:
            x.parent.right = y
        else: x.parent.left = y
        x.right = x
        x.parent = y

    def insert(self, z):
        y = self.nil
        x = self.root
        while x != self.nil:
            y = x
            if z.key < x.key:
                x = x.left
            else: x = x.right
        z.parent = y
        if y == self.nil:
            self.root = z
        elif z.key < y.key or y.key == None:
            y.left = z
        else: y.right = z
        z.left = self.nil
        z.right = self.nil
        z.color = 'red'
        self.insert_fixup(z)

    def insert_fixup(self, z):
        while z != self.root and z.parent.color == 'red':
            if z.parent == z.parent.parent.left:
                y = z.parent.parent.right
                if y.color == 'red':
                    z.parent.color = 'black'
                    y.color = 'black'
                    z.parent.parent.color = 'red'
                    z = z.parent.parent
                else:
                    if z == z.parent.right:
                        z = z.parent
                        self.left_rotate(z)
                    z.parent.color = 'black'                
                    z.parent.parent.color = 'red'
                    self.right_rotate(z.parent.parent)
            else:
                y = z.parent.parent.left
                if y.color == 'red':
                    z.parent.color = 'black'
                    y.color = 'black'
                    z.parent.parent.color = 'red'
                    z = z.parent.parent
                else:
                    if z == z.parent.left:
                        z = z.parent
                        self.right_rotate(z)
                    z.parent.color = 'black'
                    z.parent.parent.color = 'red'
                    self.left_rotate(z.parent.parent)
        self.root.color = 'black'

    def transplant(self, u, v):
        if u.parent == self.nil:
            self.root = v
        elif u == u.parent.left:
            u.parent.left = v
        else: u.parent.right = v
        v.parent = u.parent

    def delete(self, z):
        y = z
        y_original_color = y.color
        if z.left == self.nil:
            x = z.right
            self.transplant(z, z.right)
        elif z.right == self.nil:
            x = z.left
            self.transplant(z, z.left)
        else:
            y = self.minimum(z.right)
            y_original_color = y.color
            x = y.right
            if y.parent == z:
                x.parent = y
            else:
                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
            y.color = z.color
        if y_original_color == 'black':
            self.delete_fixup(x)

    def delete_fixup(self, x):
        while x != self.root and x.color == 'black':
            if x == x.parent.left:
                w = x.parent.right
                if w.color == 'red':
                    w.color = 'black'
                    x.parent.color = 'red'
                    self.left_rotate(x.parent)
                    w = x.parent.right
                if w.left.color == 'black' and w.right.color == 'black':
                    w.color = 'red'
                    x = x.parent
                else:
                    if w.right.color == 'black':
                        w.left.color = 'black'
                        w.color = 'red'
                        self.right_rotate(w)
                        w = x.parent.right
                    w.color = x.parent.color
                    x.parent.color = 'black'
                    w.right.color = 'black'
                    self.left_rotate(x.parent)
                    x = self.root
            else:
                w = x.parent.left
                if w.color == 'red':
                    w.color = 'black'
                    x.parent.color = 'red'
                    self.right_rotate(x.parent)
                    w = x.parent.left
                if w.right.color == 'black' and w.left.color == 'black':
                    w.color = 'red'
                    x = x.parent
                else:
                    if w.left.color == 'black':
                        w.right.color = 'black'
                        w.color = 'red'
                        self.left_rotate(w)
                        w = x.parent.left
                    w.color = x.parent.color
                    x.parent.color = 'black'
                    w.left.color = 'black'
                    self.right_rotate(x.parent)
                    x = self.root
        x.color = 'black'

    def minimum(self, x):
        while x.left.left != None:
            x = x.left
        return x.key

    def maximum(self, x):
        while x.right.right != None:
            x = x.right
        return x.key 

    def search(self, x, key):
        if x == None or key == x.key:
            return x
        if key < x.key:
            return self.search(x.left, key)
        else: return self.search(x.right, key)


class Node():
    def __init__(self, key, color = 'red', parent = None, left = None, right = None):
        self.key = key
        self.color = color
        self.parent = parent
        self.left = left
        self.right = right

    def __repr__(self) -> str:
        return '{|%s%s|:%s,%s}' % (self.color, self.key, self.left, self.right)


def example_usage():
    rb_tree = Red_black_tree()
    node_1 = Node(6)            #          6
    node_2 = Node(4)            #        /   \
    node_3 = Node(8)            #       4     8
    node_4 = Node(2)            #      /
    rb_tree.insert(node_1)      #     2
    rb_tree.insert(node_2)
    rb_tree.insert(node_3)
    rb_tree.insert(node_4)
    print('Tree text reprezentation:', rb_tree)
    print('Searching for key = 4:', rb_tree.search(rb_tree.root, 4))
    print('Minimum:', rb_tree.minimum(rb_tree.root))
    print('Maksimum:', rb_tree.maximum(rb_tree.root))
    rb_tree.delete(node_2)
    print('Tree text reprezentation after removing node 2 (key=4):', rb_tree)

    
if __name__ == "__main__":
    example_usage() # run an example on start
# binary search tree # author: D1N3SHh # https://github.com/D1N3SHh/algorithms #          6 #        /   \ #       4     8 #      / #     2 # run an example on start