R. (Rajamani) Sundar.

Twists, turns, cascades, deque conjecture, and scanning theorem online

. (page 1 of 3)
Online LibraryR. (Rajamani) SundarTwists, turns, cascades, deque conjecture, and scanning theorem → online text (page 1 of 3)
Font size
QR-code for this ebook

Computer Science Department


Twists, Turns, Cascades, Deque Conjecture,
and Scanning Theorem

R. Sundar

Technical Report 427

January 1989

- CN


t3 C
(0 to



ICJ (0
Ico (^

lo u




(0 (U



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

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


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) <

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

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

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

1 3

Online LibraryR. (Rajamani) SundarTwists, turns, cascades, deque conjecture, and scanning theorem → online text (page 1 of 3)