SE250:lab-7:mgha023
> 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.
one
> root
1 (*)
2
3
4
5
6
7
> right
1
2 (*)
3
4
5
6
7
> right
1
2
3 (*)
4
5
6
7
> parent
1 (*)
2
3
4
5
6
7
> root
1 (*)
2
3
4
5
6
7
> left
1
2
3
4
5
6
7
> right
Current node is not set
1
2
3
4
5
6
7
> root
1 (*)
2
3
4
5
6
7
> right
1
2 (*)
3
4
5
6
7
> right
1
2
3 (*)
4
5
6
7
> right
1
2
3
4 (*)
5
6
7
> right
1
2
3
4
5 (*)
6
7
> right
1
2
3
4
5
6 (*)
7
> right
1
2
3
4
5
6
7 (*)
> right
1
2
3
4
5
6
7
> left Current node is not set
1
2
3
4
5
6
7
> root
1 (*)
2
3
4
5
6
7
> right
1
2 (*)
3
4
5
6
7
> right
1
2
3 (*)
4
5
6
7
> right
1
2
3
4 (*)
5
6
7
> parent
1
2 (*)
3
4
5
6
7
> parent
1 (*)
2
3
4
5
6
7
> parent
1 (*)
2
3
4
5
6
7
two
> multiple insert 4 6 5 7 2 1 3
4 6 5 7 2 1 3 (*) //did not work
> clear tree
> insert 4
4 (*)
> insert 6
4 (*) 6
> insert 5
4 (*)
5
6
> insert 7
4 (*)
5
6
7
> insert 2
2
4 (*)
5
6
7
> insert 1
1
2
4 (*)
5
6
7
> insert 3
1
2
3
4 (*)
5
6
7
The way its facing is pretty odd but if thats the way it has ot be then thats the way it has to be:P
Ok, inserting in the order 4213657 also gives the same tree
H:\ec250\lab7>gcc *.c -o lab-7 && .\lab-7.exe
> insert 4
4 (*)
> insert 2
2 4 (*)
> insert 1
1 2 4 (*)
> insert 3
1
2
3
4 (*)
> insert 6
1
2
3
4 (*)
6
> insert 5
1
2
3
4 (*)
5
6
> insert 7
1
2
3
4 (*)
5
6
7
- The other combinations that works are :4261357, 4627153, 4623157, 4621735...yeah, there seem to be more...so ill stop here.
three
1
2
3
4 (*)
5
6
7
Tree[1,2,3,*4*,5,6,7]
> skew
1 (*)
2
3
4
5
6
7
Tree[*1*,2,3,4,5,6,7]
> rl //rotate left
1 (*)
2
3
4
5
6
7
>root
1
2(*)
3
4
5
6
7
Tree[1,*2*,3,4,5,6,7]
four
3
4
5
6
7
> print Tree[*1*,2,3,4,5,6,7]
> balance
1 2 3
4 (*)
5 6 7
> skew
1 (*)
2
3
4
5
6
7
> right
1
2 (*)
3
4
5
6
7
> root
1 (*)
2
3
4
5
6
7
> right
1
2 (*)
3
4
5
6
7
> right
1
2
3 (*)
4
5
6
7
> right
1
2
3
4 (*)
5
6
7
> root
1 (*)
2
3
4
5
6
7
> rr //doesnt do anything becasue it has nothign on its left to skew add above and make a root of.
1 (*)
2
3
4
5
6
7
> root 1 (*)
2
3
4
5
6
7
> print Tree[*1*,2,3,4,5,6,7]
> skew
1 (*)
2
3
4
5
6
7
> right
1
2 (*)
3
4
5
6
7
> right
1
2
3 (*)
4
5
6
7
> right
1
2
3
4 (*)
5
6
7
> r
1
2
3
4
5 (*)
6
7
> rl
1
2
3
4
5 (*)
6
7
> root
1 (*)
2
3
4
5
6
7
> right
1
2 (*)
3
4
5
6
7
> rl
1
2 (*)
3
4
5
6
7
> r
1
2
3
4
5
6
7
> balance
1 2 3 4 (*) 5 6 7
> s
1 (*)
2
3
4
5
6
7
> r
1
2 (*)
3
4
5
6
7
> r
1
2
3 (*)
4
5
6
7
> r
1
2
3
4 (*)
5
6
7
> rr
1
2
3
4 (*)
5
6
7
> rr
1
2
3
4 (*)
5
6
7
> l
1
2
3
4
5
6
7
> root
1 (*)
2
3
4
5
6
7
> r
1
2 (*)
3
4
5
6
7
> rr
1
2 (*)
3
4
5
6
7
five
1 (*)
2
3
4
5
6
7
8
> rl
1 (*)
2
3
4
5
6
7
8
> root
1
2 (*)
3
4
5
6
7
8
> rl
1
2 (*)
3
4
5
6
7
8
> root
1
2
3 (*)
4
5
6
7
8
> rl
1
2
3 (*)
4
5
6
7
8
> root
1
2
3
4 (*)
5
6
7
8
> rl
1
2
3
4 (*)
5
6
7
8
> root
1
2
3
4
5 (*)
6
7
8
> rl
1
2
3
4
5 (*)
6
7
8
> root
1
2
3
4
5
6 (*)
7
8
> rl
1
2
3
4
5
6 (*)
7
8
> root
1
2
3
4
5
6
7 (*)
8
> rl
1
2
3
4
5
6
7 (*)
8
> root
1
2
3
4
5
6
7
8 (*)
> rl
1
2
3
4
5
6
7
8 (*)
>Woohoo, a left skewed tree:D
SIX!
> skew
1 (*)
2
3
4
5
6
7
> rl
1 (*)
2
3
4
5
6
7
> root
1
2 (*)
3
4
5
6
7
> rl
1
2 (*)
3
4
5
6
7
> root
1
2
3 (*)
4
5
6
7
> rl
1
2
3 (*)
4
5
6
7
> root
1
2
3
4 (*)
5
6
7
> l
1
2
3 (*)
4
5
6
7
> rr
1
2
3 (*)
4
5
6
7
> root
1
2
3
4 (*)
5
6
7
> r
1
2
3
4
5 (*)
6
7
> rl
1
2
3
4
5 (*)
6
7
SEVEN
1 2 3 4 (*) 5 6 7
> i 8
1
2
3
4 (*)
5
6
7
8
> i 9
1
2
3
4 (*)
5
6
7
8
9
> r
1
2
3
4
5
6 (*)
7
8
9
> r
1
2
3
4
5
6
7 (*)
8
9
> rl
1
2
3
4
5
6
7 (*)
8
9
EIGHT
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...
excuse the typos!!!