UNIT insert_procedure;

INTERFACE
USES
	atomic_functions;
	
PROCEDURE insert (val : integer; VAR head : tree);

IMPLEMENTATION

PROCEDURE insert (val : integer; VAR head : tree);
	VAR back_current,leaf : tree;	
	
	(* Insertion d'un nouvel élément *)
		PROCEDURE inserer ( val : integer; VAR jumper, head, leaf : tree);
			
			PROCEDURE insert_over_NIL (val : integer; VAR jumper, leaf : tree);
				BEGIN
				new (jumper);
				jumper^.l_s := NIL;
				jumper^.r_s := NIL;
				jumper^.parent := NIL;
				jumper^.val := val;
				jumper^.hauteur := 0;
				END;

			PROCEDURE insert_left ( val : integer; VAR jumper, leaf : tree);
				BEGIN
				new ( leaf);
				leaf^.l_s := NIL;
				leaf^.r_s := NIL;
				leaf^.val := val;
				leaf^.hauteur := 0;
				leaf^.parent := jumper;
				jumper^.l_s := leaf;
				jumper := leaf;
				END;
		
			PROCEDURE insert_right ( val : integer; VAR jumper, leaf : tree);
				BEGIN
				new ( leaf);
				leaf^.l_s := NIL;
				leaf^.r_s := NIL;
				leaf^.val := val;
				leaf^.hauteur := 0;
				leaf^.parent := jumper;
				jumper^.r_s := leaf;
				jumper := leaf;
				END;	
		
			BEGIN
			IF is_empty (jumper) THEN
				insert_over_NIL (val, head, leaf)
			ELSE IF val > jumper^.val THEN
				insert_right (val, jumper, leaf)
			ELSE
				insert_left (val, jumper, leaf);
			END;
	(* *)
	(* trouver position où insérer :*)	
	PROCEDURE find_way (val : integer; head : tree; VAR step_back : tree);
		VAR current : tree;
		BEGIN
		new (step_back);
		new (current);
		step_back := NIL;
		current := head;
		while current <> NIL DO
			BEGIN
			step_back := current;
			IF val < current^.val THEN 
				current := left_son (current)
			ELSE
				current := right_son (current);
			END;
		END;
	(* *)
	BEGIN
	find_way (val,head, back_current);
	inserer (val, back_current, head, leaf);
	height_over_path (back_current);
	balance (back_current, head);
	writeln ('Racine: ', head^.val);
	END;
BEGIN
END.