Mark: 4 revision(s)

2008-11-03T05:20:21Z

4 revision(s)

New page

== 1 ==

Inserting the elements in the order: d b f a c e g
produces the tree

<Pre> a
b
c
d (*)
e
f
g
</Pre>

As explained during class; this was done by inserting the median first (in the sequence abcdefg), followed by the upper and lower medians.
No other orders for '''this particular''' sequence will produce a balanced tree. I think

== 2 ==

Taking the balanced tree

<Pre> a
b
c
d (*)
e
f
g
</Pre>

then rotating left produces

<Pre> a
b
c
d (*)
e
f
g
</Pre>

Skewing the sequence

<Pre>a (*)
b
c
d
e
f
g
</Pre>

then performing the left rotation produces

<Pre> a (*)
b
c
d
e
f
g
</Pre>

The order appears to be the same: a b c d e f g

Only the root nodes are different, this is expected because skewing the sequences sets the root at a while the balanced tree has the root at d, the median. Perhapes I misunderstood the question?

== 3 ==

I looked up the HTTB and got a good idea of how rotations work.

Starting with a right skew

<Pre>a (*)
b
c
d
e
f
g
</Pre>

Ending with a left skew

<Pre> a
b
c
d
e
f
g (*)
</Pre>

I understood that a left skew will start with the highest value as the root and move down decreasing.
At first I inserted the values in the order of g f e d c b a to produce a left skew, then i realised it wasn't what the question was asking.

i used the commands

>rotate left

>root

>rotate left

>root

>rotate left

>root

>rotate left

>root

>rotate left

>root

>rotate left

>root

== 4 ==

Starting with a balanced tree

<Pre>
a
b
c
d (*)
e
f
g
</Pre>

>right

>right

>right

>right

<Pre>a
b
c
d
e (*)
f
g
</Pre>

> rotate left

<Pre>a
b
c
d
e (*)
f
g
</Pre>

>root

>rotate left

>root

>rotate left

>root

>rotate left

<Pre> a
b
c (*)
d
e
f
g
</Pre>

>rotate right

<Pre>
a
b
c
d (*)
e
f
g
</Pre>

SE250:lab-7:tlou006 - Revision history

Mark: 4 revision(s)