Advertisement
Guest User

Untitled

a guest
Sep 14th, 2013
70
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
Java 2.65 KB | None | 0 0
  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.     }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement