Relaxed AVL Tree
The recent very successful proposal of BinBin Search Tree has encouraged
professor Fabinaris Suchbaum and his team to investigate more modifications of search trees. Now they are going to evaluate a relaxed version of AVL tree.
Relaxed AVL tree is less strict than normal AVL. In each node, the difference between the height of the right and left subtree is allowed to be up to D for some chosen constant D>1. Balancing of the tree is done using rotations L, R, LR and RL in the same way as in the case of normal AVL. There is a rule that whenever an unbalanced node can be balanced by more types of rotations then a single rotation is always preferred over a double rotation.
A specification of steps performed by insert resp. delete before the balancing process takes place is given bellow. It applies to AVL as well as relaxed AVL.
Let us denote left resp. right subtree of a node X by symbol X.Lsubtree resp. X.Rsubtree. Let us denote by symbol X.key
the key stored in X. Also, let us consider each subtree of AVL/relaxed AVL, including the empty one, to be also AVL/relaxed AVL.
Operation Insert(key)
If a key with the same value as key exists in AVL then Insert(key) has no effect on AVL.
Otherwise, for key and for each node X visited during insertion the following rules are applied recursively:
1. If AVL is empty then a new node X is created and key is stored in X.
2. If AVL is unempty then Insert(key) starts at the root. Subsequently, one of two cases applies:
2a. If key < X.key then Insert(key) is applied to X.Lsubtree.
2b. If key > X.key then Insert(key) is applied to X.Rsubtree.
Operation Delete(key)
If a key with the same value as key does not exist in AVL then Delete(key) has no effect on AVL.
Otherwise, let X be the node containing key.
One of four mutually exclusive cases applies:
1. X is a leaf. Then X is removed from AVL.
2a. X has one child and X is not a root. Then the child of X becomes the child of parent of X and X is removed from AVL.
2b. X has one child and X is a root. Then the child of X becomes the root of AVL and X is removed from AVL.
3. X has two children. Then let keyY be the greatest key in X.Lsubtree. Value of key is substituted
in X by keyY and keyY is deleted from X.Lsubtree by applying recursively the same rules.
The task
You are given a sequence of insert and delete operations. The operations are simultaneously performed on empty AVL and relaxed AVL.
For both trees, print out the final depth and the total number of rotations performed during the whole process.
Input
The input is one line containing five positive integers D, A, B, M, N separated by space. D is the maximal height difference permitted between the left and right subtree of a node in the relaxed AVL tree. The values A, B, M, N define a sequence of keys
S = (s1, s2, ..., sN) as follows:
s1 = B.
sk+1 = (A×sk + B) mod M, k = 1, 2, ..., N−1.
Operations Insert(s1), Insert(s2), ..., Insert(sN) are performed in this order on an empty AVL/relaxed AVL.
This is followed by operations Delete(s3), Delete(s6), Delete(s9), ..., Delete(sN-(N mod 3)) in this order, i.e., delete is called for each element of S whose index is divisible by 3.
The value of D is at most 10.
All keys in AVL/relaxed AVL are smaller than 109.
The values of A, B, M are positive and less than 109.
The value of N is positive and less than 1×106.
Output
The output contains two lines. The first line consists of two integers separated by space. The first integer is the depth of AVL tree after performing the operations. The second integer is the total number of rotations performed over AVL. Each single as well as double rotation counts as 1. The second row has the same format and gives the depth and the total number of rotations for relaxed AVL tree.
Example 1
Input2 1 4 11 5Output
2 1 2 0The following schemes shows AVL and relaxed AVL tree in Example 1 after performing five insert operations and the final state after performing one delete operation.
AVL tree:
Insert(4), Insert(8), Insert(1), Insert(5), Insert(9)
______[4]_____________
[1] ______[8]_______
[5] [9]
Delete(1) - left rotation in [4] is performed
__________[8]______
[4]______ [9]
[5]
relaxed AVL tree:
Insert(4), Insert(8), Insert(1), Insert(5), Insert(9)
______[4]_____________
[1] ______[8]_______
[5] [9]
Delete(1)
[4]_____________
______[8]_______
[5] [9]
Example 2
Input2 9 9 16 8Output
2 3 3 1The following schemes shows selected states of AVL and relaxed AVL tree in Example 2 during performing the insert and delete operations.
AVL tree:
Insert(9), Insert(10), Insert(3), Insert(4), Insert(13)
______________[9]_______
[3]______ [10]________
[4] [13]
Insert(14) - left rotation in [10] is performed
______________[9]______________
[3]______ _______[13]________
[4] [10] [14]
Insert(7) - left rotation in [3] is performed
______________[9]______________
______[4]______ _______[13]________
[3] [7] [10] [14]
Insert(8)
______________[9]______________
______[4]_____ _______[13]________
[3] [7]_____ [10] [14]
[8]
Delete(3) - left rotation in [4] is performed
______________[9]______________
______[7]______ _______[13]________
[4] [8] [10] [14]
Delete(14)
______________[9]______________
______[7]______ _______[13]
[4] [8] [10]
relaxed AVL tree:
Insert(9), Insert(10), Insert(3), Insert(4), Insert(13), Insert(14), Insert(7)
______________[9]________
[3]_____ [10]_______
[4]_____ [13]_______
[7] [14]
Insert(8) - left rotation in [3] is performed
______________[9]________
_____[4]_____ [10]_______
[3] [7]_____ [13]_______
[8] [14]
Delete(3), Delete(14)
______________[9]________
[4]_____ [10]_______
[7]_____ [13]
[8]
Public data
The public data set is intended for easier debugging and approximate program correctness checking. The public data set is stored also in the upload system and each time a student submits a solution it is run on the public dataset and the program output to stdout and stderr is available to him/her.
Link to public data set