Problemer en øvelsesoppgave i algoritmer

8. oktober 2008

Hei, lenge siden sist..

Jeg sitter her å fomler noe insane for å prøve å lage et generelt binært tre ved hjelp av kun et array.

Måten jeg har tenkt å gjøre det på er da og la Arr[0] = root, Arr[1] = leftnode, Arr[2] = rightnode osv.. eksempel på hva jeg mener:

A
/ \
B C
/ /\
2 5 3

Blir da [A,B,C,2,null,5,3] ..

Problemet er at jeg ikke klarer å tenke meg til hvordan jeg skal få dette implementert i insertRight, insertLeft metodene mine..

public void insertLeft(int node, E element)
{
if(node == 0)
{
S[1] = element;
_size++;
}
else
{
S[node+2] = element;
_size++;
}
}
public void insertRight(int node, E element)
{
if(node == 0)
{
S[2] = element;
_size++;
}
else
{
S[node+3] = element;
_size++;
}

Det som følgelig skjer her er at de overskriver hverandre innimellom, og det må ikke skje.. noen som kan hjelpe meg litt på vei her eller? Ville satt pris på det..

Btw, glemte å nevne at det skal ikke brukes faste plasser til nodene i tabellen, slik at 2i+1 for venstrenoder, og 2i+2 for høyrenoder er utelukket som alternativ

RipZ

<3 VIP <3

1.092 7

8. oktober 2008

Ser egentlig ikke helt hva du prøver å gjøre basert på koden din. Ser ut til at du prøver å lagre nodene i et nytt array, noe som er bortkastet. Det er i hovedsak to måter å gjøre denne oppgaven på. Den ene er å lage en metode som henter barnenoder basert på index-key. Den andre er å traversere listen og opprette nye objekter hvor du spesifiserer barnenoder for hvert objekt. Siden du allerede har en liste, er vel den første måten å løse oppgaven på den beste, og den er tillegg in place, altså den tar ikke opp mer ram enn det som kreves for å representere listen.

Metode for å hente barnenode-index basert på foreldrenode-index når root = index 0

Kode

public int[] getChildNodesIndex(int parentNode) {

    
    int parent = parentNode + 1;    
    int height = floor(log2(parent));
    
    int leftSpan = parent - 2^height;
    
    int leftChild = 2^(height + 1) - 2 * leftSpan;
    
    
    return new int[] {leftChild, ++leftChild};   
    


}

Koden er delvis pseudokode. Oversett til ditt språk. Metoden vil returnere to indexer som representerer indexen til barnenodene i listen basert på foreldrenoden sin index.

masac

Trådstarter

117 13

8. oktober 2008

Jeg vet det er bortkastet å lagre nodene i et Array - det er derfor det kalles en øvelsesoppgave hehe. Poenget er at jeg skal lage et binært tree som en klasse, ved bruk av et array. Hvordan jeg bygger treet ut ifra listen er ikke problemet, problemet er å vedlikeholder strukturen i listen, slik at en kan bygge treestrukturen ut i fra listen når bruker er ferdig med å legge inn noder..

men skal ta en titt på hva du har gjort her - skjønte ikke helt hva som skjer

masac

Trådstarter

117 13

9. oktober 2008

Det ser ikke ut som om koden din fungerte.. om jeg ikke har oversatt den feil:

public int calcPosition(int ParentIndex,int pos){
int height = (int)Math.floor(Math.log(ParentIndex)/Math.log(2.0));
int leftSpan = ParentIndex - 2^height;
int leftChild = 2^(height + 1) - 2 * leftSpan;

if(pos == 0){
return leftChild;
}
else{
return ++leftChild;
}
}

For min returnerer bare tulleposisjoner, slik som negative verdier og like verdier ..

Sist endret av masac; 9. oktober 2008 kl. 18:40.

RipZ

<3 VIP <3

1.092 7

12. oktober 2008

Husk at i de fleste språk så blir "^" regnet som exclusive or. Bruker du java erstatter du f.eks 2^x med Math.pow(2, x). Ser også at det skal være + og ikke - i "int leftChild = 2^(height + 1) - 2 * leftSpan;".

Denne koden fungerer i Java:

Kode

public class Test {

	
	public static int[] getChildNodesIndex(int parentNode) { 

	     
	    int parent = parentNode + 1; 
	    int height = (int)Math.floor( Math.log(parent) / Math.log(2));
	    
	    int leftSpan = parent - (int)Math.pow(2, height); 
	     
	    int leftChild = (int)Math.pow(2, height + 1) + 2 * leftSpan; 
	     
	     
	    return new int[] {--leftChild, ++leftChild};    
	     


	} 
	
	public static void main(String[] args) {
		
		String[] array = {"Rot", "RotLeft", "RotRight", "RotLeftLeft", "RotLeftRight", "RotRightLeft", "RotRightRight", "RootLeftLeftLeft", "RootLeftLeftRight", "RootRightLeftLeft", "RootRightLeftRight"};
		int[] childs = getChildNodesIndex(0);
		
		for(int i : childs) {
			
			if(i >= array.length)
				break;
			
			System.out.println(array[i]);			
		}
		
	}
	
	
}

▼ ... over en uke senere ... ▼

dword

598 4

20. oktober 2008

Sitat av masac

Vis hele sitatet...

Basicly det du beskriver her er en binær heap. Wikipedia har fine artikler om dette. http://en.wikipedia.org/wiki/Binary_heap

Du har en array a = [....], rot=a[0] med barn a[1] og a[2] osv.
Funksjonen for å få tak i indeksen til barna og forelder er da, venstre-barn = 2*i+1, høyre-barn= 2*i+2 og forelder = floor((i-1)/2), der i er indeksen til noden.

▼ ... over en uke senere ... ▼

masac

Trådstarter

117 13

31. oktober 2008

Hei, jeg har løst dette problemet. Beklager fraværet med svar.

dosky

1.470 242

31. oktober 2008

Hva med å legge ut løsningen?

Inb4 logotytme.

masac

Trådstarter

117 13

31. oktober 2008

Det kan jeg vett:

Kode

    private int calculator(int ParentIndex,int pos){            
        int cPosition=0;           
        for(int i=0; i<= ParentIndex;i++){       
            if(T[i] != null){            
                cPosition+=1;      
            }    
        }            
        if(pos == 0){ //VenstreInsert        
            cPosition*=2;      
        }       
        if(pos == 1){ //HøyreInsert        
            cPosition= cPosition*2+1;      
        } 
        if(!beenProcessed){
            checkArraySize(cPosition); //Sjekker om det er plass til barnet i arrayet.
            needSpace(cPosition); // Sjekker om noden trenger å få tildelt plass til sine barn mellom andre noder.
        }        
        return cPosition;         
    }

ParentIndex er indexen til den aktuelle noden som skal få barn, Pos er en bit som indikerer ved 0 og 1 om det er venstre eller høyre insert som kaller metoden.

checkArraySize utvider selve arrayet nodene ligger i, slik at det er plass til de nye nodene.
needSpace kontrollerer om det er behov for å flytte eksiterende noder i tabellen mot høyre, slik at det blir plass til de nye barna.

Dette er selvfølgelig bare en liten del av BinaryTree klassen, men det er strengt tatt det som er svaret på det jeg spurte etter.