SE250:lab-7:bvic005

In lab 7, we where given an interactive program that allows you to create and manipulate binary search trees.

Task 1

In this task we just had to get used to using the program, by creating a 7 element tree, and by moving around in it. There is not much to say about this task, obviously, but here is the tree i created:

  aClownWithNoHead
    aRoomWithAMoose
      doom
muffins (*)
    spleen
  waffles
    walnuts

Task 2

In this task we had to insert a-g in an order do that the resulting tree was balanced. I used the order d-b-a-c-f-e-g. However, there are many orders that can be used, as long as certain key elements are entered before others.

> i d

> i b

> i a

> i c 

> i f 

> i e

> i g

> display
    a
  b
    c
d (*)
    e
  f
    g

Task 3

In this task we had to skew the tree(a right screw incidentally), and then perform a left rotation.

> skew

> display
a (*)
  b
    c
      d
        e
          f
            g

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

The skew command appears to insert the elements into the tree in alphabetical order, resulting in the most right skewed tree possible(all children are right children)

> rotate left                

> display
  a (*)
b
  c
    d
      e
        f
          g

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

The rotate left command has made the current node(and its left subtree presumably, if it had one),the left subtree of its right child.

As you can see, the order they elements are printed with the print command is unaffected.

Task 4

Here was just had to play around with the rotate commands until we where comfortable with what they where doing.

Task 5

In this task, we had to start with a right skewed tree, and using rotate commands, turn it into a left skewed tree. As a left rotate command just make the tree more left skewed(and the right rotate does the opposite), to make a left skewed tree out of a right skewed one, we just had to call rotate left on the first node of the table, until a left skewed table resulted.

> display
a (*)
  b
    c
      d
        e
          f
            g

> rl

> p

> rl

> p

> rl

> p

> rl

> p

> rl

> p

> rl

> p

> display
            a
          b
        c
      d
    e
  f
g (*)

Task 6

Here we had to take a right skewed tree, and make it balanced. I generic way to do this, i found(and hope is correct) is for each tree/subtree, check if it skewed. If so, perform successive rotations on the root(rotate left for right skew, right for left skew), until it is balanced. Then, do the same for its subtrees, or any others.

a (*)
  b
    c
      d
        e
          f
            g

> rl
  a (*)
b
  c
    d
      e
        f
          g

> root
  a
b (*)
  c
    d
      e
        f
          g

> rl
    a
  b (*)
c
  d
    e
      f
        g

> root
    a
  b
c (*)
  d
    e
      f
        g

> rl
      a
    b
  c (*)
d
  e
    f
      g

> rr
    a
  b
    c (*)
d
  e
    f
      g

> root
    a
  b
    c
d (*)
  e
    f
      g

> r
    a
  b
    c
d
  e (*)
    f
      g

> rl
    a
  b
    c
d
    e (*)
  f
    g

Task 7

In this task we had to add two elements to the right of a balanced tree, and then re-balance it. This time i used a different algorithm. I started from where the changes had been made where the changes had been made, and worked up. If a node was unbalanced, i balanced it with a rotation, checked if the node was now balanced, if not, rotated it again, until it was balanced, and then i moved to the parent node, and started again.

In this case, i only had to perform one rotation, rotate left on the g:

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

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

Task 8

Finally, we had to determine if i tree can always be rebalanced by only rotating elements in the direct line between an added/deleted element and the root element.

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 01:40, 14 May 2008 (NZST)