Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- public class RecursionTree{
- private RecursionNode nodo;
- private RecursionTree root;
- private RecursionTree figlioS;
- private RecursionTree figlioD;
- private countNode;
- public RecursionTree(RecursionNode n){}
- public RecursionTree(){}
- public int size(){}
- public RecursionTree getRoot(){}
- public RecursionNode getNode(){}
- //se il RecursionTree è vuoto questo metodo aggiunge la radice
- public RecursionTree addFiglio(){}
- private RecursionTree aggFiglioS(RecursionNode fs){}
- private RecursionTree aggFiglioD(RecursionNode fd){}
- private RecursionTree getFiglioS(){}
- private RecursionTree getFiglioD(){}
- private RecursionTree removeFiglioS(){}
- private RecursionTree removeFiglioD(){}
- public RecursionTree remove(){}
- private boolean isLeaf(){}
- private RecursionTree removeInternal(RecursionNode n){}
- public RecursionTree removeExternal(RecursionNode n){}
- public static RecursionTree mergeSort(int[] a){
- RecursionTree result=new RecursionTree();
- return mergesortRic(a,0,a.length-1,result);
- }
- public static RecursionTree mergeSortRic(int[] a,int i, int j, RecursionTree tree){
- if(i>=j) return tree;
- else{
- int medio=(i+j)/2;
- mergeSortRic(a,i,medio,tree.getFiglioS());
- mergeSortRic(a,medio+1,j,tree.getFiglioD());
- return tree.addFiglio(merge(a,i,medio,j,tree));
- }
- // i while hanno un costo di O(2((j-1)+1))
- //il mergeSort ha funzione T(n)=T(n/2)+T(n/2)+nc2,T(0)=c1; dunque 2T(n/2)+nc2 per il master Theorem 2==2 e quindi O(n^1*log(n)) come già sapevamo
- //poichè le operazioni sugli alberi sono fatte sequenzialmente il loro costo è O(1) per ogni inserimento di un nodo e quindi il costo totale è O(n)
- // il costo totale di mergeSort(int[] a) è dunque O(nlogn)
- public static RecursionTreee merge(int[] a,int i, int medio, int j, RecursionTree tree){
- int it1=i;
- int it2=medio+1;
- int[] aux=new int[(j-i)+1];
- int countAux=0;
- /* while(it1<=j){
- aux[countAux++]=a[i++];
- }
- iti=i;
- countAux=0;
- */
- while(it1<=medio && it2<=j){
- if(a[it1]<=a[it2]){
- aux[countAux++]=a[it1++];
- }else{
- aux[countAux++]=a[it2++]
- }
- }
- while(it1<=medio){
- aux[countAux++]=a[it1++];
- }
- while(it2<=j){
- aux[countAux++]=a[it2++];
- }
- countAux=0;
- it1=i;
- while(i<=j){
- a[it1++]=aux[countAux++];
- }
- return new RecursionTree(aux);
- }
- //costo O(n) dove n è il numero di nodi quindi size(), poichè visita tutti i nodi una sola volta
- public static void preOrder(RecursionTree t){
- if(t==null) return;
- else{
- System.out.println(t.getNode().geElement());
- preOrder(t.getFiglioS());
- preOrder(t.getFiglioD());
- }
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement