Mark: 21 revision(s)

2008-11-03T05:20:18Z

21 revision(s)

New page

> 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

> print
Tree[1,2,3,*4*,5,6,7]

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

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

> print
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!!!

SE250:lab-7:mgha023 - Revision history

Mark: 21 revision(s)