#!/usr/bin/env python
# encoding=utf-8 (pep 0263)

nil = None

def add(tree, x):
    yield addroot(tree, x)
    if tree == nil:
        return
    left, y, right = tree
    if y > x:
        yield (add(left, x), y, right)
    else:
        yield (left, y, add(right, x))

def addroot(tree, x):
    if tree == nil:
        return (nil, x, nil)
    left, y, right = tree
    if y > x:
        left1, _, left2 = addroot(left, x)
        return (left1, x, (left2, y, right))
    if y < x:
        right1, _, right2 = addroot(right, x)
        return ((left, y, right1), x, right2)
    return tree

def del_(tree, x):
    if tree == nil:
        return
    for tree1 in delroot(tree, x):
        yield tree1
    left, y, right = tree
    if y > x:
        for left1 in del_(left, x):
            yield (left1, y, right)
    else:
        for right1 in del_(right, x):
            yield (left, y, right1)

def delroot(tree, x):
    if tree == nil:
        return
    tree_left, tree_y, tree_right = tree
    if tree_y != x:
        return
    if tree_left == nil and tree_right == nil:
        yield nil
    if tree_right != nil:
        left1 = tree_left
        left2, y, right = tree_right
        if y > x:
            for left in delroot((left1, x, left2), x):
                yield (left, y, right)
    if tree_left != nil:
        left, y, right1 = tree_left
        right2 = tree_right
        if y < x:
            for right in delroot((right1, x, right2), x):
                yield (left, y, right)
    yield tree

def show(tree):
    show2(tree, 0)

def show2(tree, indent):
    if tree == nil:
        return
    left, root, right = tree
    show2(right, indent+2)
    print("%s%s" % (" " * indent, root))
    show2(left, indent+2)

# demonstracni vypis
if __name__ == "__main__":
    print("Binarni stromy")
    print("--------------\n")
    print("Vytvoreni stromu:")
    print("T = next(add(nil, 6)); T1 = next(add(T, 8)); T2 = next(add(T1, 2)); " +
          "T3 = next(add(T2, 4)); T4 = next(add(T3, 1)); show(T4) :")
    T = next(add(nil, 6))
    T1 = next(add(T, 8))
    T2 = next(add(T1, 2))
    T3 = next(add(T2, 4))
    T4 = next(add(T3, 1))
    show(T4)

    print("\nSmazani uzlu s hodnotou 8:")
    print("T5 = next(del_(T4, 8)); show(T5) :")
    T5 = next(del_(T4, 8))
    show(T5)

    print("\nSmazani uzlu s hodnotou 2:")
    print("T6 = next(del_(T5, 2)); show(T6) :")
    T6 = next(del_(T5, 2))
    show(T6)

Binarni stromy
--------------

Vytvoreni stromu:
T = next(add(nil, 6)); T1 = next(add(T, 8)); T2 = next(add(T1, 2)); T3 = next(add(T2, 4)); T4 = next(add(T3, 1)); show(T4) :
    8
      6
  4
    2
1

Smazani uzlu s hodnotou 8:
T5 = next(del_(T4, 8)); show(T5) :
    6
  4
    2
1

Smazani uzlu s hodnotou 2:
T6 = next(del_(T5, 2)); show(T6) :
    6
  4
1