domains
avl=avl(bt,integer)
bt=bt(avl,char,avl);nil

predicates
nondeterm run(avl)
nondeterm insertA(char,avl,avl)domains
bctt = tree(char,bctt,bctt); nil

predicates
nondeterm del_min (char,bctt,bctt)
nondeterm del_mem_tree (char,bctt,bctt)
nondeterm modif_tree(bctt,bctt)
nondeterm max_tree(char,bctt)
nondeterm run(bctt)
nondeterm do(char,bctt,bctt)
nondeterm member(bctt,char)
create_tree(bctt,bctt)
insert(char,bctt,bctt)
write_tree(bctt)
height(bctt,integer)
max(integer,integer,integer)

clauses
run(Tree) :- nl,
    write("***ENTER***\n"),
    write("-1 to update\n"),
    write("-2 to show TREE\n"),
    write("-3 to find max element\n"),
    write("-4 to check if character is tree member\n"),
    write("-5 to show height of tree\n"),
    write("-6 to delete element\n"),
    write("-0 to EXIT\n"),
    write(">_"),
    readchar(C),write(C),nl,
    do(C,Tree,NewTree),
    run(NewTree).

do('1',Tree,NewTree) :-
    write("Enter char or ? to END\n\n"),
    create_tree(Tree,NewTree).

do('2',Tree,Tree) :-
    nl,write_tree(Tree),nl,
    write(Tree),nl.

do('3',Tree,Tree) :- max_tree(MAX,Tree),write("\n",MAX,"\n").

do('4',Tree,Tree) :-
    write("\nEnter character: "),
    readchar(X),write(X),nl,write(X),nl,
    member(Tree,X),write(" is member of tree.\n");write(" is NOT member of tree.\n").

do('5',Tree,Tree) :-
    height(Tree,H),
    write("\nHeight is: ",H,".\n").

do('6',Tree,NewTree):-
    write("\nEnter character: "),
    modif_tree(Tree,NewTree).

do('0',_,nil) :- write("\nThat's all"), exit.

height(nil,0).
height(tree(_,Left,Right),H):-
    height(Left,HL),
    height(Right,HR),
    max(HL,HR,MH),H=MH+1.

max(X,Y,X):- X>=Y,!.
max(_,Y,Y).

modif_tree(T,NT):-
    readchar(C),nl,write(C),
    del_mem_tree(C,T,TT),nl,write(TT),
    modif_tree(TT,NT).
modif_tree(T,T).

del_mem_tree(X,tree(X,L,nil),L).
del_mem_tree(X,tree(X,nil,Right),Right).
del_mem_tree(X,tree(E,L,R),tree(E,NL,R)):-
    E>X,del_mem_tree(X,L,NL).
del_mem_tree(X,tree(E,L,R),tree(E,L,NR)):-
    X>E,del_mem_tree(X,R,NR).
del_mem_tree(X,tree(X,L,R),tree(E,L,NR))
    :-del_min(E,R,NR).

del_min(X,tree(X,nil,R),R).
del_min (X,tree(E,L,R),tree(E,Nl,R)):-
    del_min(X,L,Nl).

max_tree(E,tree(E,_,nil)):-!.
max_tree(MAX,tree(_,_,Right)) :-
    max_tree(MAX,Right).

member(tree(E,_,_),E) :- !.
member(tree(_,Left,_),E) :- member(Left,E).
member(tree(_,_,Right),E) :- member(Right,E).

create_tree(Tree,NewTree) :-
    readchar(C),C<>'?',!,
    write(C,","),
    insert(C,Tree,TempTree),
    create_tree(TempTree,NewTree).

create_tree(Tree,Tree).

insert(New,nil,tree(New,nil,nil)) :- !.

insert(New,tree(E,Left,Right),tree(E,NewLeft,Right)) :-
    New < E,!,
    insert(New,Left,NewLeft).

insert(New,tree(E,Left,Right),tree(E,Left,NewRight)) :-
    insert(New,Right,NewRight).

write_tree(nil).

write_tree(tree(E,Left,Right)) :-
    write_tree(Left),
    write(E," "),
    write_tree(Right).

goal
run(nil).
nondeterm unionA(avl,char,avl,char,avl,avl)
max(integer,integer,integer)

clauses
run(A):-readchar(C),C<>'.',insertA(C,A,An),write(An),nl,run(An);write("\nThat's it\n").

insertA(New,avl(nil,0),avl(bt(avl(nil,0),New,avl(nil,0)),1)).
insertA(E,avl(bt(Left,E,Right),H),avl(bt(Left,E,Right),H)).

insertA(New,avl(bt(Left,E,Right),_),NewA):-
    New < E,
    insertA(New,Left,avl(bt(LT,X,RT),_)),
    unionA(LT,X,RT,E,Right,NewA).

insertA(New,avl(bt(Left,E,Right),_),NewA):-
    New > E,
    insertA(New,Right,avl(bt(LT,X,RT),_)),
    unionA(Left,E,LT,X,RT,NewA).

unionA(avl(T1,H1),A,avl(bt(L2,C,R2),H2),B,avl(T3,H3),avl(bt(avl(bt(avl(T1,H1),A,L2),HA),C,avl(bt(R2,B,avl(T3,H3)),HB)),HC)):-
    H2>H1,H2>H3,
    HA=H1+1,HB=H3+1,HC=HA+1.

unionA(avl(T1,H1),A,avl(T2,H2),B,avl(T3,H3),avl(bt(avl(T1,H1),A,avl(bt(avl(T2,H2),B,avl(T3,H3)),HB)),HA)):-
    H1>=H2,H1>=H3,
    max(H2,H3,Hb), max(H1,HB,HA).

unionA(avl(T1,H1),A,avl(T2,H2),B,avl(T3,H3),avl(bt(avl(bt(avl(T1,H1),A,avl(T2,H2)),HA),B,avl(T3,H3)),HB)):-
    H3>=H2,H3>=H1,
    max(H1,H2,HA),max(HA,H3,HB).

max(X,Y,Z) :- X>Y, !, Z=X+1.
max(X,Y,Z) :- X<=Y,!, Z=Y+1.


goal
run(avl(nil,0)).