SE250:lab-7:sgha014

TASK 1

i tried inserting a whole bunch of numbers like this: i 1 2 3 4 5 then got told that u hav to insert each number seperatley

so i says to populate the tree with 7 elements:

      1
    2
  3
4 (*)
  5
    6
      7

so i think this means that the root is 4. 3, 2 and 1 is the left subtree and 5, 6 and 7 is the right subtree. then it says to navigate using left, right, root and parent. i typed HELP to get a better idea of what these commands do

> 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.

so before i tried using the LEFT command, i thought that it should move the star to 3 since thats the left child. and that is what i got :)

>LEFT
      1
    2
  3 (*)
4 
  5
    6
      7

the star is the selected node

so now when i type parent..it should go bak to the 4

>PARENT
      1
    2
  3
4 (*)
  5
    6
      7

right should go to 5

>RIGHT
      1
    2
  3
4 
  5 (*)
    6
      7

then i did another right to move to 6

>RIGHT
      1
    2
  3
4 
  5 
    6 (*)
      7

so im guessing that ROOT will take the star back to 4?

>ROOT
      1
    2
  3
4 (*)
  5
    6
      7

but if i had used PARENT it would hav moved to 5. i tried it just to double chek.. hmmm...nope...it moved bak to 4 again?? seemed that it wasnt working for anyone.....so i asked hte tutor and she said that theres probably sumthing wrong with the code and that she'll ask Mark. We asked mark and he said that it IS working...and that its just the way that the star is displayed that makes it look wrong....this makes NO sense to me...so i chose to ignore it and move on...

so my tree's a weird v shape...so i tried inserting the elements in a differnt order to get a balnced tree.

    1
  2
    3
4 (*)
    5
  6
    7

TASK 2

so i inserted a-g so that i get a perfectly balanced tree:

    A
  B
    C
D (*)
    E
  F
    G

TASK 3

i tried making a skewd tree:

1 (*)
    10
      11
  2
    3
      4
        5
          6

this makes no sense since 10 is bigger than 2 so it shouldnt be the left child of 2! i asked for help and Mark said that its coz the insert comand takes a string....so it considers 10 as being less that 2 coz 1 is less that 2 so it comes first. So Mark said that using letters for the keys instead of integers is a better idea. so heres my new skewed tree:

A (*)
  B
    C
      D
        E
          L

> print
Tree[*A*,B,C,D,E,L]

so next i did a left rotation:

> ROTATE LEFT
  A (*)
B
  C
    D
      E
        L

> print
Tree[*A*,B,C,D,E,L]

the print statement gave the same result before and after the rotation

TASK 4

so i just played around with rotations...got a bit lost halfway throuhg, but the tutor helped me and i finally get it now

a (*)
  b
    c
      d
        e

so if i rotate left it should make b teh root

> rotate left
  a (*)
b
  c
    d
      e

then i made b teh selected node

> parent
  a
b (*)
  c
    d
      e

then rotated left to make c the root

> rotate left
    a
  b (*)
c
  d
   e

so now if i rotate right..it shoud make a the node of the left sub tree (instead if b)

> rotate right
  a
    b (*)
c
  d
    e

TASK 5

this task was reeeally easy :)

starting with a right skewed tree of seven elements:

a (*)
  b
    c
      d
        e
          f
            g

commands used to make it a left skewed tree:

> rotate left
  a (*)
b
  c
    d
      e
        f
          g

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


> rotate left
    a
  b (*)
c
  d
    e
      f
        g

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

> rotate left
      a
    b
  c (*)
d
  e
    f
      g

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

> rotate left
        a
      b
    c
  d (*)
e
  f
    g

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

> rotate left
          a
        b
      c
    d
  e (*)
f
  g

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

> rotate left
            a
          b
        c
      d
    e
  f (*)
g

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

TASK 6

i just used the balance command for this task:

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

then this is when Mark came and said that i cant just use balance and that i have to do it using rotations and stuff. so here goes:

a (*)
  b
    c
      d
        e
          f
            g

> rotate left
  a (*)
b
  c
    d
      e
        f
          g

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

> rotate left
    a
  b (*)
c
  d
    e
      f
        g

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

> rotate left
      a
    b
  c (*)
d
  e
    f
      g

> rotate right
    a
  b
    c (*)
d
  e
    f
      g

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

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

> rotate left
    a
  b
    c
d
    e (*)
  f
    g