R. (Rajamani) Sundar. # Twists, turns, cascades, deque conjecture, and scanning theorem online

. **(page 1 of 3)**

Online Library → R. (Rajamani) Sundar → Twists, turns, cascades, deque conjecture, and scanning theorem → online text (page 1 of 3)

Font size

Computer Science Department

TECHNICAL REPORT

Twists, Turns, Cascades, Deque Conjecture,

and Scanning Theorem

R. Sundar

Technical Report 427

January 1989

- CN

W

t3 C

(0 to

O

CO

I C

IK OS

â– r-

ICJ (0

Ico (^

lo u

D

CO

B

0)

o

(0 (U

3

â€¢Â»-p

CO O 0)

c 12, and proved that it

is tight for infinitely mcmy n.

In this paper, we perform a combinatorial analysis of sequences of various rotational

operations on binary trees and thereby derive an 0{{m + n)a{m + n)) bound for the deque

conjecture. This approach is very different from that of Lucas [4], which exploits the simi-

larity between splaying and certain set union algorithms. Our approach seems more general

for it is able to handle the complete set of deque operations and arbitrary initial trees. We

study the following binary tree operations (See Fig. 3):

Right t'wist: For any A; > 1, a right fc-twist arbitrarily selects k different edges from a left

subpath^ of the binary tree and rotates the edges one after another in top-to-bottom

order.

Right turn: For any A; > 1, a right A:-turn is a right A:-twist that converts a left subpath of

k edges in the binary tree into a right subpath by rotating the edges of the subpath

in top-to-bottom order.

Right cascade: For any k > 1, a. right A;-cascade is a right A;-twist that rotates every other

edge lying on a left subpath of 2k â€” 1 edges in the binary tree.

A right twist sequence (abbreviated RT-sequence) is a sequence of right twists performed on

a binary tree. Define Uk{n), Ck{n) and Tk{n), respectively, to be the maximum number of

A;-turns, A;-cascades and /;-twists in any RT-sequence performed on an n-node binary tree.

These numbers are well defined since, after 0{n'^) right rotations, the tree is transformed

into a right path and no further right rotations can be performed. We derive the following

almost tight bounds for Uk{n), Ck{n) and Tk{n):

Upper bound

Lower bound

Ukin)

Ck{n)

1 0(""L)b/2j(")) if ^7^ 3

[ 0(n log log n) if A; = 3

1 fi(nd|^^/2j("))- 4Ai{j).

Case 2. i >2 and j = l:

K2^{l) = 2iK2i-2ii)

> 8iAi^i{i) (By the Induction Hypothesis)

> 4Ai(l).

Case 3. i>2 and j > 2:

K2i{j) = AVi - l)i^2.-2(A'2.0- - l)/4)/2

> 8Ai{j â€” l)A,_i(A,(j â€” 1)) (By the Induction Hypothesis)

> 4A.(i).H

When n is of the form Kk{j), the following lemma derives the bound for Uk(n).

Lemma 3 Uk{Kk{j)) < 4jKk{j), for all k > I and j > 1.

Proof. We use double induction on k and j .

Case 1. 1 < k < 2: The lemma follows from the bounds U-[{n) < nao{n) and U2{n) <

ndi(n).

Case 2. k > 3 and j = 1: We need to show that UkiKkil)) < 47\ ;.(!). Consider a

binary tree B having A'fc(l) nodes on which an RT-sequence is performed. Divide B into

a sequence of Kk-2{\_k/2\)/2 blocks of size 2k each. Each fc-turn is of one of the following

types:

Type A. All nodes involved in the fc-tum are from the same block: Since a block has

only 2k nodes, there is at most one such fc-turn per block.

Type B. Some two nodes of the fc-turn are from the same block: Let C denote the block

tree of this block. The A;-turn causes either an increase in the size of the right path of C, or

a decrease in the size of the left path of C, or both. Hence the number of type B A;-turns is

at most 2Kk{l}-

Type C. Each node of the fc-turn is from a different block: To handle this case, we

label the root of each block global. The global nodes in B induce a binary tree G, called

the global tree. The root of G is identical to the root of B. The left child of a node a; in G

is the highest global node in the left subtree of x in B. The right child of a node is defined

similarly. It is easy to see that the left and right children of any node in G are unique. The

effect of a rotation in 5 on G is analogous to the effect of such a rotation on a block tree

o{ B: A rotation in B translates into a rotation in G if both the nodes of the rotation are

global; otherwise, G is unaffected. (If a rotation changes the root of a block then the global

role passes from the old root to the new root but this does not affect the global tree.)

Suppose that the A;-turn turns the left subpath Xi â€” X2 â€” â€¢ â€¢ â€¢ â€” Xk^i of B into a right

subpath. Since all x,s are from different blocks, the nodes X2,X3,...,xt are all global.

Therefore, the fc-turn results in a (A; â€” 2)-turn in G (if xi or Xjt+i is also global, then some

right rotations axe also performed in G.) The number of (k â€” 2)-turns in G is at most

Uk-2iKk.2ilk/2i)/2) < Uk-2(Kk.2ilk/2\))/2 (By Lemma 1)

< 2L/:/2jAV2(UV2j) (By the Induction Hypothesis)

< /u(l).

This gives an upper bound of /u(l) for the number of type C fc-turns in B.

Summing together the above bounds for the three types of ^-turns, we obtain a bound

of

Kk.2ilk/2\)/2 + 2/u(l) + /u(l) < 4A',(1)

for the total number of A:-turns in the RT-sequence. This completes Case 2.

Case 3. k > 3 and j > 2: Here we divide the binary tree on which the RT-sequence is

executed into Kk{j)/Kk{j - 1) blocks of size Kk{j - 1) each. We spHt the A;-turns into the

three types defined in Case 2 and obtain the following tally for each type of turn:

Number of type A fc- turns

- "F~r"37T â€¢'*(â€¢? ~ â– ^)-^^'*(.? ~ 1) (By the Induction Hypothesis)

< 4(j-l)Jffc(j).

Number of type B A;-turns < 2Kk{j).

Number of type C A;-turns

< Uk.2{Kk.2iKk{j-l)/4)/2)

â– < Uk-2{Kk-2{Kk{j -\)lA))/2 (By Lemma 1)

< Kkij - l)Kk-2{KkU - l)/4)/2 (By the Induction Hypothesis)

= Kkij).

Hence the total number of A;-turns in the sequence is at most

4(i - l)Kk(j) + 2KkU) + KkU) < 4jKk{j).

This finishes Case 3. H

Using the three lemmas we obtain the bound for Uk{n) for any k and n:

Theorem 1

t^.(n) 1 and j > 1. Referring to the

proof of Lemma 3, only the handling of cases 2 and 3 has to be modified. Consider Case 2.

As before, the blocks have size 2k each. The fc-ceiscades axe categorized as follows:

Type A. All nodes involved in the cascade are from the seime block: There is at most

one type A cascade per block.

Type B. One of the cascade rotations involves a pair of nodes from the same block:

If the cascade rotates an edge that lies on the left path of some block, then the length of

the left path of the block decreases by at least 1. Alternately, if the lowest three nodes

involved in the cascade are from the same block, then the number of nodes in that block

whose left depth is at most 1 increases. We conclude that the number of type B cascades

falling under the above categories is at most 2Kk{l) â€” Kk-2{lk/2\ ). In every remaining type

B fc-cascade, only the lowest cascade rotation is intrablock and the lowest three nodes do

not belong to the same block. Each such cascade behaves like a type C cascade in that it

causes a. (k â€” 2)-cascade on the global tree (defined below) which accounts for it.

Type C. The nodes participating in any cascade rotation are from distinct blocks: In

this case for each block, in addition to the root of the block, we also label the left child of

the root in- the block global, if it exists (if the root has no left child, then the right child of

the root is global.) Right rotations are propagated from the original tree to the global tree

as described in Lemma 3 except in the following situation: When the edge joining the root

and its left child, say /, in a block is rotated, the left child of /, say //, now becomes global,

and if // is not adjacent to / in B, this results in a series of right rotations in the global tree

(See Fig. 6). Under this definition of global tree, the (k - 2) interior rotations performed

by any type C fc-cascade are ail globed. Hence, each type C fc-cascade translates into a right

(k â€” 2)-cascade and a set of right rotations in the global tree.

Therefore the total number of fc-cascades in the sequence is at most

Kk.2ilk/2\)/2 + 2K,{1) - AV2(L^/2J) + Ck-2iKk-2(lk/2])) < 47x^(1).

This completes Case 2 in the proof of Lemma 3 for cascades. Case 3 is handled similarly. I

2.2 Lower bounds

As in the upper bound construction, we need a new Ackerman-like hierarchy of functions

to prove the lower bounds for Uk{n). Define:

Biij) = j forallj>l

BjO) = 2^-1 for all j > 1

_ J 1 if i > 3 and j = 1

^â€¢U) - I ((^ + i>^jB,{j - 1) + l)5,_2((t + l)iB.(i - 1)) if z > 3 and j > 2

TECHNICAL REPORT

Twists, Turns, Cascades, Deque Conjecture,

and Scanning Theorem

R. Sundar

Technical Report 427

January 1989

- CN

W

t3 C

(0 to

O

CO

I C

IK OS

â– r-

ICJ (0

Ico (^

lo u

D

CO

B

0)

o

(0 (U

3

â€¢Â»-p

CO O 0)

c 12, and proved that it

is tight for infinitely mcmy n.

In this paper, we perform a combinatorial analysis of sequences of various rotational

operations on binary trees and thereby derive an 0{{m + n)a{m + n)) bound for the deque

conjecture. This approach is very different from that of Lucas [4], which exploits the simi-

larity between splaying and certain set union algorithms. Our approach seems more general

for it is able to handle the complete set of deque operations and arbitrary initial trees. We

study the following binary tree operations (See Fig. 3):

Right t'wist: For any A; > 1, a right fc-twist arbitrarily selects k different edges from a left

subpath^ of the binary tree and rotates the edges one after another in top-to-bottom

order.

Right turn: For any A; > 1, a right A:-turn is a right A:-twist that converts a left subpath of

k edges in the binary tree into a right subpath by rotating the edges of the subpath

in top-to-bottom order.

Right cascade: For any k > 1, a. right A;-cascade is a right A;-twist that rotates every other

edge lying on a left subpath of 2k â€” 1 edges in the binary tree.

A right twist sequence (abbreviated RT-sequence) is a sequence of right twists performed on

a binary tree. Define Uk{n), Ck{n) and Tk{n), respectively, to be the maximum number of

A;-turns, A;-cascades and /;-twists in any RT-sequence performed on an n-node binary tree.

These numbers are well defined since, after 0{n'^) right rotations, the tree is transformed

into a right path and no further right rotations can be performed. We derive the following

almost tight bounds for Uk{n), Ck{n) and Tk{n):

Upper bound

Lower bound

Ukin)

Ck{n)

1 0(""L)b/2j(")) if ^7^ 3

[ 0(n log log n) if A; = 3

1 fi(nd|^^/2j("))- 4Ai{j).

Case 2. i >2 and j = l:

K2^{l) = 2iK2i-2ii)

> 8iAi^i{i) (By the Induction Hypothesis)

> 4Ai(l).

Case 3. i>2 and j > 2:

K2i{j) = AVi - l)i^2.-2(A'2.0- - l)/4)/2

> 8Ai{j â€” l)A,_i(A,(j â€” 1)) (By the Induction Hypothesis)

> 4A.(i).H

When n is of the form Kk{j), the following lemma derives the bound for Uk(n).

Lemma 3 Uk{Kk{j)) < 4jKk{j), for all k > I and j > 1.

Proof. We use double induction on k and j .

Case 1. 1 < k < 2: The lemma follows from the bounds U-[{n) < nao{n) and U2{n) <

ndi(n).

Case 2. k > 3 and j = 1: We need to show that UkiKkil)) < 47\ ;.(!). Consider a

binary tree B having A'fc(l) nodes on which an RT-sequence is performed. Divide B into

a sequence of Kk-2{\_k/2\)/2 blocks of size 2k each. Each fc-turn is of one of the following

types:

Type A. All nodes involved in the fc-tum are from the same block: Since a block has

only 2k nodes, there is at most one such fc-turn per block.

Type B. Some two nodes of the fc-turn are from the same block: Let C denote the block

tree of this block. The A;-turn causes either an increase in the size of the right path of C, or

a decrease in the size of the left path of C, or both. Hence the number of type B A;-turns is

at most 2Kk{l}-

Type C. Each node of the fc-turn is from a different block: To handle this case, we

label the root of each block global. The global nodes in B induce a binary tree G, called

the global tree. The root of G is identical to the root of B. The left child of a node a; in G

is the highest global node in the left subtree of x in B. The right child of a node is defined

similarly. It is easy to see that the left and right children of any node in G are unique. The

effect of a rotation in 5 on G is analogous to the effect of such a rotation on a block tree

o{ B: A rotation in B translates into a rotation in G if both the nodes of the rotation are

global; otherwise, G is unaffected. (If a rotation changes the root of a block then the global

role passes from the old root to the new root but this does not affect the global tree.)

Suppose that the A;-turn turns the left subpath Xi â€” X2 â€” â€¢ â€¢ â€¢ â€” Xk^i of B into a right

subpath. Since all x,s are from different blocks, the nodes X2,X3,...,xt are all global.

Therefore, the fc-turn results in a (A; â€” 2)-turn in G (if xi or Xjt+i is also global, then some

right rotations axe also performed in G.) The number of (k â€” 2)-turns in G is at most

Uk-2iKk.2ilk/2i)/2) < Uk-2(Kk.2ilk/2\))/2 (By Lemma 1)

< 2L/:/2jAV2(UV2j) (By the Induction Hypothesis)

< /u(l).

This gives an upper bound of /u(l) for the number of type C fc-turns in B.

Summing together the above bounds for the three types of ^-turns, we obtain a bound

of

Kk.2ilk/2\)/2 + 2/u(l) + /u(l) < 4A',(1)

for the total number of A:-turns in the RT-sequence. This completes Case 2.

Case 3. k > 3 and j > 2: Here we divide the binary tree on which the RT-sequence is

executed into Kk{j)/Kk{j - 1) blocks of size Kk{j - 1) each. We spHt the A;-turns into the

three types defined in Case 2 and obtain the following tally for each type of turn:

Number of type A fc- turns

- "F~r"37T â€¢'*(â€¢? ~ â– ^)-^^'*(.? ~ 1) (By the Induction Hypothesis)

< 4(j-l)Jffc(j).

Number of type B A;-turns < 2Kk{j).

Number of type C A;-turns

< Uk.2{Kk.2iKk{j-l)/4)/2)

â– < Uk-2{Kk-2{Kk{j -\)lA))/2 (By Lemma 1)

< Kkij - l)Kk-2{KkU - l)/4)/2 (By the Induction Hypothesis)

= Kkij).

Hence the total number of A;-turns in the sequence is at most

4(i - l)Kk(j) + 2KkU) + KkU) < 4jKk{j).

This finishes Case 3. H

Using the three lemmas we obtain the bound for Uk{n) for any k and n:

Theorem 1

t^.(n) 1 and j > 1. Referring to the

proof of Lemma 3, only the handling of cases 2 and 3 has to be modified. Consider Case 2.

As before, the blocks have size 2k each. The fc-ceiscades axe categorized as follows:

Type A. All nodes involved in the cascade are from the seime block: There is at most

one type A cascade per block.

Type B. One of the cascade rotations involves a pair of nodes from the same block:

If the cascade rotates an edge that lies on the left path of some block, then the length of

the left path of the block decreases by at least 1. Alternately, if the lowest three nodes

involved in the cascade are from the same block, then the number of nodes in that block

whose left depth is at most 1 increases. We conclude that the number of type B cascades

falling under the above categories is at most 2Kk{l) â€” Kk-2{lk/2\ ). In every remaining type

B fc-cascade, only the lowest cascade rotation is intrablock and the lowest three nodes do

not belong to the same block. Each such cascade behaves like a type C cascade in that it

causes a. (k â€” 2)-cascade on the global tree (defined below) which accounts for it.

Type C. The nodes participating in any cascade rotation are from distinct blocks: In

this case for each block, in addition to the root of the block, we also label the left child of

the root in- the block global, if it exists (if the root has no left child, then the right child of

the root is global.) Right rotations are propagated from the original tree to the global tree

as described in Lemma 3 except in the following situation: When the edge joining the root

and its left child, say /, in a block is rotated, the left child of /, say //, now becomes global,

and if // is not adjacent to / in B, this results in a series of right rotations in the global tree

(See Fig. 6). Under this definition of global tree, the (k - 2) interior rotations performed

by any type C fc-cascade are ail globed. Hence, each type C fc-cascade translates into a right

(k â€” 2)-cascade and a set of right rotations in the global tree.

Therefore the total number of fc-cascades in the sequence is at most

Kk.2ilk/2\)/2 + 2K,{1) - AV2(L^/2J) + Ck-2iKk-2(lk/2])) < 47x^(1).

This completes Case 2 in the proof of Lemma 3 for cascades. Case 3 is handled similarly. I

2.2 Lower bounds

As in the upper bound construction, we need a new Ackerman-like hierarchy of functions

to prove the lower bounds for Uk{n). Define:

Biij) = j forallj>l

BjO) = 2^-1 for all j > 1

_ J 1 if i > 3 and j = 1

^â€¢U) - I ((^ + i>^jB,{j - 1) + l)5,_2((t + l)iB.(i - 1)) if z > 3 and j > 2

Online Library → R. (Rajamani) Sundar → Twists, turns, cascades, deque conjecture, and scanning theorem → online text (page 1 of 3)