T | : | BST on which we are performing a splay |
insertion or retrieval | ||
T_{i} | : | tree T as it has been transformed after |
step i of the splaying process, with T_{0} = T | ||
x | : | any node in T_{i} |
T_{i}(x) | : | subtree of T_{i} with root x |
| T_{i}(x)| | : | number of nodes of T_{i}(x) |
For each step i of the splaying process and each vertex xT, we define rank at step i of x to be
For every node x of T and after every step i of splaying, node x has credit equal to its rank r_{i}(x).
If ,,
are positive real numbers with
+ ,
then
log
+ log
2log
- 2
(*)
This can be easily proved as follows:
- 0 | |||
log + log 2log - 2 |
If the i^{th} splaying step is a zig-zig or a zag-zag step at node x, then its amortized complexity a_{i} satisfies
a_{i} < 3(r_{i}(x) - r_{i - 1}(x))
See Figure 4.26.
a_{i} | = | t_{i} + C_{i} - C_{i - 1} | |
= | 2 + r_{i}(x) + r_{i}(y) + r_{i}(z) | ||
- r_{i - 1}(x) - r_{i - 1}(y) + r_{i - 1}(z) | |||
= | 2 + r_{i}(y) + r_{i}(z) - r_{i - 1}(x) - r_{i - 1}(y) ( ) |
Let
= | T_{i - 1}(x)|, = | T_{i}(z)|, and = | T_{i}(x)|. Then observe that + . This is because
T_{i - 1}(x) contains components x, A, B |
|||
T_{i}(z) contains components z, C, D | |||
T_{i}(x) . |
Thus by (*)
Result 2
If the ith splaying step is a zig-zag or zag-zig at node x, then its amortized complexity ai satisfies
a_{i} < 2(r_{i}(x) - r_{i - 1}(x))
Result 3
If the ith splaying step is a zig or a zag, then
a_{i} < 1 + (r_{i}(x) - r_{i - 1}(x))
Result 4
The total amortized cost over all the splaying steps can be computed by adding the costs of all the splay steps. If there are k such steps, only the last can be a zig or zag and the others are all zig-zag or zig-zag or zag-zig or zag-zag. Since (*) provides the weaker bound, we get,
a_{i} | = | a_{i} + a_{k} | |
3(r_{i}(x) - r_{i - 1}(x)) + (1 + 3r_{k}(x) - 3r_{k - 1}(x)) | |||
= | 1 + 3r_{k}(x) - 3r_{0}(x) | ||
1 + 3r_{k}(x) | |||
= | 1 + 3log n |
Thus the amortized cost of an insertion or retrieval with splaying in a BST with n nodes does not exceed 1 + 3log n upward moves of the target node in the tree.
Result 5
Now consider a long sequence of m splay insertions or retrievals. We seek to compute the actual cost of all these m operations.
Let Tj and Aj be the actual cost and amortized cost of the jthoperation, where j = 1, 2,..., m, now represents a typical insertion or retrieval operation.
We have
C_{0} - C_{m}
log n
Also we know that
A_{j}
1 + 3logn for j = 1, 2,..., m
Thus the above becomes
T_{j}
= m(1 + 3logn) + log n
The above gives the total actual time of m insertions or retrievals
on a tree that never has more than n nodes.
This gives O(log n) actual running time for each operation.