Mark: 18 revision(s)

2008-11-03T05:20:22Z

18 revision(s)

New page

==Task 1==
Familiarizing with the given codes were tough. However the commands and introduction given were rather simple, however I find it irritating how the tree are displayed in the cmd prompt, it was REALLY irritating to navigate through, even for a short tree.... as the tree aren't displayed properly and you would have to first navigate through them to figure out which values went where...

*Note: the "parent" command seen to not work..., jumping 2 nodes above instead of 1.
*Note: actually, after going through Task 2, the tree's appearance seen to become clear, except the orientation of the nodes seen to be off, right = down, left = up. Whereas if right = up, left = down, makes more sense as tilting your head on the side gives you the tree.

==Task 2==
*Inserting the char in the given order "d b f a c e g" gives a perfectly balanced tree:

<pre>
d
__/ \__
b f
/ \ / \
a c e g
</pre>

*Inserting the char in an order such that:
<pre>
"d" is inserted first
"b" and "f" are inserted next
"a" "c" "e" "g" are inserted last
</pre>
gives a perfectly balanced tree, ie. inserting the tree in "level order".

*Any other order simply will not work due to the code not manipulating the tree and comparing the values to be inserted with the parent of the base nodes.

==Task 3==
*Skewing the tree gives the expected shape of a linked list:
<pre>
a
\
b
\
c
\
d
\
e
\
f
\
g
</pre>

*Rotating left on Node a, should give:
<pre>
b
/ \
a c
\
d
\
e
\
f
\
g
</pre>
which was right when the tree is printed:
<pre>
a (*)
b
c
d
e
f
g
</pre>

==Task 4==
Again, this was all fun and game, rotating each nodes left and right... blah blah blah...

==Task 5==
This was pretty random... the following commands were repeated until the last nodes is flipped into position.
*rl //rotating the root node left
*root //moves the targeted nodes to the new root node
*rl
*root
.
.
.
.
.
.
.

Result should look like:
<pre>
g
/
f
/
e
/
d
/
c
/
b
/
a
</pre>
Result printed in cygwin:
<pre>
a
b
c
d
e
f
g (*)
</pre>

==Task 6==
In order to achieve a perfectly balanced tree from a right skewed tree, the following were done.

1)Point the node to the root.
2)Rotate left.
3)Repeat 1) and 2) until the root node is d.
4)Place the node to c (the left children of the root node d).
5)Rotate right on root c, putting c under b and in the same level as a.
6)Place the node to e (the right children of the root node d).
7)Rotate left on root e, putting e under f and in the same level as g.

==Task 7==
Starting with the balanced tree, adding h and i.
<pre>
a
b
c
d (*)
e
f
g
h
i
</pre>
Reshaping the tree in such a way that e is the root node with left children and right children at it's longest length(ie back tracking task 6).
<pre>
a
b
c
d
e (*)
f
g
h
i
</pre>
Then perform a similar procedure as task 6, to achieve a balanced tree.
<pre>
a
b
c
d
e (*)
f
g
h
i
</pre>
Alternatively, a "balanced" tree with the same length could b obtained simply by rotating left on node g in the first diagram to produce the following.
<pre>
a
b
c
d
e
f
g (*)
h
i
</pre>

==Task 8==
Yes, it is possible, because when removing or adding elements into the tree, only the subtree containing the added/removed element are altered. Therefore it can be balanced simply by transversing along the subtree that is affected.

SE250:lab-7:twon069 - Revision history

Mark: 18 revision(s)