SE250:Lab-2006-05-16:mgar059

Lab 9

Red Black Trees

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.

> root
> <<
> root
> <<
> root
> <<
> root
> <<

Slow Method

1. Keep rotating the root till half of the tree is on each side.
2. Balance each side in the same manner.

Add an element to unbalance the tree:

For some of these images the red and black nodes are the wrong way around.

File:Mgar059250lab1.jpg

Add K to make the tree unbalance on the right hand side.

K is a red node and J is also set to red. This means the tree is unbalanced and has to rotate.

I is rotated left

File:Mgar059250lab2.jpg

I becomes Red and J becomes Black

File:Mgar059250lab3.jpg

F is the middle element, so to completely balance the tree, it needs to be shifted around to be the root

File:Mgar059250lab4.jpg

Remove G so the tree becomes unbalanced.

File:Mgar059250lab5.jpg

Rotate H left and recolour nodes

File:Mgar059250lab6.jpg

Is it always possible to re-balance the tree on the path to the root?

Properly balanced tree File:Mgar059250lab7.jpg

Questions

Question 1

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.

Question 2

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.

Question 3

Deleting an element in the tree cannot increase the size of the tree as the rotations are all designed to reduce height.

Question 4

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.