Page 165 - DCAP605_ADVANCED_DATA_STRUCTURE_AND_ALGORITHMS

Advanced Data Structure and Algorithms

Notes 7.2 Operations

Splay trees support the following operations. We write S for sets, x for elements and k for key
values.
splay(S, k) returns an access to an element x with key k in the set S. In case no such element
exists, we return an access to the next smaller or larger element.

split(S, k) returns (S_1,S_2), where for each x in S_1 holds: key[x] <= k , and for each y in S_2
holds: k < key[y].
join(S_1,S_2) returns the union S = S_1 + S_2. Condition: for each x in S_1 and each y in S_2: x
<= y.
insert(S,x) augments S by x.

delete(S,x) removes x from S.
Each split, join, delete and insert operation can be reduced to splay operations and modifi cations
of the tree at the root which take only constant time. Thus, the run time for each operation is
essentially the same as for a splay operation.

7.3 Splay Operation

The most important tree operation is splay(x), which moves an element x to the root of the tree. In
case x is not present in the tree, the last element on the search path for x is moved instead.

The run time for a splay(x) operation is proportional to the length of the search path for x. While
searching for x we traverse the search path top-down. Let y be the last node on that path. In a
second step, we move y along that path by applying rotations as described later.

The time complexity of maintaining a splay tree is analyzed using an Amortized Analysis.
Consider a sequence of operations op_1, op_2, ..., op_m. Assume that our data structure has a
potential. One can think of the potential as a bank account. Each tree operation op_i has actual
costs proportional to its running time. We’re paying for the costs c_i of op_i with its amortized
costs a_i. The difference between concrete and amortized costs is charged against the potential
of the data structure. This means that we’re investing in the potential if the amortized costs are
higher that the actual costs, otherwise we’re decreasing the potential.
Thus, we’re paying for the sequence op_1, op_2, ..., op_m no more than the initial potential plus
the sum of the amortized costs a_1 + a_2 + ... + a_m.
The trick of the analysis is to defi ne a potential function and to show that each splay operation
has amortized costs O (ln (n)). It follows that the sequence has costs O (m ln (n) + n ln (n))

7.4 Rotations

The splay operation moves the accessed element x to the root of the tree T. This is done using
rotations on x and parent y and grandparent z.
There are two kinds of double rotations and one single rotation. Due to symmetry, we need
mirror-image versions of each rotation.
Type 1: x < y < z , or z < y < x respectively

Type 2: y < x < z , or z < x < y respectively.
Type 3: The last case deals with the situation that the splay node x is a child of the root. Thus, we
need a single rotation.

x < y , or y < x respectively.

160 LOVELY PROFESSIONAL UNIVERSITY