% nacteni:
/* ['2.7_15.pl']. */

% ve SWISH muze hlasit chybu "No permission to call sandboxed `tab(_4808)'"
% reseni viz https://github.com/SWI-Prolog/swish/issues/119

addleaf(nil,X,t(nil,X,nil)).
addleaf(t(Left,X,   Right),X ,t(Left ,X,   Right)).
addleaf(t(Left,Root,Right),X ,t(Left1,Root,Right))  :- Root>X,addleaf(Left, X, Left1).
addleaf(t(Left ,Root,Right),X,t(Left ,Root,Right1)) :- Root<X,addleaf(Right,X,Right1).

delleaf( t( nil ,X,Right),X,Right).
delleaf( t(Left ,X, nil ),X,Left ).
delleaf( t(Left ,X,Right),X,t(Left ,Y,Right1)) :- delmin(Right,Y,Right1).
delleaf( t(Left ,Root,Right),X,t(Left1,Root,Right)) :- X<Root,delleaf(Left,X,Left1).
delleaf( t(Left ,Root,Right),X,t(Left ,Root,Right1)) :- X>Root,delleaf(Right,X,Right1).
delmin(t( nil ,Y,R),Y,R).
delmin(t(Left ,Root,Right),Y,t(Left1,Root,Right)) :- delmin(Left,Y,Left1).


show(T) :- show2(T,0).
show2(nil,_).
show2(t(L,X,R),Indent) :- Ind2 is Indent+2,show2(R,Ind2),tab(Indent),
                          write(X),nl,show2(L,Ind2).

% demonstracni vypis

  % abychom se vyhli varovanim "Redefined static procedure ..."
:- dynamic
       start/0.
       
start:- 
    write('Binarni stromy'),nl,
    write('--------------'),nl, nl,
    write('Vytvoreni stromu: '),nl,
    write('addleaf(nil ,6,T),addleaf(T,8,T1), addleaf(T1,2,T2),'),nl, 
    write('addleaf(T2,4,T3), addleaf(T3,1,T4), show(T4) :'),nl,
    addleaf(nil ,6,T),addleaf(T,8,T1), addleaf(T1,2,T2), addleaf(T2,4,T3), addleaf(T3,1,T4),
    show(T4),

    write('Smazani uzlu s hodnotou 8:'),nl,
    write('delleaf(T4, 8, T5), show(T5) :'),nl,
    delleaf(T4, 8, T5), show(T5),

    write('Smazani uzlu s hodnotou 2:'),nl,
    write('delleaf(T5, 2, T6), show(T6) :'),nl,
    delleaf(T5, 2, T6), show(T6).

?-start.

:- retractall(write_all_X/3).
:- retractall(start/0).

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

Vytvoreni stromu: 
addleaf(nil ,6,T),addleaf(T,8,T1), addleaf(T1,2,T2),
addleaf(T2,4,T3), addleaf(T3,1,T4), show(T4) :
  8
6
    4
  2
    1
Smazani uzlu s hodnotou 8:
delleaf(T4, 8, T5), show(T5) :
6
    4
  2
    1
Smazani uzlu s hodnotou 2:
delleaf(T5, 2, T6), show(T6) :
6
  4
    1

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

nil = None

def addleaf(tree, x):
    if tree == nil:
        return (nil, x, nil)
    left, root, right = tree
    if x == root:
        return tree
    if root > x:
        return (addleaf(left, x), root, right)
    else:
        return (left, root, addleaf(right, x))

def delleaf(tree, x):
    if tree == nil:
        return nil
    left, root, right = tree
    if x == root:
        if left == nil:
            return right
        if right == nil:
            return left
        right1, y = delmin(right)
        return (left, y, right1)
    if root > x:
        return (delleaf(left, x), root, right)
    else:
        return (left, root, delleaf(right, x))

def delmin(tree):
    if tree == nil:
        raise ValueError("delmin je treba volat nad neprazdnym stromem")
    left, root, right = tree
    if left == nil:
        return (right, root)
    left1, y = delmin(left)
    return ((left1, root, right), y)

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 = addleaf(nil, 6); T1 = addleaf(T, 8); T2 = addleaf(T1, 2); " +
          "T3 = addleaf(T2, 4); T4 = addleaf(T3, 1); show(T4) :")
    T = addleaf(nil, 6)
    T1 = addleaf(T, 8)
    T2 = addleaf(T1, 2)
    T3 = addleaf(T2, 4)
    T4 = addleaf(T3, 1)
    show(T4)

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

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

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

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

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

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