https://wiki.kram.nz/index.php?action=history&feed=atom&title=SE250%3ALab-2006-05-16%3Amgar059SE250:Lab-2006-05-16:mgar059 - Revision history2026-05-19T10:06:14ZRevision history for this page on the wikiMediaWiki 1.45.3https://wiki.kram.nz/index.php?title=SE250:Lab-2006-05-16:mgar059&diff=324&oldid=prevMark: 1 revision(s)2008-03-08T22:35:29Z<p>1 revision(s)</p>
<table style="background-color: #fff; color: #202122;" data-mw="interface">
<col class="diff-marker" />
<col class="diff-content" />
<col class="diff-marker" />
<col class="diff-content" />
<tr class="diff-title" lang="en-GB">
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">← Older revision</td>
<td colspan="2" style="background-color: #fff; color: #202122; text-align: center;">Revision as of 22:35, 8 March 2008</td>
</tr><tr><td colspan="4" class="diff-notice" lang="en-GB"><div class="mw-diff-empty">(No difference)</div>
</td></tr>
<!-- diff cache key mediawiki-mw_:diff:1.41:old-323:rev-324 -->
</table>Markhttps://wiki.kram.nz/index.php?title=SE250:Lab-2006-05-16:mgar059&diff=323&oldid=prevMark at 20:53, 23 July 20062006-07-23T20:53:24Z<p></p>
<p><b>New page</b></p><div>==Lab 9==<br />
<br />
===Red Black Trees===<br />
<br />
To rearrange a tree with the initail elements: + A B C D E F G H I J, a simple but slow method is the continue shift the root till each of the branch weights are balanced. Once this is achived, do the same with both branches and continue down till the entire tree is balanced. The process for the first step is as follows.<br />
<br />
> root<br />
> <<<br />
> root<br />
> <<<br />
> root<br />
> <<<br />
> root<br />
> <<<br />
<br />
<br />
<br />
===Slow Method===<br />
#Keep rotating the root till half of the tree is on each side.<br />
#Balance each side in the same manner.<br />
<br />
<br />
<br />
====Add an element to unbalance the tree:====<br />
<br />
For some of these images the red and black nodes are the wrong way around.<br />
<br />
[[Image:mgar059250lab1.jpg]]<br />
<br />
Add K to make the tree unbalance on the right hand side.<br />
<br />
K is a red node and J is also set to red. This means the tree is unbalanced and has to rotate.<br />
<br />
I is rotated left<br />
<br />
[[Image:mgar059250lab2.jpg]]<br />
<br />
I becomes Red and J becomes Black<br />
<br />
[[Image:mgar059250lab3.jpg]]<br />
<br />
<br />
F is the middle element, so to completely balance the tree, it needs to be shifted around to be the root<br />
<br />
[[Image:mgar059250lab4.jpg]]<br />
<br />
Remove G so the tree becomes unbalanced.<br />
<br />
[[Image:mgar059250lab5.jpg]]<br />
<br />
Rotate H left and recolour nodes<br />
<br />
[[Image:mgar059250lab6.jpg]]<br />
<br />
Is it always possible to re-balance the tree on the path to the root? <br />
<br />
<br />
Properly balanced tree<br />
[[Image:mgar059250lab7.jpg]]<br />
<br />
<br />
==Questions==<br />
<br />
====Question 1====<br />
Adding an element and deleting it again can change the height of the tree as red black trees are not always compact. Adding an element could cause the tree to be rotate such that the paths shorten and when the element is removed, the tree remains at a shorter height.<br />
<br />
====Question 2====<br />
Adding an element can cause a reduction in the height of the tree as red black trees are not always compact. Adding an element could cause the tree to be rotate such that the paths shorten causing a reduction in height.<br />
<br />
====Question 3====<br />
Deleting an element in the tree cannot increase the size of the tree as the rotations are all designed to reduce height.<br />
<br />
====Question 4====<br />
When adding the sting value "10" the code places it after the 9 instead of between the "1" and "2". As such there must be code which intreprets stings to be numbers if possible and then treats them as integers.</div>Mark