The price of a log
A server keeps page paths in a splay search tree, keyed by the path’s number. Requests arrive one at a time. Count how many comparisons the tree makes over the whole log.
A request with key k is served like this. The search goes from the root: it compares k with the node’s key and goes left if k is smaller, right if it is larger; each visited node is one comparison. If the key is found, that is node x. If the search runs into an empty spot, a new leaf with key k is added there, and that is x, with as many comparisons as nodes visited on the way. In an empty tree the new key simply becomes the root with no comparisons.
Then x rises to the root. While x has a parent p:
- if p is the root, one rotation about the edge x–p;
- if x and p are both left children or both right ones, first a rotation of p about its parent, then a rotation of x about p;
- otherwise two rotations of x in a row: about p, then about its new parent.
A rotation lifts a node one level up while keeping the order of keys: this is how a splay tree works.
Two tests are real web server logs of the Kennedy Space Center for July 1995, with each path replaced by its number in alphabetical order.
In the second example the insertions 1, 2, 3, 4, 5 in increasing order cost one comparison each, with the root, and the tree stretches into a path. The repeated pass in increasing order is expensive at first, five comparisons to reach key 1, but lifting by pairs of rotations folds the path in half, and the total comes to 19 comparisons.
Input
The first line holds n (1 ≤ n ≤ 100,000), the number of requests. The second holds n keys, integers from 1 to 109.
Output
A single number: how many comparisons the tree makes over all the requests.
Examples
Example 1
7 5 3 8 3 5 1 3
12
Example 2
10 1 2 3 4 5 1 2 3 4 5
19
Limits
- Time · Python
- 8000 ms
- Time · Go
- 1500 ms
- Memory
- 256 MB
- Judging
- 12 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
The task is to implement the tree from the statement faithfully. Think about how to store the nodes so that a rotation is a few assignments, and how to find the parent and grandparent.
2Hint 2
Could x be lifted by single rotations, which is simpler and also reaches the root? Work it out on the second example.
3The idea
Each node has four fields: key, left child, right child, parent. A rotation of x about its parent p moves the inner subtree of x over to p, makes p a child of x and puts x in the place of p under the grandparent. Lifting to the root is a loop over the three cases of the statement. The order of rotations in the “both left” case matters: first the parent, then x. It is exactly this that folds a long path in half and gives amortised O(log n) per request; single rotations give the same tree only on short paths.
4Walkthrough
It is convenient to keep the nodes in parallel arrays and refer to them by index, with −1 for an empty link. The search goes from the root and adds a leaf if the key is absent; comparisons are counted by visited nodes. The answer can exceed 231: in the worst case it is of order n log n with a constant, on the tests about two million, but it is better to take a 64-bit number from the start.
On the server log a request costs about 6.9 comparisons on average, while a balanced tree on the same 2230 paths would spend about ten: the popular paths stay near the root. On the “increasing, twice” test the splay tree spends about three comparisons per request.
4+Solution
5Complexity
O(n log n) amortised, by the access lemma from the article.
6Common mistakes
- Single rotations. “Move to root” by rotations about the parent is the same thing only for short paths. On the second example it gives 23 comparisons instead of 19, and on keys in increasing order twice, of order n2: the long path does not fold, and the second pass walks it in full on every request. That is
wrong.py. - The wrong order in the “both left” case. Rotating x first and then x again gives the same lift by single rotations.
- Forgetting the parent. After a rotation three “upward” links change: those of x, of p and of the middle subtree.