{ Renata Lara } { CSCI 3333.01 } { March 3, 1998 } { This program implements an AVL tree which inserts(and balances), } { deletes(and balances), finds, and prints elements in alphabetical order. } { ************************************************************************ } { PROCEDURE create_tree(var T : TreePtr); } { Function: will initialize tree to an empty state } { Precondition: tree does not already exists } { Postcondition: tree has been created and is empty } { Run Time: O(1) } { ************************************************************************ } { PROCEDURE destroy_tree(var T : TreePtr); } { Function: will initialize tree to an empty state } { Precondition: tree already exists } { Postcondition: tree has been destroyed and is empty } { Run Time: O(1) } { ************************************************************************ } { PROCEDURE left_rotation(var T : TreePtr); } { Function: performs a rotation between a node and its left child } { Precondition: tree exists and is not empty; this procedure is only called if an insertion is made into the left subtree of the left child of 'alpha' } { Postcondition: balanced tree with height of not more than 1 in difference between subtrees } { Run Time: O(1) } { ************************************************************************ } { PROCEDURE right_rotation(var T : TreePtr); } { Function: performs a rotation between a node and its right child } { Precondition: tree exists and is not empty; this procedure is only called if an insertion is made into the right subtree of the right child of 'alpha' } { Postcondition: balanced tree with height of not more than 1 in difference between subtrees } { Run Time: O(1) } { ************************************************************************ } { PROCEDURE double_left(var T : TreePtr); } { Function: performs a rotation to the right and then to the left } { Precondition: tree exists and is not empty; this procedure is only called if an insertion is made into a node which has a left child, and that left child has a right child. } { Postcondition: balanced tree with height of not more than 1 in difference between subtrees } { Run Time: O(1) } { ************************************************************************ } { PROCEDURE double_right(var T : TreePtr); } { Function: performs a rotation to the left and then to the right } { Precondition: tree exists and is not empty; this procedure is only called if an insertion is made into a node which has a right child, and that right child has a left child. } { Postcondition: balanced tree with height of not more than 1 in difference between subtrees } { Run Time: O(1) } { ************************************************************************ } { PROCEDURE insert(var T : TreePtr; K : keyType; var val : boolean); } { Function: inserts a new element in the tree } { Precondition: tree exists and is not full } { Postcondition: blanced tree with new element added } { Run Time: O(log N) } { ************************************************************************ } { PROCEDURE delete(var T : TreePtr; K : keyType; var val : boolean); } { Function: deletes an element from the tree } { Precondition: tree exists and is not empty } { Postcondition: balanced tree with the element deleted } { Run Time: O(log N) } { ************************************************************************ } { PROCEDURE find(T:TreePtr; element : KeyType); } { Function: finds an element in the tree and displays its information } { Precondition: Tree exists and is not empty } { Postcondition: if element found, the information is printed } { Run Time: O(log N) } { ************************************************************************ } { PROCEDURE preprint(T:TreePtr); } { Function: prints tree in pre-order traversal } { Precondition: tree exists and is not empty } { Postcondition: tree has been printed in pre-order } { Run Time: O(N) } { ************************************************************************ } { PROCEDURE print(T:TreePtr); } { Function: prints tree in alphabetical order } { Precondition: tree exists } { Postcondition: tree has been printed in alphabetical order } { Run Time: O(N) } { ************************************************************************ } { PROCEDURE postprint(T:TreePtr); } { Function: prints tree in post-order traversal } { Precondition: tree exists and is not empty } { Postcondition: tree has been printed in post-order } { Run Time: O(N) } { ************************************************************************ } PROGRAM AVLtree; USES help1380; TYPE elementType = string; KeyType = RECORD name : elementType; zip : elementType; END; TreePtr = ^TreeNode; TreeNode = RECORD key : KeyType; left : TreePtr; right : TreePtr; height : -1..+1 { height = h(right) - h(left) } END; VAR Tree : TreePtr; value : boolean; { for insertion & deletion } menuchar : char; { loop control } info : KeyType; PROCEDURE create_tree(var T : TreePtr); BEGIN T := NIL; END; PROCEDURE destroy_tree(var T: TreePtr); BEGIN T:=NIL; END; PROCEDURE left_rotation(var T : TreePtr); VAR temp : TreePtr; BEGIN temp := T^.left; T^.left := temp^.right; temp^.right := T; T := temp; END; PROCEDURE right_rotation(var T : TreePtr); VAR temp : TreePtr; BEGIN temp := T^.right; T^.right := temp^.left; temp^.left := T; T := temp; END; PROCEDURE double_left(var T : TreePtr); BEGIN right_rotation(T^.left); left_rotation(T); END; PROCEDURE double_right(var T : TreePtr); BEGIN left_rotation(T^.right); left_rotation(T); END; PROCEDURE insert(var T : TreePtr; K : keyType; var val : boolean); PROCEDURE balance_left(var T:TreePtr; var val : boolean); BEGIN writeln('balancing to the left...'); writeln(logfile,'balancing to the left...'); { LOGFILE } case T^.height of +1 : begin T^.height := 0; val := false; end;{ case +1 } 0 : T^.height := -1; -1 : begin{ rebalance } if T^.left^.height = -1 then begin{ single left rotation } writeln('single left rotation...'); writeln(logfile,'single left rotation...'); { LOGFILE } left_rotation(T); T^.right^.height := 0; end{ if T^.left^.height = -1 then } else{ T^.left^.height = +1 } begin{ double left rotation } writeln('double left rotation'); writeln(logfile,'double left rotation'); { LOGFILE } double_left(T); if T^.height = -1 then T^.right^.height := +1 else T^.right^.height := 0; if T^.height = +1 then T^.left^.height := -1 else T^.left^.height := 0; end; { double left rotation } T^.height := 0; val := false; end; { case -1 } end;{ case T^.height of } END;{ balance_left } PROCEDURE balance_right(var T:TreePtr; var val : boolean); BEGIN writeln('balancing to the right...'); writeln(logfile,'balancing to the right...'); { LOGFILE } case T^.height of -1 : begin T^.height := 0; val := false; end;{ case -1 } 0 : T^.height := +1; +1 : begin{ rebalance } if T^.right^.height = +1 then begin{ single rotation } writeln('single right rotation...'); writeln(logfile,'single right rotation...'); { LOGFILE } right_rotation(T); T^.left^.height := 0; end else { T^.right^.height = -1 } begin { double right rotation } writeln('double right rotation...'); writeln(logfile,'double right rotation...'); { LOGFILE } double_right(T); if T^.height = -1 then T^.right^.height := +1 else T^.right^.height := 0; if T^.height = +1 then T^.left^.height := -1 else T^.left^.height := 0; end;{ case +1 } T^.height := 0; val := false; end;{ case +1 } end; { case T^.height of } END;{ balance_right } BEGIN{ insert } if T = NIL then begin new(T); T^.key := K; T^.height := 0; T^.left := NIL; T^.right := NIL; val := true; end{ if T = NIL then } else if K.name < T^.key.name then begin insert(T^.left, K, val); if val then balance_left(T, val) end{ if K < T^.key then } else if K.name > T^.key.name then begin insert(T^.right, K, val); if val then balance_right(T, val); end;{ if K > T^.key then } END; { insert } PROCEDURE delete(var T : TreePtr; K : KeyType; val : boolean); PROCEDURE balance_left(var T : TreePtr; var val : boolean); BEGIN Writeln('balance left'); Writeln(logfile,'balance left'); { LOGFILE } case T^.height of -1 : begin T^.height := 0; val := true; end; 0 : begin T^.height := +1; val :=false; end; +1 : begin { rebalance } if t^.right^.height >= 0 then begin { single right rotation } writeln('single right rotation'); writeln(logfile,'single right rotation'); { LOGFILE } if T^.right^.height = 0 then begin right_rotation(T); T^.height := -1; val := false; end else begin right_rotation(T); T^.left^.height := 0; T^.height := 0; val := true; end; end else { t^.right^.bal = -1 } begin writeln('double right rotation'); writeln(logfile,'double right rotation'); { LOGFILE } double_right(T); T^.left^.height := 0; T^.right^.height := 0; val := true; end; end; end; END; PROCEDURE balance_right(Var T : TreePtr; var val : boolean); BEGIN writeln('balancing right...'); writeln(logfile,'balancing right...'); { LOGFILE } case T^.height of +1 : begin T^.height := 0; val := true; end; 0 : begin T^.height := -1; val := false; end; -1 : begin { rebalance } if T^.left^.height <= 0 then begin { single left rotation } writeln('single left rotation'); writeln(logfile,'single left rotation'); { LOGFILE } if T^.left^.height = 0 then begin left_rotation(t); T^.height := +1; val := false; end else begin left_rotation(T); T^.left^.height := 0; T^.height := 0; val := true; end; end else { T^.left^.height = +1 } begin { double left rotation } writeln('double left rotation'); writeln(logfile,'double left rotation'); { LOGFILE } double_left(t); T^.left^.height := 0; T^.right^.height := 0; val := true; end; end; end; END; FUNCTION deletemin(var T : TreePtr; var val : Boolean) : string; BEGIN { deletemin } if T^.left = NIL then begin deletemin := T^.key.name; T := T^.right; val := true; end else begin deletemin := deletemin(T^.left, val); if val then balance_left(T, val); end; END; BEGIN { delete } if T <> NIL then begin if K.name < T^.key.name then begin delete(T^.left, K, val); if val then balance_left(T, val); end else if K.name > T^.key.name then begin delete(T^.right, K, val); if val then balance_right(T, val); end else if (T^.left = NIL) and (T^.right = NIL) then begin T := NIL; val := true; end else if T^.left = NIL then begin T := T^.right; val := true; end else if T^.right = NIL then begin T := T^.left; val := true; end else begin T^.key.name := deletemin(T^.right, val); if val then balance_right(T, val); end; end; END; PROCEDURE find(T:TreePtr; element : KeyType); BEGIN if T = NIL then begin writeln('Person not found'); { LOGFILE } writeln(logfile,'Person not found'); end else if element.name < T^.key.name then find(T^.left, element) else if element.name > T^.key.name then find(T^.right, element) else begin writeln('Person found!'); writeln(T^.key.name, ' ', T^.key.zip); writeln(logfile,'Person found!'); { LOGFILE } writeln(logfile,T^.key.name, ' ', T^.key.zip); { LOGFILE } end; END; PROCEDURE preprint(T:TreePtr); BEGIN if T <> NIL then begin writeln(T^.key.name, ' ', T^.key.zip); writeln(logfile,T^.key.name, ' ', T^.key.zip); { LOGFILE } preprint(T^.left); preprint(T^.right); end; END; PROCEDURE print(T:TreePtr); BEGIN if T <> NIL then begin print(T^.left); writeln(T^.key.name, ' ', T^.key.zip); writeln(logfile,T^.key.name, ' ', T^.key.zip); { LOGFILE } print(T^.right); end; END; PROCEDURE postprint(T:TreePtr); BEGIN if T <> NIL then begin postprint(T^.left); postprint(T^.right); writeln(T^.key.name, ' ', T^.key.zip); writeln(logfile,T^.key.name, ' ', T^.key.zip); { LOGFILE } end; END; PROCEDURE menu (var menuch: char); BEGIN writeln; writeln('insert..........I'); writeln('delete..........D'); writeln('find............F'); writeln('print...........P'); writeln('quit............Q'); writeln; write('make a selection # '); readln(menuch); writeln(logfile); { LOGFILE } writeln(logfile,'insert..........I'); { LOGFILE } writeln(logfile,'delete..........D'); { LOGFILE } writeln(logfile,'find............F'); { LOGFILE } writeln(logfile,'print...........P'); { LOGFILE } writeln(logfile,'quit............Q'); { LOGFILE } writeln(logfile); { LOGFILE } write(logfile,'make a selection # '); { LOGFILE } writeln(logfile,menuch); { LOGFILE } END;{ menu } BEGIN {***} setup_logfile; { initializes logfile } create_tree(Tree); repeat menu(menuchar); writeln; writeln(logfile); { LOGFILE } case menuchar of 'i', 'I' : begin write('Enter name to be added: '); readln(info.name); write('Enter zip-code: '); readln(info.zip); { LOGFILE } write(logfile,'Enter name to be added: '); { LOGFILE } writeln(logfile,info.name); { LOGFILE } write(logfile,'Enter zip-code: '); { LOGFILE } writeln(logfile,info.zip); insert(Tree, info, value); end; 'd', 'D' : begin writeln('Enter name to be deleted: '); readln(info.name); writeln(logfile,'Enter name to be deleted: '); { LOGFILE } writeln(logfile,info.name); { LOGFILE } delete(Tree, info, value); end; 'f', 'F' : begin writeln('Enter name to be found: '); readln(info.name); writeln; writeln(logfile,'Enter name to be found: '); { LOGFILE } writeln(logfile,info.name); { LOGFILE } writeln(logfile); { LOGFILE } find(Tree, info); end; 'p', 'P' : begin writeln('Alphabetical order: '); writeln(logfile,'Alphabetical order: '); { LOGFILE } print(Tree); writeln; writeln('Pre-order: '); writeln(logfile); { LOGFILE } writeln(logfile, 'Pre-order: '); { LOGFILE } preprint(Tree); writeln; writeln('Post-order: '); writeln(logfile); { LOGFILE } writeln(logfile, 'Post-order: '); { LOGFILE } postprint(Tree); end; 'q', 'Q' : begin writeln('Thanks for using this program.'); writeln(logfile,'Thanks for using this program.'); { LOGFILE } end; end;{ case menuchar of } until (menuchar = 'q') or (menuchar = 'Q'); destroy_tree(Tree); {***} display_logfile; {***} holdscreen; {***} close_logfile { closes logfile } END.
Make your own free website on Tripod.com