• API
• FAQ
• Tools
• Archive
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
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());
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.

Top