/*===================================================================*/ /*===================================================================*/ /*===================================================================*/ AVL: PROCEDURE OPTIONS ( MAIN ) ; /*---------------------------------------------------------------------- | | | GPL 3 Licensed. | | | | (c) Copyright W. Stewart, 13 October 1988. | | | | This program is free software: you can redistribute it and/or modify | | it under the terms of the GNU General Public License as published by | | the Free Software Foundation, either version 3 of the License, or | | (at your option) any later version. | | | | This program is distributed in the hope that it will be useful, | | but WITHOUT ANY WARRANTY; without even the implied warranty of | | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | | GNU General Public License for more details. | | | | You can find a copy of the full license at | | www.gnu.org/licenses/gpl.txt. | | | ----------------------------------------------------------------------*/ /*--------------------------------------------------------------------- | | Name | AVL | | Purpose | Read in and process requests to (1) Insert to, (2) Delete from, | (3) Print in bracketed form, and (4) Print in inorder, | an AVL tree. | | Usage | submit avl data_file | | Remarks | The AVL trees are implemented with PL/1 based storage. | | Subprograms | | Driver: | Initialization | Process_Data | Termination | | Utility: | Insert | Right_Balance | Left_Balance | Make_Tree | | Delete | Right_Balance_DLT | Left_Balance_DLT | Traverse | Check_Right | Check_Left | | Rotate_Left | Rotate_Right | Print_Tree | Print_Data | | Method | The codes are 1 character long, 'I' = insert, 'D' = delete, | 'T' = print the tree in bracketed form, 'P' = print the data | in the tree in inorder. 'I' and 'D' codes must be followed by | a 2 character key. | | Reference | Kruse, R.; "Data Structures and Program Design", chapter 9. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE 1 NODE BASED (P), 2 INFO CHARACTER (2), 2 BALANCE FIXED BINARY (31), 2 LEFT POINTER, 2 RIGHT POINTER; DECLARE ROOT POINTER, P POINTER, NULL BUILTIN, FALSE BIT (1) INIT ('0'B), TRUE BIT (1) INIT ('1'B); CALL INITIALIZATION ( ROOT ); CALL PROCESS_DATA ( ROOT ); CALL TERMINATION; RETURN; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ INITIALIZATION: PROCEDURE ( ROOT ); /*--------------------------------------------------------------------- | | Name | Initialization | | Purpose | Perform initialization functions, i.e. initialize the tree | by setting Root to Null. | | Usage | call Initialization ( Root ) | | Root - Pointer to the root of the AVL tree. | | Remarks | The AVL trees are implemented with PL/1 based storage. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE ROOT POINTER; ROOT = NULL; RETURN; END INITIALIZATION; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ PROCESS_DATA: PROCEDURE ( ROOT ); /*--------------------------------------------------------------------- | | Name | Process_Data | | Purpose | Drive the program by reading in and processing the input. | | Usage | call Process_Data ( Root ) | | Root - The root of the AVL tree. | | Subprograms | Insert | Delete | Print_Tree | Print_Data | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE EOF BIT (1), ROOT POINTER, KEY CHARACTER (2), CODE CHARACTER (1), FOUND BIT (1), TALLER BIT (1), SHORTER BIT (1); EOF = FALSE; ON ENDFILE ( SYSIN ) BEGIN; EOF = TRUE; GOTO END_LOOP; END; GET LIST ( CODE ); DO WHILE ( ^ EOF ); SELECT ( CODE ); WHEN ( 'I' ) DO; GET LIST ( KEY ); PUT SKIP (2) LIST ( ' Inserting key', KEY ); CALL INSERT ( ROOT, KEY, TALLER ); END; WHEN ( 'D' ) DO; GET LIST ( KEY ); PUT SKIP (2) LIST ( ' Deleting key', KEY ); CALL DELETE ( ROOT, KEY, SHORTER, FOUND ); IF ^ FOUND THEN PUT LIST ( '*** KEY NOT FOUND ***' ); END; WHEN ( 'T' ) DO; PUT SKIP (2) LIST ( ' Bracketed Tree:' ); CALL PRINT_TREE ( ROOT ); END; WHEN ( 'P' ) DO; PUT SKIP (2) LIST ( ' Inorder Tree:' ); CALL PRINT_DATA ( ROOT ); END; OTHERWISE PUT SKIP (2) LIST ( '*** INVALID CODE =', CODE ); END; GET LIST ( CODE ); END_LOOP: END; END PROCESS_DATA; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ INSERT: PROCEDURE ( ROOT, KEY, TALLER ) RECURSIVE; /*--------------------------------------------------------------------- | | Name | Insert | | Purpose | Will insert a Key in an AVL tree rooted at Root. | | Usage | call Insert ( Root, Key, Taller ) | | Root - Root of the tree into which Key is to be inserted. | Key - Key to be inserted. | Taller - Switch to be set if the tree rooted at Root becomes | taller as a result of the insertion. | | Remarks | This subprogram is recursive. | | Subprograms | Make_Tree | Right_Balance | Left_Balance | | Method | Recursively Insert the Key into the left or right subtree of | the Root as appropriate. If on return that left or right | subtree is taller, then adjust the balance of the root or | call Left_Balance or Right_Balance to perform AVL rotations. | | Reference | Kruse, R.; "Data Structures and Program Design", chapter 9. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE ROOT POINTER, KEY CHARACTER (2), TALLER BIT (1), TALLER_SUBTREE BIT (1); IF ROOT = NULL THEN DO; ROOT = MAKE_TREE ( KEY ); TALLER = TRUE; RETURN; END; IF KEY <= ROOT -> INFO THEN DO; CALL INSERT ( ROOT -> LEFT, KEY, TALLER_SUBTREE ); IF TALLER_SUBTREE THEN SELECT ( ROOT -> BALANCE ); WHEN ( 1 ) CALL LEFT_BALANCE ( ROOT, TALLER ); WHEN ( 0 ) DO; ROOT -> BALANCE = 1; TALLER = TRUE; END; WHEN ( -1 ) DO; ROOT -> BALANCE = 0; TALLER = FALSE; END; END; ELSE TALLER = FALSE; END; ELSE DO; CALL INSERT ( ROOT -> RIGHT, KEY, TALLER_SUBTREE ); IF TALLER_SUBTREE THEN SELECT ( ROOT -> BALANCE ); WHEN ( 1 ) DO; ROOT -> BALANCE = 0; TALLER = FALSE; END; WHEN ( 0 ) DO; ROOT -> BALANCE = -1; TALLER = TRUE; END; WHEN ( -1 ) CALL RIGHT_BALANCE ( ROOT, TALLER ); END; ELSE TALLER = FALSE; END; END INSERT; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ DELETE: PROCEDURE ( ROOT, KEY, SHORTER, FOUND ); /*--------------------------------------------------------------------- | | Name | Delete | | Purpose | Will delete a Key from an AVL tree rooted at Root. | | Usage | call Delete ( Root, Key, Shorter, Found ) | | Root - Root of the tree from which Key is to be deleted. | Key - Key to be deleted. | Shorter - Switch to be set if the tree rooted at Root becomes | shorter as a result of the deletion. | Found - Switch indicating if the Key was found in the tree. | | Remarks | This subprogram is recursive. | | Subprograms | Check_Left | Check_Right | Traverse | | Method | Recursively traverse the tree to find and delete the Key. | | When the Key is found, there are three cases: (1) there is | no right child of Root; (2) there is no left child of Root; | (3) there are left and right children of Root. | | Cases (1) and (2) are easily handled. Case (3) requires the | identification of the immediate predecessor of the Root, by | taking the path all the way right from Root -> Left. The key | stored in this predecessor is stored in the Root, and then | the predecessor is easily deleted, being of case (1), i.e. | having no right child. | | Traverse identifies, obtains the Key of, and deletes the | immediate predecessor of the Root in case (3). | | On each return from a recursive call to Delete or the | call to Traverse, if the left or right subtree became Shorter, | then Check_Left or Check_Right must be called to ensure that | the tree remains AVL. | | Reference | Kruse, R.; "Data Structures and Program Design", chapter 9. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE ROOT POINTER, KEY CHARACTER (2), RKEY CHARACTER (2), SHORTER BIT (1), FOUND BIT (1), T POINTER; IF ROOT = NULL THEN DO; FOUND = FALSE; SHORTER = FALSE; RETURN; END; IF KEY < ROOT -> INFO THEN DO; CALL DELETE ( ROOT -> LEFT, KEY, SHORTER, FOUND ); IF SHORTER THEN CALL CHECK_LEFT ( ROOT, SHORTER ); END; ELSE IF KEY > ROOT -> INFO THEN DO; CALL DELETE ( ROOT -> RIGHT, KEY, SHORTER, FOUND ); IF SHORTER THEN CALL CHECK_RIGHT ( ROOT, SHORTER ); END; ELSE DO; FOUND = TRUE; IF ROOT -> RIGHT = NULL THEN DO; T = ROOT; ROOT = ROOT -> LEFT; FREE T -> NODE; SHORTER = TRUE; RETURN; END; ELSE IF ROOT -> LEFT = NULL THEN DO; T = ROOT; ROOT = ROOT -> RIGHT; FREE T -> NODE; SHORTER = TRUE; RETURN; END; ELSE DO; CALL TRAVERSE ( ROOT -> LEFT, RKEY, SHORTER ); ROOT -> INFO = RKEY; IF SHORTER THEN CALL CHECK_LEFT ( ROOT, SHORTER ); END; END; END DELETE; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ TRAVERSE: PROCEDURE ( ROOT, RKEY, SHORTER ) RECURSIVE; /*------------------------------------------------------------------- | | Name | Traverse | | Purpose | Will traverse the right path from Root until a node with no | right child is found. The Key of this node will be stored for | return to the calling procedure, and the node is deleted. | | Usage | call Traverse ( Root, RKey, Shorter ) | | Root - Root of the tree to be traversed. | RKey - Key of the final right-most node of the tree. | Shorter - Switch to be set if the tree rooted at Root becomes | shorter as a result of the deletion. | | Remarks | This subprogram is recursive. | | Subprograms | Check_Right | | Method | Recursively Traverse the tree down the right path until a | node is found with no right child. This node is the immediate | predecessor of the node to be deleted. Store this node's | key and delete it. On return check if adjustments to balances | or rotations are required in the case the right subtree has | become shorter as a result of the deletion. | | Reference | Kruse, R.; "Data Structures and Program Design", chapter 9. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE ROOT POINTER, RKEY CHARACTER (2), SHORTER BIT (1), T POINTER; IF ROOT -> RIGHT = NULL THEN DO; RKEY = ROOT -> INFO; T = ROOT; ROOT = ROOT -> LEFT; FREE T -> NODE; SHORTER = TRUE; RETURN; END; ELSE DO; CALL TRAVERSE ( ROOT -> RIGHT, RKEY, SHORTER ); IF SHORTER THEN CALL CHECK_RIGHT ( ROOT, SHORTER ); END; END TRAVERSE; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ CHECK_LEFT: PROCEDURE ( ROOT, SHORTER ); /*------------------------------------------------------------------- | | Name | Check_Left | | Purpose | Will adjust the balance of the Root or call Right_Balance_DLT | to perform rotations as appropriate. | | Usage | call Check_Left ( Root, Shorter ) | | Root - Root of the tree for which the left subtree has | become shorter. | Shorter - Switch to be reset if the height of the tree rooted | at Root does not change. | | Subprograms | Right_Balance_DLT. | | Reference | Kruse, R.; "Data Structures and Program Design", chapter 9. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE ROOT POINTER, SHORTER BIT (1); SELECT ( ROOT -> BALANCE ); WHEN ( 1 ) ROOT -> BALANCE = 0; WHEN ( 0 ) DO; ROOT -> BALANCE = -1; SHORTER = FALSE; END; WHEN ( -1 ) CALL RIGHT_BALANCE_DLT ( ROOT, SHORTER ); END; END CHECK_LEFT; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ CHECK_RIGHT: PROCEDURE ( ROOT, SHORTER ); /*------------------------------------------------------------------- | | Name | Check_Right | | Purpose | Will adjust the balance of the Root or call Left_Balance_DLT | to perform rotations as appropriate. | | Usage | call Check_Right ( Root, Shorter ) | | Root - Root of the tree for which the right subtree has | become shorter. | Shorter - Switch to be reset if the height of the tree rooted | at Root does not change. | | Subprograms | Left_Balance_DLT. | | Reference | Kruse, R.; "Data Structures and Program Design", chapter 9. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE ROOT POINTER, SHORTER BIT (1); SELECT ( ROOT -> BALANCE ); WHEN ( 1 ) CALL LEFT_BALANCE_DLT ( ROOT, SHORTER ); WHEN ( 0 ) DO; ROOT -> BALANCE = 1; SHORTER = FALSE; END; WHEN ( -1 ) ROOT -> BALANCE = 0; END; END CHECK_RIGHT; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ RIGHT_BALANCE: PROCEDURE ( ROOT, TALLER ); /*------------------------------------------------------------------- | | Name | Right_Balance | | Purpose | Will perform a single or double rotation around Root to | restore the AVL condition. | | Usage | call Right_Balance ( Root, Taller ) | | Root - Root of the tree, right high, for which the right | subtree has become taller. | Taller - Switch to be reset to indicate that rotation(s) have | restored the original height of Root. | | Subprograms | Rotate_Left | Rotate_Right | | Method | Check the balance of Root -> Right. If left high then perform | a double rotation and set the balances as appropriate. If | right high then perform a single rotation. | | Reference | Kruse, R.; "Data Structures and Program Design", chapter 9. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE ROOT POINTER, TALLER BIT (1), X POINTER, W POINTER; X = ROOT -> RIGHT; SELECT ( X-> BALANCE ); WHEN ( 1 ) DO; W = X -> LEFT; SELECT ( W -> BALANCE ); WHEN ( 1 ) DO; ROOT -> BALANCE = 0; X -> BALANCE = -1; END; WHEN ( 0 ) DO; ROOT -> BALANCE = 0; X -> BALANCE = 0; END; WHEN ( -1 ) DO; ROOT -> BALANCE = 1; X -> BALANCE = 0; END; END; CALL ROTATE_RIGHT ( ROOT -> RIGHT ); CALL ROTATE_LEFT ( ROOT ); W -> BALANCE = 0; TALLER = FALSE; END; WHEN ( 0 ) PUT LIST ( '*** ERROR: (ROOT->RIGHT)->BALANCE = 0' ); WHEN ( -1 ) DO; ROOT -> BALANCE = 0; X -> BALANCE = 0; TALLER = FALSE; CALL ROTATE_LEFT ( ROOT ); END; END; END RIGHT_BALANCE; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ LEFT_BALANCE: PROCEDURE ( ROOT, TALLER ); /*------------------------------------------------------------------- | | Name | Left_Balance | | Purpose | Will perform a single or double rotation around Root to | restore the AVL condition. | | Usage | call Left_Balance ( Root, Taller ) | | Root - Root of the tree, left high, for which the left | subtree has become taller. | Taller - Switch to be reset to indicate that rotation(s) have | restored the original height of Root. | | Subprograms | Rotate_Left | Rotate_Right | | Method | Check the balance of Root -> Left. If right high then perform | a double rotation and set the balances as appropriate. If | left high then perform a single rotation. | | Reference | Kruse, R.; "Data Structures and Program Design", chapter 9. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE ROOT POINTER, TALLER BIT (1), X POINTER, W POINTER; X = ROOT -> LEFT; SELECT ( X-> BALANCE ); WHEN ( -1 ) DO; W = X -> RIGHT; SELECT ( W -> BALANCE ); WHEN ( -1 ) DO; ROOT -> BALANCE = 0; X -> BALANCE = 1; END; WHEN ( 0 ) DO; ROOT -> BALANCE = 0; X -> BALANCE = 0; END; WHEN ( 1 ) DO; ROOT -> BALANCE = -1; X -> BALANCE = 0; END; END; CALL ROTATE_LEFT ( ROOT -> LEFT ); CALL ROTATE_RIGHT ( ROOT ); W -> BALANCE = 0; TALLER = FALSE; END; WHEN ( 0 ) PUT LIST ( '*** ERROR: (ROOT->LEFT)->BALANCE = 0' ); WHEN ( 1 ) DO; ROOT -> BALANCE = 0; X -> BALANCE = 0; TALLER = FALSE; CALL ROTATE_RIGHT ( ROOT ); END; END; END LEFT_BALANCE; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ RIGHT_BALANCE_DLT: PROCEDURE ( ROOT, SHORTER ); /*------------------------------------------------------------------- | | Name | Right_Balance_DLT | | Purpose | Will perform a single or double rotation around Root to | restore the AVL condition. | | Usage | call Right_Balance_DLT ( Root, Shorter ) | | Root - Root of the tree, right high, for which the left | subtree has become shorter. | Taller - Switch to be reset to if rotation(s) restore the | original height of Root. | | Subprograms | Rotate_Left | Rotate_Right | | Method | Check the balance of Root -> Right. If left high then perform | a double rotation and set the balances as appropriate. If | right high then perform a single rotation. If equal balance | perform a single rotation. | | Reference | Kruse, R.; "Data Structures and Program Design", chapter 9. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE ROOT POINTER, SHORTER BIT (1), X POINTER, W POINTER; X = ROOT -> RIGHT; SELECT ( X-> BALANCE ); WHEN ( 1 ) DO; W = X -> LEFT; SELECT ( W -> BALANCE ); WHEN ( 1 ) DO; ROOT -> BALANCE = 0; X -> BALANCE = -1; END; WHEN ( 0 ) DO; ROOT -> BALANCE = 0; X -> BALANCE = 0; END; WHEN ( -1 ) DO; ROOT -> BALANCE = 1; X -> BALANCE = 0; END; END; CALL ROTATE_RIGHT ( ROOT -> RIGHT ); CALL ROTATE_LEFT ( ROOT ); W -> BALANCE = 0; SHORTER = TRUE; END; WHEN ( 0 ) DO; ROOT -> BALANCE = -1; X -> BALANCE = 1; SHORTER = FALSE; CALL ROTATE_LEFT ( ROOT ); END; WHEN ( -1 ) DO; ROOT -> BALANCE = 0; X -> BALANCE = 0; SHORTER = TRUE; CALL ROTATE_LEFT ( ROOT ); END; END; END RIGHT_BALANCE_DLT; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ LEFT_BALANCE_DLT: PROCEDURE ( ROOT, SHORTER ); /*------------------------------------------------------------------- | | Name | Left_Balance_DLT | | Purpose | Will perform a single or double rotation around Root to | restore the AVL condition. | | Usage | call Left_Balance_DLT ( Root, Shorter ) | | Root - Root of the tree, left high, for which the right | subtree has become shorter. | Taller - Switch to be reset to if rotation(s) restore the | original height of Root. | | Subprograms | Rotate_Left | Rotate_Right | | Method | Check the balance of Root -> Left. If right high then perform | a double rotation and set the balances as appropriate. If | left high then perform a single rotation. If equal balance | perform a single rotation. | | Reference | Kruse, R.; "Data Structures and Program Design", chapter 9. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE ROOT POINTER, SHORTER BIT (1), X POINTER, W POINTER; X = ROOT -> LEFT; SELECT ( X-> BALANCE ); WHEN ( -1 ) DO; W = X -> RIGHT; SELECT ( W -> BALANCE ); WHEN ( -1 ) DO; ROOT -> BALANCE = 0; X -> BALANCE = 1; END; WHEN ( 0 ) DO; ROOT -> BALANCE = 0; X -> BALANCE = 0; END; WHEN ( 1 ) DO; ROOT -> BALANCE = -1; X -> BALANCE = 0; END; END; CALL ROTATE_LEFT ( ROOT -> LEFT ); CALL ROTATE_RIGHT ( ROOT ); W -> BALANCE = 0; SHORTER = TRUE; END; WHEN ( 0 ) DO; ROOT -> BALANCE = 1; X -> BALANCE = -1; SHORTER = FALSE; CALL ROTATE_RIGHT ( ROOT ); END; WHEN ( 1 ) DO; ROOT -> BALANCE = 0; X -> BALANCE = 0; SHORTER = TRUE; CALL ROTATE_RIGHT ( ROOT ); END; END; END LEFT_BALANCE_DLT; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ ROTATE_LEFT: PROCEDURE ( ROOT ); /*------------------------------------------------------------------- | | Name | Rotate_Left | | Purpose | Will perform a left rotation around Root. | | Usage | call Rotate_Left ( Root ) | | Root - Root of the tree requiring left rotation. | | Reference | Kruse, R.; "Data Structures and Program Design", chapter 9. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE ROOT POINTER, T POINTER; IF ROOT = NULL | ROOT -> RIGHT = NULL THEN DO; PUT LIST ( '*** ERROR: ILLEGAL ROTATE_LEFT ATTEMPT.' ); RETURN; END; T = ROOT -> RIGHT; ROOT -> RIGHT = T -> LEFT; T -> LEFT = ROOT; ROOT = T; END ROTATE_LEFT; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ ROTATE_RIGHT: PROCEDURE ( ROOT ); /*------------------------------------------------------------------- | | Name | Rotate_Right | | Purpose | Will perform a right rotation around Root. | | Usage | call Rotate_Right ( Root ) | | Root - Root of the tree requiring right rotation. | | Reference | Kruse, R.; "Data Structures and Program Design", chapter 9. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE ROOT POINTER, T POINTER; IF ROOT = NULL | ROOT -> LEFT = NULL THEN DO; PUT LIST ( '*** ERROR: ILLEGAL ROTATE_RIGHT ATTEMPT.' ); RETURN; END; T = ROOT -> LEFT; ROOT -> LEFT = T -> RIGHT; T -> RIGHT = ROOT; ROOT = T; END ROTATE_RIGHT; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ MAKE_TREE: PROCEDURE ( KEY ) RETURNS ( POINTER ); /*------------------------------------------------------------------- | | Name | Make_Tree | | Purpose | Create a one node AVL tree and store the Key. | | Usage | Root = Make_Tree ( Key ) | | Key - The Key to be stored in the node. . | Root - Pointer returned, pointing to the new tree. | | Remarks | Uses PL/1 based storage. | | Reference | Kruse, R.; "Data Structures and Program Design", chapter 9. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE KEY CHARACTER (2), P POINTER; ALLOCATE NODE SET ( P ); P -> INFO = KEY; P -> BALANCE = 0; P -> LEFT = NULL; P -> RIGHT = NULL; RETURN ( P ); END MAKE_TREE; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ PRINT_DATA: PROCEDURE ( ROOT ) RECURSIVE; /*------------------------------------------------------------------- | | Name | Print_Data | | Purpose | Prints the Keys stored in the tree rooted at Root in inorder. | | Usage | call Print_Data ( Root ) | | Root - Root of the tree to be printed. | | Remarks | This subprogram is recursive. | | Method | Inorder traversal. | | Reference | Kruse, R.; "Data Structures and Program Design", chapter 9. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE ROOT POINTER; IF ROOT = NULL THEN RETURN; ELSE DO; CALL PRINT_DATA ( ROOT -> LEFT ); PUT EDIT ( ROOT -> INFO, ',' ) ( A, A ); CALL PRINT_DATA ( ROOT -> RIGHT ); END; END PRINT_DATA; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ PRINT_TREE: PROCEDURE ( ROOT ) RECURSIVE; /*------------------------------------------------------------------- | | Name | Print_Tree | | Purpose | Prints the tree rooted at Root in bracketed form. | | Usage | call Print_Tree ( Root ) | | Root - Root of the tree to be printed. | | Remarks | This subprogram is recursive. | | Method | Preorder traversal. | | Reference | Kruse, R.; "Data Structures and Program Design", chapter 9. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ DECLARE ROOT POINTER; IF ROOT = NULL THEN RETURN; ELSE IF ROOT -> LEFT = NULL & ROOT -> RIGHT = NULL THEN PUT EDIT ( ROOT -> INFO ) ( A ); ELSE DO; PUT EDIT ( '(', ROOT -> INFO, ': ' ) ( A, A, A ); CALL PRINT_TREE ( ROOT -> LEFT ); PUT EDIT ( ' , ' ) ( A ); CALL PRINT_TREE ( ROOT -> RIGHT ); PUT EDIT ( ')' ) ( A ); END; END PRINT_TREE; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ TERMINATION: PROCEDURE; /*------------------------------------------------------------------- | | Name | Termination | | Purpose | Any function required at termination, such as compiling and | printing statistics, etc. | | Usage | call Termination | | Remarks | Presently no termination functions required. | | Author | Wm. M. Stewart | | Date | 13 October 1988 | ---------------------------------------------------------------------*/ RETURN; END TERMINATION; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ END AVL; /*===================================================================*/ /*===================================================================*/ /*===================================================================*/ //GO.SYSIN DD * 'I' 'A ' 'T' 'P' 'I' 'B ' 'T' 'P' 'I' 'C ' 'T' 'P' 'I' 'D ' 'T' 'P' 'I' 'E ' 'T' 'P' 'I' 'F ' 'T' 'P' 'I' 'G ' 'T' 'P' 'I' 'H ' 'T' 'P' 'I' 'I ' 'T' 'P' 'I' 'J ' 'T' 'P' 'I' 'K ' 'T' 'P' 'I' 'L ' 'T' 'P' 'I' 'M ' 'T' 'P' 'I' 'N ' 'T' 'P' 'I' 'O ' 'T' 'P' 'I' 'P ' 'T' 'P' 'I' 'Q ' 'T' 'P' 'I' 'R ' 'T' 'P' 'I' 'S ' 'T' 'P' 'I' 'T ' 'T' 'P' 'I' 'U ' 'T' 'P' 'I' 'V ' 'T' 'P' 'I' 'W ' 'T' 'P' 'I' 'X ' 'T' 'P' 'I' 'Y' 'T' 'P' 'I' 'Z' 'T' 'P' 'D' 'P ' 'T' 'P' 'D' 'K ' 'T' 'P' 'D' 'W ' 'T' 'P' 'D' 'C ' 'T' 'P' 'D' 'G ' 'T' 'P' 'D' 'T ' 'T' 'P' 'D' 'M ' 'T' 'P' 'D' 'E ' 'T' 'P' 'D' 'Z ' 'T' 'P' 'D' 'I ' 'T' 'P' 'D' 'X ' 'T' 'P' 'D' 'N ' 'T' 'P' 'D' 'D ' 'T' 'P' 'D' 'H ' 'T' 'P' 'D' 'S ' 'T' 'P' 'D' 'Y ' 'T' 'P' 'D' 'V ' 'T' 'P' 'D' 'Q ' 'T' 'P' 'D' 'L ' 'T' 'P' 'D' 'J ' 'T' 'P' 'D' 'A ' 'T' 'P' 'D' 'U ' 'T' 'P' 'D' 'B ' 'T' 'P' 'D' 'F ' 'T' 'P' 'D' 'O' 'T' 'P' 'D' 'R' 'T' 'P'