*s = z->left; node *t = z->right; delete z; node *sMax = NULL; if (s) { s->parent = NULL; sMax = subtree_maximum(s); splay(sMax); root = sMax; } if (t) { if (s) sMax->right = t; else root = t; t->parent = sMax; } p_size--; } */ const T& minimum() { return subtree_minimum(root)->key; } const T& maximum() { return subtree_maximum(root)->key; } bool empty() const { return root == nullptr; } unsigned long size() const { return p_size; } }; #endif // SPLAY_TREE Analysis A simple amortized analysis of static splay trees can be carried out using the potential method. Define: size(r) = the number of nodes in the sub-tree rooted at node r (including r). rank(r) = log2(size(r)). Φ = the sum of the ranks of all the nodes in the tree. Φ will tend to be high for poorly balanced trees and low for well-balanced trees. To apply the potential method, we first calculate ΔΦ: the change in the potential caused by a splay operation. We check each case separately. Denote by rank' the rank function after the operation. x, p and g are the nodes affected by the rotation operation (see figures above). Zig step {| |- | ΔΦ || = rank'(p) − rank(p) + rank'(x) − rank(x) | [since only p and x change ranks] |- | || = rank'(p) − rank(x) | [since rank'(x)=rank(p)] |- | || ≤ rank'(x) − rank(x) | [since rank'(p)<rank'(x)] |} Zig-zig step {| | ΔΦ ||colspan=2| = rank'(g) − rank(g) + rank'(p) − rank(p) + rank'(x) − rank(x) |- | || = rank'(g) + rank'(p) − rank(p) − rank(x) | [since rank'(x)=rank(g)] |- | || ≤ rank'(g) + rank'(x) − 2 rank(x) | [since rank(x)<rank(p) and rank'(x)>rank'(p)] |- | || ≤ 3(rank'(x)−rank(x)) − 2 | [due to the concavity of the log function] |} Zig-zag step {| | ΔΦ ||colspan=2| = rank'(g) − rank(g) + rank'(p) − rank(p) + rank'(x) − rank(x) |- | || ≤ rank'(g) + rank'(p) − 2 rank(x) | [since rank'(x)=rank(g) and rank(x)<rank(p)] |- | || ≤ 3(rank'(x)−rank(x)) − 2 | [due to the concavity of the log function] |} The amortized cost of any operation is ΔΦ plus the actual cost. The actual cost of any zig-zig or zig-zag operation is 2 since there are two rotations to make. Hence: {| | amortized-cost || = cost + ΔΦ |- | || ≤ 3(rank'(x)−rank(x)) |} When summed over