|T||:||BST on which we are performing a splay|
|insertion or retrieval|
|Ti||:||tree T as it has been transformed after|
|step i of the splaying process, with T0 = T|
|x||:||any node in Ti|
|Ti(x)||:||subtree of Ti with root x|
|| Ti(x)|||:||number of nodes of Ti(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 ri(x).
are positive real numbers with
log + log 2log - 2 (*)
This can be easily proved as follows:
|log + log 2log - 2|
If the ith splaying step is a zig-zig or a zag-zag step at node x, then its amortized complexity ai satisfies
ai < 3(ri(x) - ri - 1(x))
See Figure 4.26.
|ai||=||ti + Ci - Ci - 1|
|=||2 + ri(x) + ri(y) + ri(z)|
|- ri - 1(x) - ri - 1(y) + ri - 1(z)|
|=||2 + ri(y) + ri(z) - ri - 1(x) - ri - 1(y) ( )|
= | Ti - 1(x)|, = | Ti(z)|, and = | Ti(x)|. Then observe that + . This is because
Ti - 1(x) contains components x, A, B
|Ti(z) contains components z, C, D|
Thus by (*)
If the ith splaying step is a zig-zag or zag-zig at node x, then its amortized complexity ai satisfies
ai < 2(ri(x) - ri - 1(x))
If the ith splaying step is a zig or a zag, then
ai < 1 + (ri(x) - ri - 1(x))
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,
|ai||=||ai + ak|
|3(ri(x) - ri - 1(x)) + (1 + 3rk(x) - 3rk - 1(x))|
|=||1 + 3rk(x) - 3r0(x)|
|1 + 3rk(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.
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.
C0 - Cm
Also we know that
1 + 3logn for j = 1, 2,..., m
Thus the above becomes
Tj = 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.