SE250:lab-7:Maintainers report

Intro

The purpose of this lab is to give us a hand on experience on building Binary Search Tree, and manipulating them.

Bugs

The code does not compile under Visual Studio or Emacs, this has to be done under cygwin.
The write command did not work, possibly due to lab computer not having graphic packages installed on them. (Taken from hpan027)
The parent command actually selects the parents parent.
The clear tree command crashes the program in windows.

Task 1

Most student had an easy time on this task, where all we had to do was fiddle around with each of the commands to familiarize ourselves with them.

The HELP command was a great help:

Commands:
QUIT -- exit the program
HELP -- display this message

ROTATE RIGHT -- right rotate on the selected node
ROTATE LEFT  -- left rotate on the selected node
BALANCE      -- make the tree have minimal height
SKEW         -- make the tree have maximal height

LEFT   -- move to the left child of the selected node
RIGHT  -- move to the right child of the selected node
PARENT -- move to the parent of the selected node
ROOT   -- move to the root of the tree

INSERT str -- add `str' to the tree if it is not present
MULTIPLE INSERT str
           -- add `str' to the tree (even if it is already present)
DELETE     -- delete the selected node
CLEAR TREE -- remove all nodes

AUTO DISPLAY ON
AUTO DISPLAY OFF
           -- turn on/off display of the tree before the > prompt
AUTO WRITE ON [file]
AUTO WRITE OFF
           -- turn on/off writing an image file of the tree before the > prompt
PRINT      -- print the elements of the tree, as a list
DISPLAY    -- display the structure of the tree
WRITE file -- create an image file showing the structure of the tree

Commands can be abbreviated; so "rr" is ROTATE RIGHT, etc.

Outcome

a<b<c.... etc.
a>b>aa>bb... etc.
The trees drawn in cygwin are displayed sideway, with the bottom branch being the right(larger values), and top branch being the left(smaller values).

Problem

A few student found the "PARENT" command doesn't work as expected, moving to the node's parent's parent. However Mark explained the command DOES work, just the display of the star makes it look wrong.
The shape of the tree drawn is rather confusing for a few of us, but this was solved after navigating through the tree for a while. A node adjacent to another node is less than the node in question if it is displayed above, and greater than if displayed below, contrary to intuition.

Task 2

In order to obtain a perfectly balanced tree

    a
  b
    c
d
    e
  f
    g

Insert d.
Insert b, f in any order.
Insert a, c, e, g in any order.
Also, if b is inserted, a and c will be in the right place anyway. Hence there are more ways to do it. e.g. dbacfeg

Task 3

The task: "Skew the tree, then perform a left rotation on the root. Compare the shape of the tree before and after the rotation. Confirm (using "print") the elements appear in the same order before and after the rotation."

Before rotation:

Order Before rotation (using "print"): Tree[*a*,b,c,d,e,f,g]

After rotation:

  a
b (*)
  c
    d
      e
        g

Order After rotation: Tree[a,*b*,c,d,e,f,g]

The skewed tree before and after rotation are displayed above.

The left rotation makes the select node to be the child of its right hand side child.

The order of the rotation has not changed even though the structure has changed.

Task 4

The task: "Play around using left and right rotations to reshape the tree until you are confident you understand how they work."

This was to aid the completion of the next few tasks which were done by most students.

Task 5

The task: "Starting with a right-skew tree of seven elements(as formed by the “skew” command), reshape the tree into a left-skew tree. Record the rotations and movement command you used in your lab report."

This involved repeating the commands "root" and "rotate left" repeatedly until left skew is achieved:

Task 6

The task: "Reshape a right-skew tree of seven elements into a balanced(minimal height) tree. Record the order of rotations and movement commands in your lab report."

    a
  b
    c 
d(*)
    e
  f
    g

This was achieved by first making 'd' the root by doing half of the process of achieving left skew. Once this is done, the selected node was set to the first node on the right of the root node 'd' (node e) and the Rotate Left command was used. This half of the tree then becomes balanced. After this, the selected node was set to the first node on the left of the root (node c) and a Rotate Right command was used. Thus, perfect balance was achieved.

Task 7

The task: "Starting with a balanced tree of seven elements, add two new elements each larger than the current maximal element and then re-balance the tree using a minimal number of rotations.

This simply involved selecting the node shown:

    a
  b
    c
d
    e
  f
    g (*)
      h
        i

and using the "Rotate Left" command to produce this tree:

    a
  b
    c
d
    e
  f
      g (*)
    h
      i

Another interpretation of a "balanced" tree that many students considered was a symmetrical tree like the following:

The tediousness of producing this interpretation meant that only llay008 bothered. Besides, the question asked for a balanced tree from a minimal number of steps, thus the first interpretation was the obvious solution. This solution probably arose from a misunderstanding of what was meant by balanced.

Task 8

The Task: "When an element is added or deleted, the insert function traverses a path from the root to the leaf. Is it always possible to re-balance the tree by performing rotations only on nodes along this path? Explain."

Some of the students' answers to this question:

"At this point I believe you can do so for insertion, but definitely not deletion. Due to the fact when you change something, that change will propagate up the tree. Although I could be totally wrong." gfun006

"No not really. Well lets look say we have 5 as the root and the numbers 321 and 567 on either side of it lined up one below the other...so the heigh tof the tree is 3. now say 3 is removed. the tree is not balanced anymore. going along hte smae path and rotating will not rebalnace hte tree ... hence no, it cannot always be done..." mgha023

"As far as i can tell, yes. The heights of the subtree pairs in a balanced tree can only be different by one, and the addition or subtraction of a element can only change a height by 1, so at the most you have a difference in height somewhere along the direct line to the root of 2. At worse this difference can be at the root node, which would require a rotation of it, but as the root is part if the line, this does not invalidate the theory." - bvic005

"It seems like it should be possible to balance the tree only using rotations along that path, since inserting or deleting an element can only put each subtree along that path out of balance by one node." - dols008

"Only nodes along the path of the nodes (and the children of those nodes) in question are affected by a deletion/insertion. This means only they need to be adjusted if balancing is required. "- dsan039

useful link-> answers to this question Balance Trees : http://homepages.ius.edu/JHOLLY/c343/notes/lrotate.htm