Splay Trees Advanced)

Splay Trees by Amna Humayun

Splay Trees Self-adjusting form of binary search tree.  A splay rotation consist of a sequence of rotations. 

They follow the heuristic Move to the root

Rotation Rotation plays an important role in Splay trees. Types of rotation:  Left-Rotation  Right-Rotation

Left-Rotation P P c

c x

b

b

x

b a

b

a

Right-Rotation P P x x

c a

a

c

b

b

b

b

Use of Splay Trees In many applications, when a node is accessed, it is likely to be accessed again in the near future.

The central idea of splay is If a node is deep, there are many node on the path that are relatively deep, and then restructuring make future accesses cheaper on all these nodes.

Types of Splay Trees Bottom-Up Splay Trees  Top-Down Splay Trees 

Bottom-Up Splay Trees

Bottom-Up Splay Trees  

 

Similar to binary search tree. Search, insert and delete operations are performed in the same way, except that they are followed by splay. In split, however first splay is performed. Bottom-up splay rotations are performed along the path from the start node to the root of the binary search tree.

Simple idea One way of performing restructuring is to perform single rotations, bottom-up. Rotate every node on the access path with its parent.

Example — Search(p1) 

Search(p1) p5 g

p4 p3 p2 b

f e

p1 c

d c

Example — Search(p1) 

Perform single rotation bottom-up. p5 g

p4 p3 p2 b

f e

p1 c

d c

Example — Search(p1) 

Perform single rotation bottom-up. p5 g

p4 p3 p2 bp2

f e

p1 c p2

d c

b

c

Example — Search(p1) 

Perform single rotation bottom-up. p5 g

p4 p3 p1

b

e d

p2 c

f

Example — Search(p1) 

Perform single rotation bottom-up. p5 g

p4 p3 p1 p2 b

f e p3

d p3 c d

d

e

Example — Search(p1) 

Perform single rotation bottom-up. p5 g

p4 p1 p3

p2 b

f

e

c d d

Example — Search(p1) 

Perform single rotation bottom-up. p5 g

p4 p1 p2 b

p4f p3 p4

c dp3 ef d p3 e d d e d

Example — Search(p1) 

Perform single rotation bottom-up. p5 p1 p2 b

g p4

c p3

f e

d d

Example — Search(p1) 

Perform single rotation bottom-up. p5 g

p1 p4 p5

p2 b

p3

c d

f

p4e d p3

d

f e

Example — Search(p1) p5 g

p4 p3 p2 b

p1

e

p1 c

p5

p2

f b

p4

c

p3

d

g f

c Original Tree e

d d

The rotations have pushed p1 to the root, for easy future access. But, it has pushed another node p3 almost as deep as p1 used to be.

SPLAYING The splaying strategy is similar to rotation idea, except that it a little more selective about how rotations are performed.

Steps for Splay Let x be the node at which splay is being performed.  If x is a root, then splay terminates.  If x is a non-root node and x has parent (p) but no grandparent — zig case.  If x is a non-root node and x has both parent (p) and grandparent (g), then there are two cases: Zig-Zig Case Zig-Zag Case

Steps for Splay… ZIG CASE If x is the left child of p perform right rotation around p. P x

p Right-Rotation

x

a

c

c

a

b

b b

Steps for Splay… ZIG CASE (symmetric) If x is the right child of p perform left rotation around p. P c

p

x

Left-Rotation c

x

b

b

a b

a

Steps for Splay… ZIG-ZIG CASE If x is the left child of p, and p is also the left child of g.  Perform right rotation around g.  Perform right rotation around p.

p

g

p

g p x

a

d c

b

x a

a

x

d

g c b

a

ag

b

b

c c

p

c

d

Steps for Splay… ZIG-ZIG CASE (symmetric) If x is the right child of p, and p is also the right child of g.  Perform left rotation around g.  Perform left rotation around p.

p

g g g

a bp

a

p

bg

b

ax

c

b

d

b p c

a x

c d

a

x

d

c

Steps for Splay… ZIG-ZAG CASE If x is the left child of p, and p is the right child of g.  Perform right rotation around p.  Perform left rotation around g.

g

g g a

a

P

p

x

x d

b

c c

p d

c

b g

ap

c

P c

b

x

a

b d

d

Steps for Splay… ZIG-ZAG CASE (symmetric) If x is the right child of p, and p is the left child of g.  Perform left rotation around p.  Perform right rotation around g. g

g g

p d

p

a

pa

p a

x

x pb b

c

x

d

c

a

d

g c b

b a

b

c

Search 

If the search is successful, then it must end at a particular node and the start node of splay is that particular node.



If the search is unsuccessful, then it must end at some external node and the start node of splay is the parent of that external node.

Example Search(p1) — Using Splay  

Search(p1). Search is successful.

p5 g

p4 p3 p2 b

f e

p1 c

d c

Example Search(p1) — Using Splay 

Perform splay bottom-up from p1. p5 g

p4 p3 p2 b

f e zig-zag

p1 c

d

Example Search(p1) — Using Splay 

Perform splay bottom-up from p1. p5 g

p4 p3 p2 bp2

f e zig-zag

p1 c p2

d c

b

c

Example Search(p1) — Using Splay 

Perform splay bottom-up from p1. p5 g

p4 p3 p1

b

e d

p2 c

f

zig-zag

Example — Search(p1) 

Perform single rotation bottom-up. p5 g

p4 p3 p1 p2 b

f e p3

d p3 c d

d

e

Example Search(p1) — Using Splay 

Perform splay bottom-up from p1. p5 p4 p1

f p3

p2 b

zig-zig

g

e

c d d

f

Example Search(p1) — Using Splay 

Perform splay bottom-up from p1. p5 p4 p1

f

p5

p3

p2 b

zig-zig

g

e

c d d

f

Example Search(p1) — Using Splay 

Perform splay bottom-up from p1.

zig-zig

p4 p5

p1 p4 f p3

p2 b

e

c d d p3

e

d d

g

Example Search(p1) — Using Splay p5

p3 p2 b

f

p4

p2

e

p1 c

p1

g

p4

d

c Original Tree

b

p5

p3

c

e

d

f

g

d

Splaying not only moves the accessed node to the root, but also has the effect of roughly halving the depth of most nodes on the access path.

Insert 

If the element to be inserted is already present in the tree, then the start node of splay is the node containing that particular element.



If the element to be inserted is not present in the tree, then insert element in the tree and the start node of splay is the newly inserted node.

Insert(36)   

Search(36) Element not found. Insert 36. 16 16 9

5

31 31 13

20

37 37 35 35

40

36

Insert(36) 

Perform splay bottom-up from 36. 16 9

5

31 13

37

20

35 35 35

40

36

35

zig-zag

Insert(36) 

Perform splay bottom-up from 36. 16 9

5

31 13

37 37

20 36

35

zig-zag 40

Insert(36) 

Perform splay bottom-up from 36. 16 9

5

31 13

37 37

20 36

35

zig-zag 37 40 37 37 40

Insert(36) 

Perform splay bottom-up from 36. 16 16

zig-zig 31 31

9

5

13

20

36

35

37 37 40

Insert(36) 

Perform splay bottom-up from 36. 16 16

zig-zig 31 31

9

5

13

20

36

35

37 37 40

20

Insert(36) 

Perform splay bottom-up from 36. zig-zig

31 31 36

16 16

9

20

37 37

3135

40 5

13

35

Insert(36) 16 9

5

36 31

13

20

37 37

31 31 16 16

37 9

35 40

36 Original Tree

5

35 20

13

40

Delete 

If the element to be deleted is present in the tree, then the node containing that element is deleted, and the start node of splay is the parent of the deleted node.



If the element to be deleted is not present in the tree, unsuccessful search must end at some external node, and the start node of splay is the parent of that external node.

Delete(36)   

Search(36) Element found. Delete 36. 16 16 9

5

31 31 13

20

37 37 35 35

40

36

Delete(36) 

Perform splay bottom-up from parent of 36 i.e. 35.

16 zig-zag 9

5

31 13

20

37 37 35 35

40

Delete(36) 

Perform splay bottom-up from parent of 36 i.e. 35.

16 zig-zag 9

5

31 13

20

37 37 35 35 35

37 40 37 37 40

Delete(36) 

Perform splay bottom-up from parent of 36 i.e. 35.

16 zig-zag 9

5

31 31 13

20

35 35 37 37 40

Delete(36) 

Perform splay bottom-up from parent of 36 i.e. 35.

16 zig-zag 9

5

31 31 13

35 35

3120 31 31

37 37 40

20

Delete(36) 

Perform splay bottom-up from parent of 36 i.e. 35.

zig

16 16 9

5

35 35 13

31 31

37 37 40

20

Delete(36) 

Perform splay bottom-up from parent of 36 i.e. 35.

zig

16 16 9

5

35 35 16 31 31

13

37 37 40

20 31 31

20

Delete(36) 16 31 35 35 9

31

37 37

16 16 5

13

20

37

9

31 31

35 40 5 36 Original Tree

13

20

40

Delete(16)   

Search(16) Element found. Delete 16.

35 35 16 16

9

5

37 31 31

13

20

40 delete by copy

Delete(16)   

Search(16) Element found. Delete 16.

35 35 16

9

5

37 31 31

13

20

40

Delete(16) 

Perform splay bottom-up from parent of 16 i.e. 31. 35 35

zig-zag 20

9

5

37 31 31

13

40

Delete(16) 

Perform splay bottom-up from parent of 16 i.e. 31. 35 35

zig-zag 20 20 9

5

31 31

13 9

5

37

13

20

40

Delete(16) 

Perform splay bottom-up from parent of 16 i.e. 31. 35 35

zig-zag 31

20

9 5

13

37 40

Delete(16) 

Perform splay bottom-up from parent of 16 i.e. 31. 35 35

zig-zag 31

20

9 5

13

37 35

40

Delete(16) 35 16

9

35 31 35 37

31 31

5 13 20 Original Tree

20 40

9

5

35 37

13

40

Split (similar to search) Search the node on which split is to be performed.  

If the search is successful, then it must end at a particular node and the start node of splay is that particular node. If the search is unsuccessful, then it must end at some external node and the start node of splay is the parent of that external node. Split return two trees one contain all items in the tree less than or equal to searched node, the other tree contain all items in tree greater than searched node.

Split (at 40)  

Search(40) Search is successful. 70 80

30 20

80 50 20 40

39 35

60 43

Split (at 40) 

Perform splay bottom-up from 40. 70 zig-zag

80

30 20

80 50 20 40

39 35

60 43

Split (at 40) 

Perform splay bottom-up from 40. 70 zig-zag

80

30 20

50 20 40

39 35

60 50 43 50

43

60 43

Split (at 40) 

Perform splay bottom-up from 40. 70 zig-zag

80

30 20

20 40 39

35

50 43

60

Split (at 40) 

Perform splay bottom-up from 40. 70 zig-zag

30

3020

80

40 20 39 30

35 20

3943 43 39 35

35

50 60

Split (at 40) 

Perform splay bottom-up from 40. 70

zig

80

20 40 30 20

5070 39

43

60

35

50 43

60

Split (at 40) 

Perform split at 40.

20 40 30 20

70 39

35

43

80

50 60

Split (at 40) 70

20 40

70

80

30

30 20

80 50 20 40

39

60 43

35 Original Tree

20

39 35

80

50 43

60

Amortized Analysis 

Lemma If a + b ≤ c, and a and b are both positive integers, then loga + logb ≤ 2 logc -2

Proof By the arithmetic-geometric mean inequality, ab ≤ (a + b)/2 Thus ab ≤ c /2 Squaring both sides gives ab ≤ c2 /4 Taking logarithms of both sides log(ab) ≤ log(c2 /4) loga + logb ≤ 2 logc -2

Amortized Analysis 

Amortized Time (AmT) = Actual Time for the ith operation (AcT) + (Potential Cost of ith operation (Pi) – Potential Cost of (i-1)th operation (Pi-1) ) AmT = AcT + (Pi – Pi-1 )



Potential function

Ф(T) = iΣЄ Tlog s(i) where Then

s(i) = Number of descendants of i + i itself. r(i) = log s(i) (Rank of node i) Ф(T) = i ЄΣT r(i)

Benefit of the potential function A splay rotation can only change the rank of x , p and g. where r (x) and r '(x) is the rank before and after rotation.

Amortized Analysis Theorem The amortized time to splay a tree with root T at node x is at most 3( r(T) - r(x) ) +1= O(log N).



Proof If x is the root of T, then there are no rotations. Potential change = 0. AcT = 1 (cost to access the node) AmT = AcT + (Pi – Pi-1 ) AmT = 1 + 0

Amortized Analysis 

Cost of zig case

p x

AcT = 1 (cost of single rotation) Pi = r '(x)+ r '(p) Pi-1= r (x)+ r (p)

a

X c

b

Original Tree

a

p b

c

Final Tree

AmT = AcT + (Pi – Pi-1 ) AmT = 1 + r '(x)+ r '(p) - r (x) - r (p) since only x and p can change rank AmT ≤ 1 + r '(x) - r (x) since r (p) ≥ r '(p) AmT ≤ 1 +3( r '(x) - r (x)) since r' (x) ≥ r (x) For more detail

Amortized Analysis 

Cost of zig-zig case p

AcT = 2 (cost of double rotation) Pi = r '(x) + r '(p) + r '(g) Pi-1= r (x) + r (p) + r (g) AmT = AcT + (Pi – Pi-1 )

x

g

x

d

bp

a

c

b

ag

b

c

Original Tree

Final Tree

a

AmT = 2 + r '(x)+ r '(p) + r '(g) - r (x) - r (p) - r (g) since only x, p and g can change rank AmT = 2 + r '(p) + r '(g) - r (x) - r (p) AmT ≤ 2 + r '(p) + r '(g) - 2 r (x)

since r '(x) = r (g) since r (x) ≤ r (p)

AmT ≤ 2 + r '(x) + r '(g) - 2 r (x) —— (1)

since r '(x) ≥ r '(p)

d

Amortized Analysis 

x

g

Cost of zig-zig case p x

d

bp

a

c

b

ag

b

c

Original Tree

Final Tree

a

d

s '(x) +s '(g) ≤ s '(x)

from figure

log s '(x) + log s '(g) ≤ 2 log s '(x) -2 r '(x) + r '(g) ≤ 2 r '(x) – 2

from lemma by definition of rank

AmT ≤ 2 + r '(x) + r '(g) – 2 r (x)

Putting the value in equation 1

AmT ≤ AmT ≤ 2 + r '(x) + r '(g) + r (x) – 3 r (x) AmT ≤ 3( r '(x) - r (x) )

For more detail

Amortized Analysis 

g

Cost of zig-zag case AcT = 2 (cost of double rotation) Pi = r '(x) + r '(p) + r '(g) Pi-1= r (x) + r (p) + r (g)

a

x p

x b

g

ap

d c

a

Original Tree

b c

d

Final Tree

AmT = AcT + (Pi – Pi-1 ) AmT = 2 + r '(x)+ r '(p) + r '(g) - r (x) - r (p) - r (g) since only x, p and g can change rank AmT = 2 + r '(p) + r '(g) - r (x) - r (p)

since r '(x) = r (g)

AmT ≤ 2 + r '(p) + r '(g) - 2 r (x) —— (1)

since r (x) ≤ r (p)

Amortized Analysis 

Cost of zig-zag case

g a

x p

x b

g

ap

d c

a

Original Tree

b c

d

Final Tree

s '(p) +s '(g) ≤ s '(x)

from figure

log s '(p) + log s '(g) ≤ 2 log s '(x) -2 r '(p) + r '(g) ≤ 2 r '(x) – 2

from lemma by definition of rank

AmT ≤ 2 + r '(p) + r '(g) – 2 r (x)

Putting the value in equation 1

AmT ≤ 2( r '(x) - r (x) ) AmT ≤ 3( r '(x) - r (x) )

since 2( r '(x) - rFor (x) more ) ≤ 3(detail r '(x) - r (x) )

Amortized Analysis Since the last splaying step leaves x at the root T. The amortized bound of entire splay is

3( r '(T) - r (x)) + 1 = O( log N)

Top-Down Splay Trees

Top-Down Splay Trees… 

Similar to bottom-up search trees, top-down splay trees consists of a sequence of rotations.



Splay rotations are performed along the path from root to the splay node (start node of bottom-up splay tree) of the binary search tree.

Steps for Splay Partition the binary search tree into three components.   

Original Tree Right Tree (R) Left Tree (L)

x

L null null

p

c

R r

null null

q

L and R are initially empty. They are reassembled with the new root of the original tree in the end.

Steps for Splay Reassemble    

Attach left child of the new root of original tree as the right child of largest element in L. Attach right child of the new root of original tree as the left child of smallest element in R. Attach right child of L as the left child of new root of original tree. Attach left child of R as the right child of new root of original tree.

Steps for Splay…   

Let x be a node. If x is the splay node, then splay terminates. If x is a non- splay node and x has child (c) — zig case. If x is a non-splay node and x has both child (c) and grandchild (gc), then there are two cases: Zig-Zig Case Zig-Zag Case

Steps for Splay… ZIG CASE   

If c is the left child of x. Attach x and its right child as a left child of the smallest item in R. x is the new smallest item in R. c is now the new root of original tree.

x

L null null

p

c

R

L

null null

null null

x

r

q

R null

c

p

r

q

null

Steps for Splay… ZIG CASE (symmetric)   

If c is the right child of x. Attach x and its left child as a right child of the largest item in L. x is the new largest item in R. c is now the new root of original tree.

L

R

x

null null

null null

p

null

r

R

x

null null

null

p

c

q

L

c

q

r

Steps for Splay… For the zig case to apply

  

c needs not to be a leaf node. If the item to be searched for is smaller than c, and c has no left child but has a right child. If the item to be searched for is greater than c, and c has no right child but has a left child.

Steps for Splay… ZIG-ZIG CASE    

If gc is the left child of c and c is the left child of x. Perform right rotation around x. Attach c and its right child as a left child of the smallest item in R. c is the new smallest item in R. gc is now the new root of original tree. x

L

L

R

R

c

null null

c

null null

gc

s null

null

gc

x

r p

p

null null

q

q

r

s

Steps for Splay… ZIG-ZIG CASE (symmetric)    

If gc is the right child of c and c is the right child of x. Perform left rotation around x. Attach c and its left child as a right child of the largest item in L. c is the new largest item in L. gc is now the new root of original tree. L

x

L

R

R null null

null null

null null

c

null null

bc

p

x q

agc

agc

r

s

p

q

r

s

Steps for Splay… ZIG-ZAG CASE   

If gc is the left child of c and c is the right child of x. Attach x and its left child as a right child of the largest item in L. x is the new largest item in L. c is now the new root of original tree. L

X

L

R

X

R

null null

null null null null

null null

p

C

C gc

gc

q

p

s

s r

q

r

Steps for Splay… ZIG-ZAG CASE (symmetric)   

If gc is the right child of c and c is the left child of x. Attach x and its right child as a left child of the smallest item in R. x is the new smallest item in R. c is now the new root of original tree. x

L null null

r s

c

p

gc

q

null null

L null null

null null

s

c

p r

R

x

gc

q

r

Search  

Let x is the node to be searched. Perform splay rotations along the path from root to the splay node (x). 





If the search is successful, then splay must end at a searched node, which is now the new root of the original tree. If the search is unsuccessful, then splay must end at a particular node greater than/ less than the node to be searched and this particular node is now the new root of the original tree.

Reassemble the three trees in the end.

Search(19) 

Search(19) by performing splay.

12 30 5

80 50 25 20

15 13

24 18

16

30

Search(19) 

Search(19) by performing splay.

12 30 12 L

null

5 null

80 50 25 25 20 20

15 13

30 24

18 16

R

null

null

Search(19) 

Search(19) by performing splay. zig-zag L

null

12 30 12 5

12 null

80 25 50 25 20 40 20

15 13

30 24

18 16

R

null

null

Search(19) 

Search(19) by performing splay.

zig-zig

80 25 50 25

L

R 40 20 20 12 30 12

null 5

null

15 15 13

30

24 18

16 24

null

Search(19) 

Search(19) by performing splay.

L

R

zig-zig 12 30 12

null

40 20 20

5

null 20

15 13

80 25 50 25 18

16

24

null

25 30

Search(19)  Element  Search(19) performing splay. not by found .

zig 15 15 L

R 13 12 30 12

null 5

18 18 16

40 20 20

null

null

15 80 25 50 25 24

30

Search(19) 

Reassemble.

18 18 L

R 16 12 30 12

null 5

40 20 20

null

15 15 13

80 25 50 25 24

30

Search(19) 

Reassemble.

18 18

L null

12 30 12 null 5

R

20 40 20 null

null

15 15 13

80 25 50 25 16

24

30

Search(19) 12 30 18 40 20

12 30 5

5

15 13

20 15

80 25 50 16

24

30

13

18

Original Tree

25

12

30 24

16 Top-Down Splay Tree

20 18

50 80 25

15 20

5 13

16

Bottom-Up Splay Tree

Insert      

Let x is the node to be inserted. Create a new node (z). If tree is empty, a one-node tree is created. Otherwise perform splay rotations along the path from root to the splay node (x). If the element to be inserted is already present in the tree, then discard the z. If the element to be inserted is not present in the tree. 

If the new root of original tree contains a value larger than the z 



Attach new root and its right subtree to the right of a z.

If the new root of original tree contains a value smaller than the z 

Attach new root and its left subtree to the left of a z.

Insert(80) 

80

Create a new node 80 50 30

10

60 40

90

20

70

65

100

Insert(80) 

Search(80) by performing splay. 50

L

zig-zig

30 null

80

60 60

null

null 10

R

40

90 90

20

70

65

100

null

Insert(80) 

Search(80) by performing splay. 50

L

zig-zig

30 null

80

60

null

null 10

R

40

90

20

70

65

100

null

Insert(80) 

80

Search(80) by performing splay. L

zig-zig

60 60 null

60 null

null

50 90

50

30 70 10

40 20

65

100

R

null

Insert(80)  

80

Search(80) performing splay. Element not by found . 90

L

null

60 60 50

30

10

40 20

70 70

65

zig 100

null

R

null

null

Insert(80)   Element not found . Search(80) by performing

90

L

null

30

10

40 20

70

60 60 50

80

splay.

zig

R

100 null 90

65

null

Insert(80) 

Insert 80.



70 < 80

80 70

L 60 60

null 50 30

10

40 20

65

R

90 90

null 100

Insert(80)  Attach 70 and its left sub tree to the left of 80.

70

L null

60 60 50

30

10

40 20

65

80

70

R

90 90

null 100

Insert(80) 

Reassemble.

80 70 70

L

null

60 60 50

30

10

40 20

65

R

90 90

null 100

Insert(80) 

Reassemble. L

null

80

null 60 60 50

65 10

40 20

null 90 90 70 70

30

R

null 100

Insert(80) 80 60 50

30

90 70

80 50

50

100

30

10

40

30 10

20

65 Top-Down Splay Tree

Original Tree

85

70

100

65

70 100

65 10 40

50

90 90

20

90

20 60

60 60

40 20

Bottom-Up Splay Tree

Insert(33) 

33

Create a node 33. 16 16

31 31

9

5

13

20

37 37 35

40 36

Insert(33) 

33

Search 33 by performing splay. 16 16

zig-zig

L 31 31

9 null

R

null

null 5

13

20

37 37 35

40 36

null

Insert(33) 

Search 33 by per forming splay.

33 16 16

L

zig-zig 31 31

9 null

R

null

null 5

13

20

37 37 35

40 36

20

null

Insert(33) 

Search 33 by per forming splay.

33

L

zig-zig

R

31 31 null

31 null

null 37 37

16 16 16

35 9

40

20 36

5

13

null

Insert(33)  Search 33found by per Element not . forming splay.

L

null

31 31

35 35

?

5

20

13

zig

37 37

16 16

9

33

40

36

R

null

null

Insert(33) 

Search 33 by per forming splay.

33

L

R

zig 37 37

null

31 31

16 16

9

5

35 35

40 36

20

13

null 37

null

Insert(33)  

Insert 33. 35 > 33

33

35

L

null

31 31

5

20

13

36

37 37

null 40

16 16

9

R

Insert(33)  Attach 35 and its right sub tree to the right of 33. 33

null

31 31

5

20

13

36

36

37 37

null 40

16 16

9

R

35

35

L

Insert(33)  Reassemble. 33 35

L

null

31 31

5

20

13

36

37 37

null 40

16 16

9

R

Insert(33) 

Reassemble.

33

L

null

31 31 null

16 16

5

13

null 37 37

null

40

35 20

9

R

36

Insert(33) 33 31

16

9 5

37

35 20

33

16 16

36

31

31 31

9 40 5

37 37

13 20

35

Original Tree

9

40 36

13 Top-Down Splay Tree

16

5

20

37 35 37 36

13 Bottom-Up Splay Tree

40

Delete    

Let x be the node to be deleted. Perform splay rotations along the path from root to the splay node (x). If the element to be deleted is not present in the tree, the simply return. If the element to be deleted is present in the tree. 

If the left child of new root of original tree is null.   



If the left child of new root of original tree is not null.     



Make its right child the new root. Delete x. Reassemble. Find maximum from the left sub tree by performing splay. Make it the new root. Attach right child to it. Delete x. Reassemble.

If both the left and right of new root of original tree are null.  

Delete x. Reassemble L and R by attaching right child of L as the left child of smallest item in R.

Delete(70) 

Search(70) by performing splay.

45 29

15

50 40

20

85 70

95

80 75

83

Delete(70) 

Search(70) by performing splay.

45

L

zig-zig

29 null

R

50 50

null

null

15

40 20

85 85 70

95

80 75

83

null

Delete(70) 

Search(70) by performing splay.

45 50

L

zig-zig

29 null

R

50 60 null

null 15

40 20

90 85 70

95

80 75

83

null

Delete(70) 

Search(70) by performing splay.

L

zig-zig

50 60 50 null

null

null

45 50 90 85

45

29 70 15

95

40 80

20 75

83

R

null

Delete(70) 

Element found.

L

50 60

null

zig

90 85 70 70

45 50

95

80

29 75 15

40 20

83

R

null

null

Delete(70) 

Element found.

L

zig

90 85

R Empty

50 60

null

70 70

45 50

95

80

29 75 15

40 20

83

85 null

null

Delete(70)  

Left child of 70 is null. Make its right child the new root. 70 70

L 50 60

null 45 50 29

15

40 20

R 80

null 75

90 85 83

null 95

Delete(70) 

Delete 70.

70 70

L 50 60

null 45 50 29

15

40 20

80 75

R 83

90 85

null 95

Delete(70) 

Reassemble

80

L 50 60

null 45 50 29

15

40 20

75

R 83

90 85

null 95

Delete(70) 

Reassemble

80

L 50 60 null

null 45 50 29

15

40 20

R

90 85 null 75

83

null 95

Delete(70) 45

80 29 50 60 45 50

50

90 85 75

43 15

83

80

95

29

40 20

85 70

75 Top-Down Splay Tree

29

95

83

75

83

40

15

80

15 40 20

85

20 Bottom-Up Splay Tree

Original Tree

95

Delete(40) 

Search(40) by performing splay.

55 35

22

72 40

59

84

Delete(40) 

Search(40) by performing splay.



Element found. 55

L 35 35 null

zig-zag R 72

null

null 22

40 40

59

84

null

Delete(40)  

Search(40) by performing splay. Element found. 55

L 35 35 null

zig-zag R 72

null

55 null 22

40 40

59

84

null

Delete(40)  

Search(40) by performing splay. Element found.

L 22 null

zig

35 35

null35

R 40 55

null 72 59

84

Delete(40)  

Both left and right of 40 are null. Reassemble L and R by attaching right child of L as the left child of smallest item in R. 40

R

L

null

35 35 null 22

55 null

null 72 59

84

Delete(40) 

Delete 40.

40

L

R 55

null

null

null 35 35

22

72 59

84

null

Delete(40) 55 35

35

55 35

72

72

22

55 72

22

59

Top-Down Splay Tree

84

22

40

59 84

Original Tree

59 84 Bottom-Up Splay Tree

Delete(69) 

Search(69) by performing splay.

80 60

120 69

65 62

90 75

67

125

Delete(69)  

Search(69) by performing splay. Element found. 80

L

R 60 60

null

zig-zag

120

null

null 69 69

65 62

90 75

67

125

null

Delete(69)  

Search(69) by performing splay. Element found. 80

L

R 60 60

null

zig-zag

120

null 69 70

65 62

90 75

67

125

80 null

null

Delete(69) 

Search(69) by performing splay. zig L

null

60

R 69 70

60 null

80 65 62

75

null 120

67 90

125

Delete(69)  

Left child of 69 is not null. Find maximum from left subtree of 69 by performing splay. 69 70

L

null

R 65 65

60 62

75 80

67 67

120

L null

null

R 90 null

null

null

125

Delete(69)  

Left child of 69 is not null. Find maximum from left subtree of 69 by performing splay. 69 70

L

R 75

null

65 65

60 62

67

null 120

L null

80

zig

R 90 null

null

null

125

Delete(69)  

Left child of 69 is not null. Find maximum from left subtree of 69 by performing splay. 69 70

L

R 75

null

65 65

60 62

67

L null

80

zig

120

R

null

null

null

90 null

125

Delete(69) 

67 is now the new root.

69 70

L

R 75

null

67

60

80

67 L null 62

120

R

65 65 null

null

null

90 null

125

Delete(69) 

Attach right child of 69 as right child of 67.

69 70

L

R 75

null

67

60 65 65 62

80

null 120

90

125

Delete(69) 

Delete 69.

69 70

L

null

R

67

60 65 65 62

80 75

null 120

90

125

Delete(69) 

Reassemble.

L

null

R

67

60 65 65 62

80 75

null 120

90

125

Delete(69) 

Reassemble.

L

null

R

67

60 null 65 65 62

null 80 75

null 120

90

125

Delete(69) 67 60

62

60

80

65 65

67 65

80

75

69

120

90

65

125 62

Top-Down Splay Tree

120 90

60

80

125 62 67

120

75 67 Original Tree

75

90 125

Bottom-up Splay Tree

Amortized Cost Search O(logn) Insert O(logn) Delete O(logn)

References 

Daniel Dominic Sleator, Robert Endre Tarjan, “Self-Adjusting Binary Search Trees” ,Journal of the Association for Computing Machinery, Vol. 32, No. 3, July 1985, pp. 652-686.



Mark Allen Weiss, “Data Structures and Algorithm Analysis in C (2nd Edition)”, Addison-Wesley, 1995 .

Amortized Analysis 

p

Cost of zig case x AcT = 1 (cost of single rotation) Pi = r '(x)+ r '(p) Pi-1= r (x)+ r (p)

a

X c

a b

b

Original Tree

c

Final Tree

AmT = AcT + (Pi – Pi-1 ) since only x and p can change rank AmT = 1 + r '(x)+ r '(p) - r (x) - r (p) since r (p) ≥ r '(p) AmT ≤ 1 + r '(x)+ r '(p) - r (x) - r '(p) AmT ≤ 1 + r '(x) - r (x) since r '(x) ≥ r (x) AmT ≤ 1 +3( r '(x) - r (x))

p

Back

Amortized Analysis 

Cost of zig-zig case p

AcT = 2 (cost of double rotation) Pi = r '(x) + r '(p) + r '(g) Pi-1= r (x) + r (p) + r (g)

x

d c

b

ag c

Original Tree

Final Tree

since r '(x) = r (g) AmT = 2 + r '(x)+ r '(p) + r '(g) - r (x) - r (p) - r (g) AmT = 2 + r '(p) + r '(g) - r (x) - r (p) since r (x) ≤ r (p) AmT ≤ 2 + r '(p) + r '(g) - r (x) - r (x) AmT ≤ 2 + r '(p) + r '(g) - 2 r (x)

bp

a

b

a AmT = AcT + (Pi – Pi-1 ) since only x, p and g can change rank AmT = 1 + r '(x)+ r '(p) - r (x) - r (p)

x

g

Back

Next

d

Amortized Analysis 

Cost of zig-zig case x

g Since r '(x) ≥ r '(p) AmT ≤ 2 + r '(x) + r '(g) - 2 r (x) —— (1)

p x

from figure s (x) + s '(g) ≤ s '(x) from lemma log s (x) + log s '(g) ≤ 2 log s '(x) -2 by definition of rank r (x) + r '(g) ≤ 2 r '(x) - 2 Putting the value in equation 1 AmT ≤ 2 + r '(x) + r '(g) – 2 r (x) AmT ≤ 2 + r '(x) + r '(g) + r (x) – 3 r (x) AmT ≤ 2 + r '(x) + ( 2 r '(x) - 2 ) – 2 r (x) AmT ≤ 3( r '(x) - r (x) )

d c

bp

a b

ag

b

c

Original Tree

Final Tree

a

Back

d

Amortized Analysis 

Cost of zig-zag case AcT = 2 (cost of double rotation) Pi = r '(x) + r '(p) + r '(g) Pi-1= r (x) + r (p) + r (g)

g

x

a

p x

b

g

ap

d c

Original Tree

AmT = AcT + (Pi – Pi-1 ) since only x, p and g can change rank AmT = 2 + r '(x)+ r '(p) + r '(g) - r (x) - r (p) - r (g)

a

d

b c Final Tree

since r '(x) = r (g) AmT = 2 + r '(x)+ r '(p) + r '(g) - r (x) - r (p) - r (g) AmT = 2 + r '(p) + r '(g) - r (x) - r (p) since r (x) ≤ r (p) AmT ≤ 2 + r '(p) + r '(g) - r (x) - r (x) AmT ≤ 2 + r '(p) + r '(g) - 2 r (x) —— (1)

Back

Next

Amortized Analysis 

g

Cost of zig-zag case from figure s '(p) +s '(g) ≤ s '(x) from lemma log s '(p) + log s '(g) ≤ 2 log s '(x) -2 by definition of rank r '(p) + r '(g) ≤ 2 r '(x) - 2

a

x p

x b

g

ap

d c

Original Tree

a

b c Final Tree

Putting the value in equation 1 AmT ≤ 2 + r '(p) + r '(g) – 2 r (x) AmT ≤ 2 + ( r '(x) - 2 ) – 2 r (x) AmT ≤ 2( r '(x) - r (x) ) since 2( r '(x) - r (x) ) ≤ 3( r '(x) - r (x) ) AmT ≤ 3( r '(x) - r (x) )

Back

d