def BVS_insert(tree, key):
    """Vlozi novy uzel s klicem 'key' do stromu 'tree'."""
    """
    Nejprve vyhledame misto, kde je jeho rodič, poté porovnáme s hodnotou rodiče a uzel uložíme
    na jemu příslušící místo.
    """
    node = Node()
    node.key = key

    x = tree.root
    tmp = None

    while x != None:
        tmp = x
        if x.key < key:
            x = x.right
        elif x.key > key:
            x = x.left

    node.parent = tmp

    if tmp == None:
        tree.root = node
    elif tmp.key > key:
        tmp.left = node
    else:
        tmp.right = node

    # Pozn - potřebujeme ukazatel na tento uzel!!! - MODIFIKACE
    return node


# Viz s220
def insert(tree, key):
    """Vlozi novy uzel s klicem 'key' do stromu 'tree'. Operace zachova
    korektni cerveno-cerny strom.

    Pozn:   Základ vkládání nového uzlu je stejný jako v BVS - proto adopce funkce BVS_insert -> modifikace na poslednim řádku
            Problém může nastat při obarvování uzlu -> dojde k porušení vlastností č-č stromu -> musime opravit

            Obarvujeme na červeno - černá výška je tedy stále platná,
                        - můžeme porušit 1. vlastnost (kořen nemusí být černý)
                        - můžeme porušit 3. vlastnost (můžeme mit 2 červené uzly spojené přímo hranou
                    - musíme použít korekci
    """
    node = BVS_insert(tree, key)
    node.color = Colors.red

    while node != tree.root and node.parent.color == Colors.red:
        if node.parent == node.parent.parent.left:
            d = node.parent.parent.right
            # Oproti pseudokodu na slidech je treba navic kontrolovat ještě, zda uzel není None type!!!
            if d != None and d.color == Colors.red:
                node.parent.color = Colors.black
                d.color = Colors.black
                node.parent.parent.color =  Colors.red
                node = node.parent.parent
            elif node == node.parent.right:
                node = node.parent
                rotate_left(tree, node)
            else:
                node.parent.color = Colors.black
                node.parent.parent.color = Colors.red
                rotate_right(tree, node.parent.parent)
        # Stejně jako první větev IF-podmínky, jen prohozené left a right
        else:
            d = node.parent.parent.left
            if d != None and d.color == Colors.red:
                node.parent.color = Colors.black
                d.color = Colors.black
                node.parent.parent.color = Colors.red
                node = node.parent.parent
            elif node == node.parent.left:
                node = node.parent
                rotate_right(tree, node)
            else:
                node.parent.color = Colors.black
                node.parent.parent.color = Colors.red
                rotate_left(tree, node.parent.parent)

    tree.root.color = Colors.black