SE250:lab-7:hpan027

Initial problem

The write command did not work. Possibly due to the graphviz package not being installed on the lab computers. Had to go to their website to download the programme and manually convert the .dot files.

Balanced tree

http://studwww.cs.auckland.ac.nz/~hpan027/250-7-1.jpg

Input order: d b e a c f g

• The order only matters by level - the tree will still remain perfectly ordered if you shuffle the order within levels (e.g. d f b e c a g)

Rotating a skewed tree

Pre-rotation:

http://studwww.cs.auckland.ac.nz/~hpan027/250-7-2.jpg

Tree[a,b,*c*,d,e,f,g]

Post-rotation:

http://studwww.cs.auckland.ac.nz/~hpan027/250-7-3.jpg

Tree[a,b,*c*,d,e,f,g]

• Tree has been rotated to the left
• Order is still the same

Right skewed to left

http://studwww.cs.auckland.ac.nz/~hpan027/250-7-4.jpg

• Using "rl" then "p" until the tree is left skewed (i.e. always rotating the tree to the right with respect to the root)

http://studwww.cs.auckland.ac.nz/~hpan027/250-7-5.jpg

Right skewed into balanced

• Use "p" and "rl" as above until tree is as follows

http://studwww.cs.auckland.ac.nz/~hpan027/250-7-6.jpg

• Then perform "rr" operations on node c and "rl" on node e

http://studwww.cs.auckland.ac.nz/~hpan027/250-7-7.jpg

Rebalancing after two elements

http://studwww.cs.auckland.ac.nz/~hpan027/250-7-8.jpg

• "rl" on root

http://studwww.cs.auckland.ac.nz/~hpan027/250-7-9.jpg