https://wiki.kram.nz/index.php?action=history&feed=atom&title=SE250%3Alab-7%3Avpup001SE250:lab-7:vpup001 - Revision history2026-05-02T18:37:11ZRevision history for this page on the wikiMediaWiki 1.45.3https://wiki.kram.nz/index.php?title=SE250:lab-7:vpup001&diff=7943&oldid=prevMark: 22 revision(s)2008-11-03T05:20:22Z<p>22 revision(s)</p>
<p><b>New page</b></p><div>This lab is about balancing binary search trees.<br />
The code is run by using GNU compiler.<br />
==Task 1==<br />
I have inserted the numbers, "4,5,6,7,3,2" and the tree looks like this...<br />
<br />
2<br />
3<br />
4 (*)<br />
5<br />
6<br />
7<br />
<br />
The '(*)' next to the element '4' means it is the node.<br />
<br />
When we use the command 'left' the node moves one step down to left child (left child is selected).<br />
<br />
2<br />
3 (*)<br />
4 <br />
5<br />
6<br />
7<br />
<br />
When we use the command 'right' the node moves one step down to right child (right child is selected).<br />
<br />
2<br />
3<br />
4 <br />
5 (*)<br />
6<br />
7<br />
<br />
If there is no right or left child to that particular node then nothing is selected.<br />
<br />
When we use the command 'root', the root of the tree should be selected (in this case 4).<br />
<br />
2<br />
3<br />
4 (*)<br />
5<br />
6<br />
7<br />
<br />
When we use the command 'parent', the parent should be selected. For example if (*) is next to '6' and we used parent command, it should be displayed next to '5' (since 5 is the parent of 6)<br />
<br />
2<br />
3<br />
4 <br />
5 (*)<br />
6<br />
7<br />
<br />
*The command 'delete' is supposed to delete the element '(*)' is pointing to but its deleting the root!!!!<br />
*The parent is not working properly. If the (*) is pointing to 7 and we used parent command it is pointing to 5 when it is suppose to point to 6 (since 6 is the parent of 7).<br />
<br />
==Task 2==<br />
<br />
Inserting elements a-g such that the tree is perfectly balanced.<br />
<br />
The order of insertion was... "d,b,c,a,f,g,e"<br />
a<br />
b<br />
c <br />
d (*)<br />
e<br />
f<br />
g<br />
<br />
There are other orders of inserting elements which result in a perfectly balanced tree but the root should always be 'd' and the children of 'd' should always be 'b' and 'f'. We can insert the other elements in any order.<br />
<br />
The other orders of insertion are...<br />
<br />
"d,b,a,c,f,e,g"<br />
<br />
"d,f,b,g,e,c,a" and so on...<br />
<br />
*The order of insertion differs but the order is always the same which is "Tree[a,b,c,*d*,e,f,g]".<br />
<br />
==Task 3==<br />
<br />
The perfectly balanced tree...<br />
<br />
a<br />
b<br />
c <br />
d (*)<br />
e<br />
f<br />
g<br />
<br />
The order of the tree is printed by using 'print' command.<br />
<br />
Tree[a,b,c,*d*,e,f,g]<br />
<br />
The tree is skewed by using 'skew' and it looks like this...<br />
<br />
a (*)<br />
b<br />
c<br />
d<br />
e<br />
f<br />
g<br />
<br />
The order...<br />
<br />
Tree[*a*,b,c,d,e,f,g]<br />
<br />
When a left rotation is performed on the root...<br />
<br />
a <br />
b (*)<br />
c<br />
d<br />
e<br />
f<br />
g<br />
<br />
The order is...<br />
<br />
Tree[*a*,b,c,d,e,f,g]<br />
*The order of the tree is the same before and after the rotation. It is the structure of the tree that changes (root changes).<br />
<br />
==Task 4==<br />
<br />
"rotate left" rotates the selected node to left and "rotate right" rotates the selected node to right.<br />
<pre><br />
> rl<br />
a (*)<br />
b<br />
c<br />
d<br />
e<br />
f<br />
g<br />
> root<br />
a<br />
b (*)<br />
c<br />
d<br />
e<br />
f<br />
g<br />
<br />
> rl<br />
a<br />
b (*)<br />
c<br />
d<br />
e<br />
f<br />
g<br />
<br />
> parent<br />
a<br />
b<br />
c (*)<br />
d<br />
e<br />
f<br />
g<br />
<br />
> rr<br />
a<br />
b<br />
c (*)<br />
d<br />
e<br />
f<br />
g<br />
<br />
> rl<br />
a<br />
b<br />
c (*)<br />
d<br />
e<br />
f<br />
g<br />
</pre><br />
*In the last tree, I have used 'rl' when 'c' was selected so the tree rotates from c (the whole tree doesn't rotate)!!</div>Mark