Starting from:
$30
CSE222- HOMEWORK 4 Solved
Course Assistant:
BURAK KOCA
1 INTRODUCTION
1.1 Problem Definition
The problem is to understand well consept of binary tree and , to implement general tree by using provided binary tree class ,to implement others binary searh algorithm like level order search,post order search and preorder traverse, and to implement multi dimensionle tree by using provided binary tree class and search tree interface.
1.2 System Requirements
It is needed a binary tree class for implementing general tree in part 1 and
a binary tree class , a search tree interface and a class that has a constructor , can take multiple arguments , for implementing multi dimensionel tree in part2
2 METHOD
2.1 Class Diagrams
Generic part1 class extends binary tree class ,and implements add method and some search methods(level order search and post order search) which add method can use one of them when find reference of parent node.
Generic part2 class extends binary tree , implements search tree.
MustBeComparable class is created for part2 class and extends Comparable.
2.2 Problem Solution Approach
For implementing general tree ,it is needed a binary tree class.
Generic part1 class extends binary tree class , override pre order traverse method and implement some useful methods(add,level order search) whose perform operations on the general tree.
· boolean add(E parent,E child,int option) : add child to tree and return true if parent is on the tree ,false otherwise.The option argument determine that method used level order search or pre order search when was finding the parent.
· Node<E levelOrderSearch(E item) : search item level by level with respect to general tree.if it finds item ,it returns reference of item in tree,null otherwise.
· Node<E preOrderSearch(E item) : search item according to preorder algorithm with respect to general tree.if it finds item ,it returns reference of item in tree,null otherwise.
For implementing multi dimensionel tree,it is needed a binary tree class ,a search tree interface and a MustBeComparable class.
Generic part2 class extends binary tree class and implements search tree interface for implementing multi dimensionel tree.
MustBeComparable class extends Comparable ,and has special constructor that has multiple arguments like MustBeComparable(E item1,E item2,...) In the otherwords
MustBeComparable(E... args).
Generic item in the part2 class must be MustbeComparable class or extend MustbeComparable class .
· boolean add(E item) : add item to tree and return true if item is not in tree,false otherwise. The add method use another private addhelper method for traversing tree recursively.
· E find(E item) : return reference of item in the tree if item is present in the tree ,null otherwise. The find method use another private findHelper method for traversing tree recursively.
· boolean contains(E item) : return true in the tree if item is present in the tree ,false otherwise. The contains method just use find method inside.
· E delete(E item) : delete item and return reference of item in the tree if item is present in the tree ,null otherwise. The delete method use other private deleteHelper method for traversing tree recursively and use another private helper method named findLargestNode so that structure of mds tree is not break down when item is deleted.
· boolean remove(E item) : delete item and return true in the tree if item is present in the tree ,false otherwise. The remove method just use delete method inside.
3 RESULT
3.1 Test Cases
1) PART1
Adding child that has no parent in tree is failed.(add method return type boolean)
Adding child that has parent in the tree is succesfull.
Searching item which is present in tree is succesfull in level order or post order search.(level and post order method return type reference)
Searching item which is not present in tree is failed in level order or post order search.(level and post order method )
2) PART2
Adding item that is present already in tree is failed .(add method return type boolean)
Adding item that is not present in tree is successfull.
Deleting item is present in the tree is successfull.(delete method return type a reference of deleted item)
Deleting item does not exist in the tree is failed.
Removing item is present in the tree is successfull.(remove method return type boolean)
Removing item does not exist in the tree is failed.
Finding item is present in the tree is successfull.(find method return type a reference of found item)
Finding item does not exist in the tree is failed.
Finding item is present in the tree is successfull.(contains method return type boolean)
Finding item does not exist in the tree is failed.
failed : method return false or null according to return type of method.
successfull: method return true or a reference of deleted or found items in tree according to return type of method.
3.2 Unit Tests
It is writen test classes for part1 and part2 ,and can be seen result of unit test of methods by running test classes.
3.3 Running Results
PART1 RESULTS :
add method outputs.
As seen above,add method return false if parent is not in the tree such as,add(logan,hercule,0) and seen that parent has how many childs.
If parent has no child ,it is added child to leftside of parent,if parent has child or chids it is added childs to rightside of last child.
LevelOrderSearch and postOrderSearch methods output:
As show above,when search fiona on tree by using level order search fiona compares ,in turn,jack ,ariana,rebeca in the first level and then compares with victory,adam,ella,carter, henry and finally fiona in second level.Thereby,fiona is found at second level.
PART 2 RESULTS:
add , find and contains methods outputs:
As seen above, add method adds apoint appropiate location on tree with respect to dimension value.find method return reference of given item if item is present in tree,null otherwise,and then contains method works like find methods ,but it return boolean value.
delete and remove methods outputs :
preOrderTraverse output:
3.4 Analyze time complexity of methods of part1
è Level order search:
result argument is needed for wheather value of node is printing or not when searching.
It is required to calculate time complexity of two while loop : inner while loop and outer while loop.
The best case of the this function is that item is equal to root.So ,TB(n) = Ɵ(1).
The worst case of this function is that every parent has more one than child and child is bottom of tree(the last level of tree.)
inner loop = input size m (for example parent has m child)
Tinner(n) = O(m)
Outter loop = input size n (for example queue.size() is n)
Toutter(n) = O(n)
Tworst case(n) = Toutter(n)*Tinner(n) = O(m*n) = O(n^2)
è Post order search :
The best case of this function is that every parent has just one child.So,It searches linearly on the tree.
Tbest(n) is O(n);
The worst case of this function is that every parent has one or more childs on the tree.
Assume that,number of parent in tree is n and maximum number of childs of every parent is m.
Tworst(n) = T(m)*T(n) = O(m*n)
T(n) is O(n) and T(m) is O(n)
thereby Tworst(n) is T(n)*T(m) = O(m*n) = (n^2).
è add method :
The best case of this function is that parent is root and has no child.So,
Tbest(n) is Ɵ(1)
The worst case of this function is max(Tlevel-worst case(n),Tpost-worst case(n)) + Tfind last clhild of parent(n)
Tlevel-worst case(n) = O(n^2)
Tpost-worst case(n) = O(n^2)
Tfind last clhild of parent(n) = O(n)
Tworst(n) = max(O(n^2),O(n^2)) + O(n)
max(O(n^2),O(n^2)) = O(n^2)
Tworst(n) = O(n^2) + O(n) = max(O(n^2),O(n)) = O(n^2).
BURAK KOCA
1 INTRODUCTION
1.1 Problem Definition
The problem is to understand well consept of binary tree and , to implement general tree by using provided binary tree class ,to implement others binary searh algorithm like level order search,post order search and preorder traverse, and to implement multi dimensionle tree by using provided binary tree class and search tree interface.
1.2 System Requirements
It is needed a binary tree class for implementing general tree in part 1 and
a binary tree class , a search tree interface and a class that has a constructor , can take multiple arguments , for implementing multi dimensionel tree in part2
2 METHOD
2.1 Class Diagrams
Generic part1 class extends binary tree class ,and implements add method and some search methods(level order search and post order search) which add method can use one of them when find reference of parent node.
Generic part2 class extends binary tree , implements search tree.
MustBeComparable class is created for part2 class and extends Comparable.
2.2 Problem Solution Approach
For implementing general tree ,it is needed a binary tree class.
Generic part1 class extends binary tree class , override pre order traverse method and implement some useful methods(add,level order search) whose perform operations on the general tree.
· boolean add(E parent,E child,int option) : add child to tree and return true if parent is on the tree ,false otherwise.The option argument determine that method used level order search or pre order search when was finding the parent.
· Node<E levelOrderSearch(E item) : search item level by level with respect to general tree.if it finds item ,it returns reference of item in tree,null otherwise.
· Node<E preOrderSearch(E item) : search item according to preorder algorithm with respect to general tree.if it finds item ,it returns reference of item in tree,null otherwise.
For implementing multi dimensionel tree,it is needed a binary tree class ,a search tree interface and a MustBeComparable class.
Generic part2 class extends binary tree class and implements search tree interface for implementing multi dimensionel tree.
MustBeComparable class extends Comparable ,and has special constructor that has multiple arguments like MustBeComparable(E item1,E item2,...) In the otherwords
MustBeComparable(E... args).
Generic item in the part2 class must be MustbeComparable class or extend MustbeComparable class .
· boolean add(E item) : add item to tree and return true if item is not in tree,false otherwise. The add method use another private addhelper method for traversing tree recursively.
· E find(E item) : return reference of item in the tree if item is present in the tree ,null otherwise. The find method use another private findHelper method for traversing tree recursively.
· boolean contains(E item) : return true in the tree if item is present in the tree ,false otherwise. The contains method just use find method inside.
· E delete(E item) : delete item and return reference of item in the tree if item is present in the tree ,null otherwise. The delete method use other private deleteHelper method for traversing tree recursively and use another private helper method named findLargestNode so that structure of mds tree is not break down when item is deleted.
· boolean remove(E item) : delete item and return true in the tree if item is present in the tree ,false otherwise. The remove method just use delete method inside.
3 RESULT
3.1 Test Cases
1) PART1
Adding child that has no parent in tree is failed.(add method return type boolean)
Adding child that has parent in the tree is succesfull.
Searching item which is present in tree is succesfull in level order or post order search.(level and post order method return type reference)
Searching item which is not present in tree is failed in level order or post order search.(level and post order method )
2) PART2
Adding item that is present already in tree is failed .(add method return type boolean)
Adding item that is not present in tree is successfull.
Deleting item is present in the tree is successfull.(delete method return type a reference of deleted item)
Deleting item does not exist in the tree is failed.
Removing item is present in the tree is successfull.(remove method return type boolean)
Removing item does not exist in the tree is failed.
Finding item is present in the tree is successfull.(find method return type a reference of found item)
Finding item does not exist in the tree is failed.
Finding item is present in the tree is successfull.(contains method return type boolean)
Finding item does not exist in the tree is failed.
failed : method return false or null according to return type of method.
successfull: method return true or a reference of deleted or found items in tree according to return type of method.
3.2 Unit Tests
It is writen test classes for part1 and part2 ,and can be seen result of unit test of methods by running test classes.
3.3 Running Results
PART1 RESULTS :
add method outputs.
As seen above,add method return false if parent is not in the tree such as,add(logan,hercule,0) and seen that parent has how many childs.
If parent has no child ,it is added child to leftside of parent,if parent has child or chids it is added childs to rightside of last child.
LevelOrderSearch and postOrderSearch methods output:
As show above,when search fiona on tree by using level order search fiona compares ,in turn,jack ,ariana,rebeca in the first level and then compares with victory,adam,ella,carter, henry and finally fiona in second level.Thereby,fiona is found at second level.
PART 2 RESULTS:
add , find and contains methods outputs:
As seen above, add method adds apoint appropiate location on tree with respect to dimension value.find method return reference of given item if item is present in tree,null otherwise,and then contains method works like find methods ,but it return boolean value.
delete and remove methods outputs :
preOrderTraverse output:
3.4 Analyze time complexity of methods of part1
è Level order search:
result argument is needed for wheather value of node is printing or not when searching.
It is required to calculate time complexity of two while loop : inner while loop and outer while loop.
The best case of the this function is that item is equal to root.So ,TB(n) = Ɵ(1).
The worst case of this function is that every parent has more one than child and child is bottom of tree(the last level of tree.)
inner loop = input size m (for example parent has m child)
Tinner(n) = O(m)
Outter loop = input size n (for example queue.size() is n)
Toutter(n) = O(n)
Tworst case(n) = Toutter(n)*Tinner(n) = O(m*n) = O(n^2)
è Post order search :
The best case of this function is that every parent has just one child.So,It searches linearly on the tree.
Tbest(n) is O(n);
The worst case of this function is that every parent has one or more childs on the tree.
Assume that,number of parent in tree is n and maximum number of childs of every parent is m.
Tworst(n) = T(m)*T(n) = O(m*n)
T(n) is O(n) and T(m) is O(n)
thereby Tworst(n) is T(n)*T(m) = O(m*n) = (n^2).
è add method :
The best case of this function is that parent is root and has no child.So,
Tbest(n) is Ɵ(1)
The worst case of this function is max(Tlevel-worst case(n),Tpost-worst case(n)) + Tfind last clhild of parent(n)
Tlevel-worst case(n) = O(n^2)
Tpost-worst case(n) = O(n^2)
Tfind last clhild of parent(n) = O(n)
Tworst(n) = max(O(n^2),O(n^2)) + O(n)
max(O(n^2),O(n^2)) = O(n^2)
Tworst(n) = O(n^2) + O(n) = max(O(n^2),O(n)) = O(n^2).
1 file (761.7KB)
