Loading in order
An event log receives records numbered 1, 2, 3, … strictly in order and builds an index on the number, an AVL tree with the same rules as in the article: a new key becomes a leaf, and then the nodes on the path to the root recompute their heights and, at a two-storey lean, make a single or double rotation. The administrator wants to know in advance, without loading the log: how high the index will be after n records, how many rebalancings the insertions will make in total, and how many comparisons a search for record number k will cost, that is, at what depth it will be (the root has depth 1).
The second and sixth tests are the index of the USGS catalogue of 19,073 earthquakes of magnitude 5 and above in 2015–2025, loaded in time order; the second asks about the strongest earthquake of each year.
Input
The first line holds q (1 ≤ q ≤ 10⁵), the number of questions. Then q lines n k (1 ≤ k ≤ n ≤ 10¹⁸).
Output
For each question, a line of three numbers: the height of the tree after inserting the keys 1, 2, …, n in order into an empty AVL tree, the total number of rebalancings over all these insertions (a double rotation is one rebalancing), and the depth of the key k.
Examples
Example 1
5 1 1 7 4 8 8 12 5 12 11
1 0 1 3 4 1 4 4 4 4 8 4 4 8 3
Example 2
13 19073 1088 19073 3153 19073 4320 19073 5808 19073 7258 19073 9066 19073 11014 19073 13130 19073 13811 19073 15440 19073 17977 19073 1 19073 19073
15 19058 8 15 19058 14 15 19058 9 15 19058 10 15 19058 13 15 19058 13 15 19058 13 15 19058 14 15 19058 15 15 19058 11 15 19058 15 15 19058 14 15 19058 15
Limits
- Time · Python
- 4000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 8 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
A tree of 10¹⁸ nodes cannot be built, but small ones can. Insert the keys up to 20–30 in order with the article's listing and write out for each n the right branch from the root: the root, its right child, that one's right child and so on. What hangs on the left of these nodes?
2Hint 2
A rotation does not change the height of the subtree where it happened; that is a theorem of the article. So the height of the tree grows only on insertions without a rotation. The article's listing shows that on increasing keys exactly the 1st, 2nd, 4th, 8th, … insertions do without a rotation. How is this related to the binary notation of n?
3Hint 3
Perfect trees hang on the left of the nodes of the right branch. Write n in binary and compare the heights of these perfect trees with the digits.
4The idea
The tree grown from the keys 1, …, n is the binary notation of the number n. Let n = 1b₁b₂…bH−1 in binary, H the number of digits. Then the right branch from the root consists of H nodes v₁, …, vH, the last of them a leaf, and on the left of vj (for j < H) hangs a perfect tree of height aj = H − 1 − j + bj. Inserting the next key is adding one to n: if the notation has a zero, exactly one rotation; if not, the height grows without rotations. Hence the height is H, there are n − H rebalancings, and a walk along the right branch finds the depth of a key.
5Walkthrough
Why it is built this way. We prove the claim by induction on n. For n = 1 the tree is one leaf, H = 1. First note that the subtree rooted at vj has height H − j + 1: on its left is a perfect tree of height at most H − j, on its right the rest of the branch, of height H − j. The balance of vj (left height minus right) is bj − 1, that is, 0 or −1, and the tree really is an AVL tree.
Insert the key n + 1. It is larger than all others and becomes the right child of the leaf vH. Suppose the notation of n has a zero, and let m be the position of the last zero: bm = 0, and all digits after it are ones. Climb from vH: every vj with j > m had balance 0, its right branch grew, so the balance is −1, the height grew, and we go on. At vm the balance was −1, and the right branch grew to H − m + 1 against a left one of H − m − 1: a lean. The right child vm+1 leans right (on its left a perfect tree of height H − m − 1, on its right now H − m), so this is case RR, one left rotation. After the rotation vm gets two perfect trees of height H − m − 1 on the left and right and itself becomes the root of a perfect tree of height H − m, and vm+1 takes its place. The height of the subtree is unchanged, and nothing changes above.
The new right branch is v₁, …, vm−1, vm+1, …, vH and the new leaf, H nodes again. The number n + 1 has the same digits up to position m, a 1 at position m, and zeros after it. Check the formula: at position m there is now a node with a perfect tree of height H − m = H − 1 − m + 1; at a position p > m stands the former vp+1 with a tree of height H − 1 − (p + 1) + 1 = H − 1 − p + 0; the last is a leaf. Everything agrees.
If instead n = 2H − 1 and all digits are ones, all nodes of the branch were level, each gets balance −1 and becomes higher, there are no rotations, and the height of the tree grows to H + 1. The branch is extended by the new leaf, and n + 1 = 10…0 with H zeros: the heights on the left are H − j = (H + 1) − 1 − j + 0, and the formula holds.
The answers. The height is H, the number of binary digits of n. A rebalancing happens at every insertion except those where the new n is a power of two, and there are exactly H of those among 1, …, n: n − H in total. For 19,073 records that is 15 and 19,058, just what the article's listing counted. The key of the node vj is one more than all keys to its left: vj = vj−1 + 2aj (with v₀ = 0). Walk along the branch while k > vj. If k = vj, the depth is j. Otherwise k lies in the perfect tree to the left of vj with keys vj−1 + 1, …, vj − 1; let m = k − vj−1. In a perfect tree of height a with keys 1, …, 2a − 1 the root is 2a−1, and the key m lies at depth a minus the number of trailing zeros in the binary notation of m. The answer is j + aj − (trailing zeros of m).
5+Solution
6Complexity
O(log n) per question: a branch of H ≤ 60 nodes. For random k the walk usually ends at the first nodes: the root's left tree holds at least 2H−2 − 1 keys, almost a quarter of all, and often more than half.
7Common mistakes
- A logarithm in floating point.
ceil(log2(n + 1))for n = 253 and above computes n + 1 without its last one: for n = 2⁶⁰ it gives 60 instead of 61. The number of digits is given exactly byn.bit_length()in Python andbits.Len64in Go. - Honest insertion. Even for 10⁶ records it works, but for 10¹⁸ never.
- The height “as for a perfect tree” without proving the depths. The height and the number of rotations can be guessed from small examples, but the depth of a particular key depends on the shape of the whole tree: without a formula for the left subtrees it cannot be found.
- Overflow. Keys up to 10¹⁸ fit in a 64-bit integer, and the sum of powers of two along the branch is also a key, at most n; adding in 32 bits will not do.