AVL search tree update
Assignment
Quido is developing a search engine which will manipulate millions of items in a relatively constrained memory space. To demonstrate the effectivity of his solution he is going to prepare a limited demo version which solves the task described bellow.
Denote by key(x) the value of the key of stored in a node x in an unempty AVL tree.
Define the left order of the node x as the number of nodes in the AVL tree which key value is smaller than key(x).
Operation Update(x, h) consists of two steps: In the first step, the node x is removed from the AVL tree by standard operation Delete. In the second step, if the AVL tree does not contain a node with key h than a new node with key h is inserted into the AVL tree by standard operation Insert.
To specify the task unambiguously, Quido follows the rules:
-
A. Whenever it is necessary in the operation Delete to substitute the deleted node y by another node or to substitute the deleted key by another key in the AVL tree the implemenation will use the node (or the key of that node) which left order is equal to the left order of y increased by 1.
-
B. Whenever the root of the AVL tree has only one child and the root is deleted, the child of the root becomes the new root of the AVL tree.
-
C. Whenever an unbalanced node can be balanced by more types of rotations then a single rotation is always preferred over a double rotation.
The demo version generates a sequence of AVL trees (T1, T2, …, TK), K > 0, the sizes of these AVL trees are denoted (in this order) by the symbols N1, N2, …, NK.
The AVL tree T1 is a balanced tree which depth is minimum possible and which contains all integer keys from the set \{N, N+1, N+2, …, N+2D − 2\}, where N and D are positive integers. Note that N1 = 2D − 1.
Let A, B, M be fixed positive integers. The AVL tree Tk+1 (k = 1, 2, …, K−1) is obtained by modifying the AVL tree Tk with one operation Update:
-
1. In the AVL tree Tk is located the node xk, which left order in Tk is equal to k2 mod Nk.
-
2. The operation Update(xk, (A×key(xk) + B) mod M) is performed in Tk. The updated AVL tree is Tk+1.
The task
To check Quido’s implementation we have to calculate the value of NK, the depth of TK and the number of those nodes in TK which depth is equal to the depth of TK.
Input
The input contains one text line with six positive integers K, N, D, A, B, M, separated by spaces. The meaning of the integers is described in the text above.
The value of K does not exceed 106, the value of D does not exceed 23, all other input values do not exceed 107.
Output
The otuput contains one text line with tree integers separated by spaces. The first integer is equal to NK, the second one is equal to the depth of TK and the third one is equal to the number of those nodes in TK which depth is equal to the depth of TK.
Let us remind you that the depth of the tree root is 0. You may suppose that the AVL tree’s T1, T2, …, TK are unempty.
Examples
Example 1
5 8 3 1 1 106 2 3The shape and the keys of the AVL tree T5 are depicted bellow.
_______[11]_____ ____[3]____ [13]____ [0] [10] [14]