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
