Rotations on the conveyor
A seismic report service keeps the shocks of the last few days in an AVL tree: the key is the event number, and numbers grow with time. A new event is inserted, and an event that has become older than the window is deleted. The tree is being rewritten in another language, and to compare the two implementations a reference is needed: how many rebalancings of each kind the tree makes on a recorded log of operations, and how high it is at the end. The implementations must agree down to every rotation, so the rules are given exactly.
- Inserting a key k works as in an ordinary search tree: from the root go left if k is less than the node's key, otherwise right; the new node becomes a leaf.
- Deleting a key k. A node without children is simply removed, a node with one child is replaced by that child. A node with two children gets its key replaced by the smallest key of its right subtree, and the node where that smallest key lay is removed (it has no left child, and its right child, if any, takes its place).
- Rebalancing. After an insertion and after a deletion all nodes on the path from the place of the change to the root, bottom up, recompute their height (a leaf has height 1, an empty subtree 0). If at a node the left subtree is 2 higher than the right, look at the left child: if the height of its left subtree is not less than that of its right, rotate right about the node; this is case LL; otherwise first rotate left about the child, then right about the node; this is case LR. If the right subtree is higher, mirror it: RR (a left rotation) or RL (a right rotation about the right child, then a left one about the node). After a rotation the climb continues from the new root of that subtree. On deletion the path starts at the parent of the removed node.
The third and fourth tests are all 19,073 earthquakes of magnitude 5 and above in 2015–2025 from the USGS catalogue: event number i is inserted when it happens and deleted as soon as an event occurs 7 days (in the third test) or 30 days (in the fourth) after it.
Input
The first line holds q (1 ≤ q ≤ 10⁵), the number of operations. Then q lines of the form + k (insert the key k, which is not in the tree) or - k (delete the key k, which is in the tree), 1 ≤ k ≤ 10⁹. The tree is empty at first.
Output
Five numbers separated by spaces: how many rebalancings of kinds LL, LR, RR and RL there were over all operations, and the height of the tree at the end (0 if it is empty). A double rotation counts as one rebalancing of its kind.
Examples
Example 1
10 + 1 + 2 + 3 + 4 + 5 + 6 + 7 - 1 - 2 - 3
0 0 5 0 3
Example 2
12 + 50 + 20 + 30 + 80 + 60 + 10 + 90 + 70 + 40 - 10 - 90 - 30
0 1 1 1 3
Limits
- Time · Python
- 6000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 10 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
This is a direct application of the article: an AVL tree with heights in the nodes, insertion and deletion with a climb to the root. All the difficulty is in following the rules exactly, especially on deletion.
2Hint 2
Work through the first sample by hand. After inserting the keys 1 to 7 the tree is perfect: root 4, with 2 and 6 below. Deleting 1 and 2 creates no lean, and after deleting 3 the root has nothing on the left and a subtree of height 2 on the right, and the right child 6 is level: its branches 5 and 7 have the same height. Which rotation is needed here, single or double?
3The idea
Recursive insertion and deletion, as in the article's listing: the function returns the new root of the subtree, and on the way back each node calls the rebalancing. The way back out of the recursion is exactly the path from the place of the change to the root that the statement requires. A level child occurs only on deletion, and it needs a single rotation: the rule “the height of the child's outer subtree is not less than the inner one” is written with ≥, not >.
4Walkthrough
A node stores a key, two children and a height. Rebalancing a node: recompute its height, compute the difference of the subtree heights; at +2 compare the heights of the left child's subtrees and do LL (a right rotation) or LR (a left rotation at the child, then a right one at the node), at −2 mirror it. A rotation changes three links and recomputes the heights of two nodes, first the one that went down, then the one that went up.
Deletion goes down to the key. A node with one child or none returns that child (or nothing). A node with two children gets its key replaced by the smallest key of the right subtree, and the recursive deletion of that key from the right subtree goes down to its node and back by itself, rebalancing along the way. Then the node itself and everything above is rebalanced.
Why a level child needs a single rotation. Let the right subtree of a node x be two higher, its root y level, both subtrees of y of height h, and the left subtree of x of height h − 1. A single left rotation makes y the root: on the left is x with subtrees of heights h − 1 and h, its height h + 1, on the right a subtree of height h; all is well. A double rotation lifts the left grandchild z to the top, and the right subtree of z moves over to y and stands next to y's right subtree of height h. If that subtree of z was lower, of height h − 2, y ends up with a two-storey lean, and the tree stops being an AVL tree. And even if it does not, the shape is still different, and so is the answer: in the first sample the right answer is 0 0 5 0 3, while a double rotation gives 0 0 4 1 3.
On the real data all rebalancings are RR: each new key is larger than all others, and on insertion the right branch of the right child outweighs; the smallest key is always the one deleted, and after it the right side outweighs too. In the 7-day window there are 26,937 of them for 19,073 insertions and 19,047 deletions.
4+Solution
5Complexity
Each operation costs O(log n), where n is the number of keys in the tree: the height of an AVL tree is at most 1.44·log₂ n. In total O(q log q) time and O(q) memory. The recursion depth is the height of the tree, at most 24 for 10⁵ keys, so Python's recursion limit is no obstacle.
6Common mistakes
- A strict comparison instead of a non-strict one. The insertion rule “if the child's inner subtree is higher, a double rotation, otherwise a single one” is right for deletion too, but “if the outer one is higher, a single rotation, otherwise a double one” picks a double rotation for a level child: the tree gets a different shape, and sometimes a lean an AVL tree does not allow. On the first sample the answer differs at once.
- The predecessor instead of the successor. If a node with two children is replaced by the largest key of its left subtree, the tree stays a search tree, but the shape and the number of rotations will be different.
- No rebalancing on the way to the successor. The nodes between the deleted one and the successor lose height too; if only the nodes above the deleted one are rebalanced, the leans below remain.
- The order of height updates in a rotation. First the node that went down, then the one that went up: the height of the new root depends on the already corrected height of its child.