BinBin Search Tree
Distinguished computer scientist professor Fabinaris Suchbaum and his colleagues from Max Planck Institute for Software Systems in Saarbrücken
are currently experimenting with various types of binary search trees. Their last invention is named BinBin Search Tree (BBST).
BBST differs from usual BST in two ways. First, any of its nodes can contain one or two keys (and no more). Second, apart from operations Find, Insert and Delete
which are analogous to the same operations in BST there is also additional Consolidate operation which often significantly reshapes the whole tree making it more
suitable for fast searching.
Other (more or less standard) properties of BBST are:
All keys in the left subtree of a node are smaller than the key(s) in that node
and all keys in the right subtree of a node are greater than the key(s) in that node.
A node in BBST may have 0, 1, or 2 children.
BBST never contains duplicate keys.
Next, we specify the particular BBST operations in more detail.
Let us denote left resp. right subtree of a node X by symbol X.Lsubtree resp X.Rsubtree. Let us denote by symbol X.KEYS
the set of all keys (one or two) stored in X. Also, let us consider each subtree of BBST, including the empty one, to be also BBST.
Operation Insert(key)
If a key with the same value as key exists in BBST then Insert(key) has no effect on BBST.
Otherwise, for key and for each node X visited during insertion the following rules are applied recursively:
1. If BBST is empty then a new root X is created and key is stored in X.
2. If BBST is unempty then Insert(key) starts at the root. Subsequently, one of three mutually exclusive cases applies:
2a. If key < min(X.KEYS) then Insert(key) is applied to X.Lsubtree.
2b. If key > max(X.KEYS) then Insert(key) is applied to X.Rsubtree.
2c. If min(X.KEYS) < key < max(X.KEYS) then Insert(max(X.KEYS)) is applied to X.Rsubtree
and key is stored in X.
Note that when Insert operation increases the number of keys in BBST it also increases the number of nodes in BBST.
Operation Delete(key)
If a key with the same value as key does not exist in BBST then Delete(key) has no effect on BBST.
Otherwise, let X be the node containing key.
If X contains two keys then key is deleted from X and no other action is taken.
If key is the single key in X then one of four mutually exclusive cases applies:
1. X is a leaf. Then X is removed from BBST.
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 BBST.
2b. X has one child and X is a root. Then the child of X becomes the root of BBST and X is removed from BBST.
3. X has two children. Then let keyY be the smallest key in X.Rsubtree. Value of key is substituted
in X by keyY and keyY is deleted from X.Rsubtree by applying recursively the same rules.
Note that when Delete operation reduces the number of keys in BBST it does not necessarily reduce the number of nodes in BBST.
Operation Consolidate
The result of this operation is rearranged BBST. All keys remain in BBST, not necessarily in the same nodes, and the shape of BBST is changed.
When Consolidate operation is completed the structure of BBST fulfills the following conditions:
1. All nodes other than the root contain two keys.
2. When the number of keys in BBST is odd then the root contains only one key, otherwise it also contains two keys.
3. There is at most one node with exactly one child and that child is the left child.
4. The depth of any two leaves differs by at most 1.
5. For any two leaves X and Y it holds: If key(s) of X are smaller than the key(s) of Y then the depth of X is greater or equal to the depth of Y.
6. The depth of BBST is minimum possible.
Note that the shape of BBST and the contents of its nodes are always unambiguously specified by any sequence of operations Insert, Delete, Consolidate.
The task
You are given a sequence of operations on BBST containing some Consolidate operations.
Print out the number of keys, number of nodes and depth of BBST immediately before each Consolidate operation.
Implementation note
The tree in this problem might be relatively big (millions of keys and nodes) and subject to many frequent small changes (Insert, Delete) and also occasional big changes (Consolidate). Therefore, in some cases the purely object oriented approach might be either slow or exceedingly memory-demanding or both. In such case, depending on your particular implementation, you should consider some more effective strategy. Typically, you might want to create a fixed set of objects at the beginning and later only change its contents thus saving the system from the time and space consuming household chores associated with continual construction/destruction of short lived objects.
Input
The first line contains five positive integers A, B, M, N, OP separated by space. The values A, B, M, N specify BBST which has to be initially built.
The sequence S = (s1, s2, ..., sN) of keys is defined as follows:
s1 = B.
sk+1 = (A×sk + B) mod M, k = 1, 2, ..., N−1.
The initial BSST is built by applying operations Insert(s1), Insert(s2), ..., Insert(sN) in this order on BBST which
is empty before Insert(s1).
Next, there are OP lines each of which specifies one operation on BBST built in the previous phase.
The Insert operation is represented by character 'I ' followed by space and non-negative integer key to be inserted to BBST.
The Delete operation is represented by character 'D ' followed by space and non-negative integer key to be deleted from BBST.
The Consolidate operation is represented by single character 'C '.
All OP operations specified in the input sequence are supposed to be performed in exactly the same order.
No input line contains any leading spaces.
All keys in BBST are smaller than 109.
The values of A, B, M are positive and less than 109.
The values of N, OP are positive and less than 3×106.
In this problem, you may suppose that the number of keys in BBST is at least 2 during all OP operations.
Output
The output contains as many lines as there are Consolidate operations in the input sequence of operations. Each line corresponds to one Consolidate operation and the order of lines preserves the order of Consolidate operations. Each line contains three integers separated by space. The integers are number of keys, number of nodes and depth of BBST (in this order) immediately before the corresponding Consolidate operation is performed.
Example 1
Input60 17 59 8 5 C I 33 D 34 I 53 COutput
8 8 3 9 5 2The following scheme shows BBST in Example 1 before the first Consolidate operation and then also before each subsequent operation specified in the input. Note that the initial building of the tree (specified by values A, B, M, N) produces structurally the same tree as would be produced by the same sequence of Insert operations in usual BST.
______[17,--]____________________
______[ 9,--] ______[34,--]_____________
[ 1,--] ______[26,--] ______[51,--]
[18,--] [43,--]
C
______[26,34]______
______[17,18] [43,51]
[ 1, 9]
I 33
______[26,33]_____________
______[17,18] ______[43,51]
[ 1, 9] [34,--]
D 34
______[26,33]______
______[17,18] [43,51]
[ 1, 9]
I 53
______[26,33]______
______[17,18] [43,51]______
[ 1, 9] [53,--]
Example 2
Input63 23 31 9 7 I 3 I 28 C D 28 D 22 I 24 COutput
11 11 4 10 6 2The following scheme shows BBST in Example 2 before the first Insert operation and then also before each subsequent operation specified in the input.
____________________[23,--]_____________
_____________[15,--]_____________ ______[30,--]
______[ 7,--]______ ______[22,--] [29,--]
[ 6,--] [14,--] [21,--]
I 3
____________________[23,--]_____________
_____________[15,--]_____________ ______[30,--]
______[ 7,--]______ ______[22,--] [29,--]
______[ 6,--] [14,--] [21,--]
[ 3,--]
I 28
____________________[23,--]____________________
_____________[15,--]_____________ ______[30,--]
______[ 7,--]______ ______[22,--] ______[29,--]
______[ 6,--] [14,--] [21,--] [28,--]
[ 3,--]
C
_____________[22,--]_____________
______[ 7,14]______ ______[29,30]
[ 3, 6] [15,21] [23,28]
D 28
_____________[22,--]_____________
______[ 7,14]______ ______[29,30]
[ 3, 6] [15,21] [23,--]
D 22
_____________[23,--]______
______[ 7,14]______ [29,30]
[ 3, 6] [15,21]
I 24
_____________[23,--]_____________
______[ 7,14]______ ______[29,30]
[ 3, 6] [15,21] [24,--]
Example 3
Input52 11 17 8 20 D 10 D 4 D 15 C D 9 C I 14 D 16 I 9 D 5 I 10 C I 5 C D 14 D 10 I 12 C D 5 COutput
5 5 2 4 3 1 5 4 3 6 4 2 5 4 2 4 3 1The following scheme shows BBST in Example 3 before the first Delete operation and then also before each subsequent operation specified in the input.
____________________[11,--]_____________
______[ 5,--]_____________ ______[16,--]
______[ 4,--] ______[10,--] [15,--]
[ 3,--] [ 9,--]
D 10
_____________[11,--]_____________
______[ 5,--]______ ______[16,--]
______[ 4,--] [ 9,--] [15,--]
[ 3,--]
D 4
_____________[11,--]_____________
______[ 5,--]______ ______[16,--]
[ 3,--] [ 9,--] [15,--]
D 15
_____________[11,--]______
______[ 5,--]______ [16,--]
[ 3,--] [ 9,--]
C
______[ 9,--]______
[ 3, 5] [11,16]
D 9
______[11,--]______
[ 3, 5] [16,--]
C
______[11,16]
[ 3, 5]
I 14
______[11,14]______
[ 3, 5] [16,--]
D 16
______[11,14]
[ 3, 5]
I 9
_____________[11,14]
[ 3, 5]______
[ 9,--]
D 5
_____________[11,14]
[ 3,--]______
[ 9,--]
I 10
____________________[11,14]
[ 3,--]______
[ 9,--]______
[10,--]
C
______[10,--]______
[ 3, 9] [11,14]
I 5
_____________[10,--]______
[ 3, 5]______ [11,14]
[ 9,--]
C
______[ 9,10]______
[ 3, 5] [11,14]
D 14
______[ 9,10]______
[ 3, 5] [11,--]
D 10
______[ 9,--]______
[ 3, 5] [11,--]
I 12
______[ 9,--]______
[ 3, 5] [11,--]______
[12,--]
C
______[ 9,--]______
[ 3, 5] [11,12]
D 5
______[ 9,--]______
[ 3,--] [11,12]
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