Mark: 15 revision(s)

2008-11-03T05:20:19Z

15 revision(s)

New page

== Task 1 ==

<pre>
Populate your tree with seven distinct elements, and navigate
around using “left”, “right”, “parent” and “root” until you are con-
fident you know what you are doing.
</pre>

This was quite easy as all you do to insert an element is "insert [element]". e.g. insert 2, to insert a "2" in the tree. And moving around the tree is quite trivial.

== Task 2 ==

<pre>
Clear the tree and insert the seven elements a–g in such an order
that the resulting tree is perfectly balanced. Record the order in
your lab report. Do any other insertion orders also result in a
perfectly balanced tree? Explain.
</pre>

Commands:
<pre>
> clear tree
> i D
> i F
> i B
> i A
> i C
> i E
> i G
> display
</pre>

The final display command produces the output:
<pre>
A
B
C
D (*)
E
F
G
</pre>

Do any other insertion orders also result in a perfectly balanced tree? '''No'''. Because there is only one median, lower quartile and upper quartile.

== Task 3 ==

<pre>
Skew the tree, then perform a left rotation on the root. Compare
the shape of the tree before and after the rotation. Confirm (using
"print") the elements appear in the same order before and after
the rotation.
</pre>

Commands:
<pre>
> skew
> print
Tree[*A*,B,C,D,E,F,G]
> display
A (*)
B
C
D
E
F
G
> root
> rotate left
> display
A (*)
B
C
D
E
F
G
> print
Tree[*A*,B,C,D,E,F,G]
</pre>

== Task 4 ==

<pre>
Play around using left and right rotations to reshape the tree until
you are confident you understand how they work.
</pre>
'''Wierd stuff in the lab'''

After doing Task 3 I have a tree that looks like this:
<pre>
A (*)
B
C
D
E
F
G
</pre>

Then I tried the playing around with the rotations as it says on Task 4. I tried the commands:
<pre>
> root
> display
A
B (*)
C
D
E
F
G
> right
> display
A
B
C (*)
D
E
F
G
> rotate left
A
B
C (*)
D
E
F
G
> parent
A
B (*)
C
D
E
F
G
</pre>

The selected node was "C" and the command '''parent''' (which moves to the parent of the selected node) moved to the node "B"!!! And clearly after the rotation, "B" should not be C's parent. Also I tried the following commands to verify the tree:
<pre>
> root
> left
> display
A (*)
B
C
D
E
F
G
> parent
> display
A
B (*)
C
D
E
F
G
> right
> display
A
B
C
D (*)
E
F
G
> parent
> display
A
B (*)
C
D
E
F
G
> right
> left
> display
A
B
C (*)
D
E
F
G
> parent
> display
A
B (*)
C
D
E
F
G
</pre>

Again, '''C''''s parent appears to be '''B'''! This means that '''B''' has three children! Which means it is not a proper Binary Search Tree. Although '''B''' does not "know" about the node '''C'''. i.e. there is no pointer to node '''C''' from the node '''B'''. But there is a pointer (the pointer to the parent) to node '''B''' from '''C'''. Which means the tree '''actually''' looks like this:

<html>
<img src="http://studwww.cs.auckland.ac.nz/~rwan064/lab7/se250lab7task4.png" width="422" height="499" alt="se250-lab7-task4-tree" />
</html>

SE250:lab-7:rwan064 - Revision history

Mark: 15 revision(s)