task_90.pr

DOMAINS
	bi_t = tree_b(bi_t, string, bi_t); nil
	i = integer
	
PREDICATES
	nondeterm main()
	nondeterm handle_input(bi_t, char)
	nondeterm find_subtree(bi_t, string, bi_t)
	nondeterm get_tree_height(bi_t, i)
	nondeterm delete_element(bi_t, string, bi_t)
	nondeterm migrate(bi_t, string, bi_t)
	nondeterm max(i, i, i)
	nondeterm write_tree(bi_t)
	nondeterm write_tree(bi_t, i)
	nondeterm tab(i)
	
CLAUSES
	main():-
		T=tree_b(tree_b(tree_b(tree_b(nil,"aa",nil),
			"ab",tree_b(tree_b(nil,"bb",nil),"bc",tree_b(nil,"cc",nil))),"cd",tree_b(nil,"dd",nil)),"de",tree_b(tree_b(nil,"ee",nil),"ef",tree_b(nil,"ff",nil))),
		write_tree(T),
		write("Operation code [h - height, d - delete] >> "), readchar(I), nl,
		handle_input(T, I),
		main().
		
	handle_input(T, I):-
		I='h',
		write("Element >> "), readln(E),
		find_subtree(T, E, S),
		get_tree_height(S, H),
		write("Height >> ", H, "\n==========\n").
		
	handle_input(T, I):-
		I='d',
		write("Element >> "), readln(E),
		delete_element(T, E, NewT),
		write("New tree >> \n"), write_tree(NewT), write("==========\n").
	
	find_subtree(tree_b(Left, E, Right), E, tree_b(Left, E, Right)):-!.
	
	find_subtree(tree_b(Left, E, Right), X, T):-
		find_subtree(Left, X, T).
		
	find_subtree(tree_b(Left, E, Right), X, T):-
		find_subtree(Right, X, T).
	
	delete_element(nil, _, nil).
	
	delete_element(tree_b(Left, E, Right), X, tree_b(NewLeft, E, Right)):-
		E>X,
		delete_element(Left, X, NewLeft).
		
	delete_element(tree_b(Left, E, Right), X, tree_b(Left, E, NewRight)):-
		E<X,
		delete_element(Right, X, NewRight).
		
	delete_element(tree_b(Left, X, nil), X, Left).
	
	delete_element(tree_b(nil, X, Right), X, Right).
	
	delete_element(tree_b(Left, X, Right), X, tree_b(Left, E, NewRight)):-
		migrate(Right, E, NewRight).
		
	migrate(tree_b(Left, E, Right), X, tree_b(NewLeft, E, Right)):-
		migrate(Left, X, NewLeft).
		
	migrate(tree_b(nil, X, Right), X, Right).
	
	get_tree_height(nil, 0).
	
	get_tree_height(tree_b(Left, E, Right), H):-
		get_tree_height(Left, H1),
		get_tree_height(Right, H2),
		max(H1, H2, H3),
		H=H3+1.
	
	max(A, B, R):-
		A>=B,
		R=A.
		
	max(A, B, B).
	
	write_tree(T):-
		write_tree(T, 0).
		
	write_tree(nil, _):-!.
	
	write_tree(tree_b(Left, E, Right), D):-
		NewD = D + 1,
		write_tree(Right, NewD),
		tab(D), write(E), nl,
		write_tree(Left, NewD).
		
	tab(0):-!.
	
	tab(D):-
		write("\t"),
		NewD = D - 1,
		tab(NewD).
GOAL
	main().