https://wiki.kram.nz/index.php?action=history&feed=atom&title=SE250%3Alab-7%3Ahlin079SE250:lab-7:hlin079 - Revision history2026-04-29T10:23:44ZRevision history for this page on the wikiMediaWiki 1.45.3https://wiki.kram.nz/index.php?title=SE250:lab-7:hlin079&diff=7601&oldid=prevMark: 10 revision(s)2008-11-03T05:20:15Z<p>10 revision(s)</p>
<p><b>New page</b></p><div>====task1====<br />
root-> the starting node<br />
left->left hand side of the current node<br />
right->right hand side of the current node<br />
parent->parent node of the current node<br />
<pre><br />
i toke me a while to figured out how to insert elements<br />
</pre><br />
====task2====<br />
the order i used for this task is (d,b, a,c,f,e,g).<br />
the order of insertion can be start with the right hand side of d (f).<br />
the order of the insertion of (a&c)and (e&g) do not matter.<br />
====task3&task 4====<br />
rl command moved the right of the current node to parent postion.<br />
rr command moved the left of the current node to parent positon.<br />
the elements are in the same order before and after rl and rr command.<br />
skewed and rotated left: <br />
Before rotation: <br />
<br />
a (*)<br />
b<br />
c<br />
d<br />
e<br />
f<br />
g<br />
Order Before rotation: Tree[a,b,c,d,e,f,g] <br />
<br />
After rotation: <br />
<br />
a<br />
b (*)<br />
c<br />
d<br />
e<br />
g<br />
Order after rotation: Tree[a,b,c,d,e,f,g] .<br />
rl command moved the right of the current node to parent postion.<br />
rr command moved the left of the current node to parent positon.<br />
the elements are in the same order before and after rl and rr command.<br />
<br />
====task5====<br />
after right skew the tree, i used <br />
<pre><br />
move the node to b use rl<br />
move the node to a by root use two rl<br />
move the node to c by root use two rl<br />
move the node to e by root use rl<br />
move the node to f by root use rl<br />
</pre><br />
====task 6====<br />
changing from right <br />
a<br />
b<br />
c<br />
d<br />
e <br />
f<br />
g (*)<br />
to perfect balance tree<br />
a<br />
b<br />
c <br />
d(*)<br />
e<br />
f<br />
g<br />
This was achieved by <br />
<pre><br />
move the node to b use rl<br />
move the node to a use two rl<br />
move the node to the new root c use a rl then a rr<br />
move to d by root command <br />
move to right ->e use rl<br />
move the node to g use rl<br />
</pre> <br />
Thus, perfect balance was achieved.<br />
====task7====<br />
adding 2 elements larger than the largest node into a perfectly balanced tree and using minimum rotations to achieve a perfectly balanced tree <br />
a<br />
b<br />
c<br />
d<br />
e<br />
f<br />
g (*)<br />
h<br />
i<br />
<br />
<br />
To balance this tree i moved the node to g and used the rl command to produced this tree: <br />
<br />
a<br />
b<br />
c<br />
d<br />
e<br />
f<br />
g (*)<br />
h<br />
i<br />
Is it always possible to rebalance the tree by performing rotations only on nodes along this path?</div>Mark