Mark: 4 revision(s)

2008-11-03T05:20:13Z

4 revision(s)

New page

== task1 ==

for this task we had to populate the tree with the seven elements a-g.
such that the resulting tree would be perfectly balanced ..
the order i tried out was [d b f a c e g] .. other orders also work .. such as
[d f b c a g e] .. as we inserted the median of the values first .. and then inserting either b or f
first doesn't really matter as they are the median of the right and left remaining sides.
same reasoning for inserting a or c first .. or .. e or g first .

(this task was particulary easy and nothing was challenging )

== task2 ==
i entered the elements and then used SKEW command ..
the order of the tree was ( Tree[a,b,c,d,e,f,g] )

i then performed a left rotation on the root .. and printed the tree to get
( Tree[a,b,c,d,e,f,g] )

which shows that the rotation doesn't effect the overall order
of the binary tree.

== task3 ==

i inserted the elements 1-7 in this order
[1,2,3,4,5,6,7] to get a right skewed data.

we were asked to convert the tree into a left skewed tree
i did this by performing :
<pre>left rotation on the root "1".
then using root to move to node "2"
left rotation on the root "2".
then using root to move to "3".
left rotation on the root "3".
then using root to move to node "4"
left rotation on the root "4".
then using root to move to node "5"
left rotation on the root "5".
then using root to move to node "6"
left rotation on the root "6".
</pre>

== task4 ==
we were asked to balance a right skewed tree
by performing a number of rotation and movements
i did this by performing:
<pre>left rotation on the root "1".
then using root to move to node "2"
left rotation on the root "2".
then using root to move to "3".
left rotation on the root "3".
</pre>

although this tree is balanced it's still not a good binary tree because it's too high.
to make it more balanced .. most of the branches should have 2 childern .. to minimise the height ..
therefore minimising the look up time.

== task5 ==
<pre>
Starting with a balanced tree of seven elements, add two new elements
each larger than the current maximal element and then
rebalance the tree using a minimal number of rotations.
</pre>

i started by adding the elements [ 4,2,6,1,3,5,7]
then added [8,9]

and then to make the tree balanced ..
<pre>i moved away from the root using RIGHT twice .. then performed a rotate left .</pre>
to make the tree balanced ( the total difference is 1 level therefore it's a balanced tree )

http://aamranovich.googlepages.com/test1.jpg

SE250:lab-7:aomr001 - Revision history

Mark: 4 revision(s)