https://wiki.kram.nz/index.php?action=history&feed=atom&title=SE250%3Alab-7%3Asdal039SE250:lab-7:sdal039 - Revision history2026-04-29T01:16:11ZRevision history for this page on the wikiMediaWiki 1.45.3https://wiki.kram.nz/index.php?title=SE250:lab-7:sdal039&diff=7806&oldid=prevMark: 12 revision(s)2008-11-03T05:20:19Z<p>12 revision(s)</p>
<p><b>New page</b></p><div>Balanced order: <br />
d b a c f e g<br />
d f e g b a c<br />
d c b a e f g<br />
d c a b e g f<br />
d a b c g f e<br />
<br />
There are quite a few more, all starting with d as the root. This is enough to give the idea however...<br />
<br />
<br />
Rotations to get from right skewed to left skewed tree:<br />
Rotate left on root until finished.<br />
<br />
<br />
Rotations to get from right skewed tree to balanced:<br />
right, right, right, right<br />
rotate left - at e<br />
root<br />
rotate left - at a<br />
root, right<br />
rotate left - at c<br />
root<br />
rotate left - at b<br />
<br />
Difficulty in this was determining which node was the selected, as the (*) was sometimes positioned ambiguously. <br />
<br />
<br />
Add in two new elements and balance<br />
insert h<br />
insert i<br />
<br />
Need to make e the root<br />
starting at root:<br />
right - now at f<br />
rotate right <br />
root - now at d<br />
rotate left<br />
root<br />
right<br />
right - now on g<br />
rotate left<br />
<br />
Tree is now of minimum height.<br />
<br />
<br />
<br />
When an element is added or deleted, the insert function traverses<br />
a path from the root to the leaf. Is it always possible to rebalance<br />
the tree by performing rotations only on nodes along this path?<br />
<br />
This isn't always true. If you have the tree<br />
d<br />
b e<br />
f<br />
g<br />
h<br />
<br />
and add in the element 'a' the resulting tree will be<br />
d<br />
b e<br />
a f<br />
g<br />
h<br />
<br />
It is not possible to rebalance this tree without rotating elements in the roots right sub tree.</div>Mark