SHARE
TWEET

Untitled

a guest Sep 14th, 2013 33 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class RecursionTree{
  2.  
  3.         private RecursionNode nodo;
  4.         private RecursionTree root;
  5.         private RecursionTree figlioS;
  6.         private RecursionTree figlioD;
  7.         private countNode;
  8.        
  9.         public RecursionTree(RecursionNode n){}
  10.         public RecursionTree(){}
  11.        
  12.         public int size(){}
  13.         public RecursionTree getRoot(){}
  14.         public RecursionNode getNode(){}
  15.         //se il RecursionTree è vuoto questo metodo aggiunge la radice
  16.         public RecursionTree addFiglio(){}
  17.         private RecursionTree aggFiglioS(RecursionNode fs){}
  18.         private RecursionTree aggFiglioD(RecursionNode fd){}
  19.         private RecursionTree getFiglioS(){}
  20.         private RecursionTree getFiglioD(){}
  21.         private RecursionTree removeFiglioS(){}
  22.         private RecursionTree removeFiglioD(){}
  23.         public RecursionTree remove(){}
  24.         private boolean isLeaf(){}
  25.         private RecursionTree removeInternal(RecursionNode n){}
  26.         public RecursionTree removeExternal(RecursionNode n){}
  27.        
  28.        
  29.        
  30.        
  31.        
  32.         public static RecursionTree mergeSort(int[] a){
  33.                 RecursionTree result=new RecursionTree();
  34.                 return mergesortRic(a,0,a.length-1,result);
  35.         }
  36.        
  37.        
  38.        
  39.         public static RecursionTree mergeSortRic(int[] a,int i, int j, RecursionTree tree){
  40.                 if(i>=j) return tree;
  41.                
  42.                
  43.                 else{
  44.                         int medio=(i+j)/2;
  45.                         mergeSortRic(a,i,medio,tree.getFiglioS());
  46.                         mergeSortRic(a,medio+1,j,tree.getFiglioD());
  47.                         return tree.addFiglio(merge(a,i,medio,j,tree));
  48.                 }
  49.                 // i while hanno un costo di O(2((j-1)+1))
  50.                 //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
  51.                 //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)
  52.                 // il costo totale di mergeSort(int[] a) è dunque O(nlogn)
  53.         public static RecursionTreee merge(int[] a,int i, int medio, int j, RecursionTree tree){
  54.                
  55.                 int it1=i;
  56.                 int it2=medio+1;
  57.                 int[] aux=new int[(j-i)+1];
  58.                 int countAux=0;
  59. /*              while(it1<=j){
  60.                         aux[countAux++]=a[i++];
  61.                 }
  62.                 iti=i;
  63.                 countAux=0;
  64.         */
  65.                 while(it1<=medio && it2<=j){
  66.                         if(a[it1]<=a[it2]){
  67.                                 aux[countAux++]=a[it1++];
  68.                         }else{
  69.                                 aux[countAux++]=a[it2++]
  70.                         }
  71.                        
  72.                 }
  73.                 while(it1<=medio){
  74.                         aux[countAux++]=a[it1++];
  75.                 }
  76.                 while(it2<=j){
  77.                         aux[countAux++]=a[it2++];
  78.                 }
  79.                 countAux=0;
  80.                 it1=i;
  81.                 while(i<=j){
  82.                         a[it1++]=aux[countAux++];
  83.                 }
  84.                 return new RecursionTree(aux);
  85.        
  86.         }
  87.         //costo O(n) dove n è il numero di nodi quindi size(), poichè visita tutti i nodi una sola volta
  88.         public static void preOrder(RecursionTree t){
  89.                 if(t==null) return;
  90.                 else{
  91.                         System.out.println(t.getNode().geElement());
  92.                         preOrder(t.getFiglioS());
  93.                         preOrder(t.getFiglioD());
  94.                 }
  95.        
  96.         }
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
 
Top