SE250:lab-7:rwan064
Task 1
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.
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
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.
Commands:
> clear tree > i D > i F > i B > i A > i C > i E > i G > display
The final display command produces the output:
A
B
C
D (*)
E
F
G
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
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.
Commands:
> 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]
Task 4
Play around using left and right rotations to reshape the tree until you are confident you understand how they work.
Wierd stuff in the lab
After doing Task 3 I have a tree that looks like this:
A (*)
B
C
D
E
F
G
Then I tried the playing around with the rotations as it says on Task 4. I tried the commands:
> 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
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:
> 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
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>
