/ Forside / Teknologi / Udvikling / Java / Nyhedsindlæg
Login
Glemt dit kodeord?
Brugernavn

Kodeord


Reklame
Top 10 brugere
Java
#NavnPoint
molokyle 3688
Klaudi 855
strarup 740
Forvirret 660
gøgeungen 500
Teil 373
Stouenberg 360
vnc 360
pmbruun 341
10  mccracken 320
newbie: Balancering af binært-træ
Fra : Unen


Dato : 26-05-01 14:07

Hej!

Jeg har oprettet en træstruktur. Problemmet er at det først oprettede
element er roden, hvilket kan resulterer i at, der er mange venstre-sønner
og kun få højre-sønner eller omvendt. Spørgsmålet er så hvorledes der er
muligt at få balance i træ-strukturen, så der er lige mange sønner til hver
side?

Jeg har hørt, der skulle være en API, der skulle kunne klare det meste.




 
 
Thomas Jespersen (26-05-2001)
Kommentar
Fra : Thomas Jespersen


Dato : 26-05-01 15:17

"Unen" <**REMOVE**duper@post.tele.dk**REMOVE**> writes:

> Jeg har oprettet en træstruktur. Problemmet er at det først oprettede
> element er roden, hvilket kan resulterer i at, der er mange venstre-sønner
> og kun få højre-sønner eller omvendt. Spørgsmålet er så hvorledes der er
> muligt at få balance i træ-strukturen, så der er lige mange sønner til hver
> side?

Du kan f.eks. bruge Rød-Sorte træer eller AVL-træer:
http://swww.ee.uwa.edu.au/~plsd210/ds/red_black.html

> Jeg har hørt, der skulle være en API, der skulle kunne klare det meste.

Ja, java.util.TreeMap er en implementation af Rød-Sorte træer.

Ulrik Magnusson (26-05-2001)
Kommentar
Fra : Ulrik Magnusson


Dato : 26-05-01 15:26

Unen wrote:

> Hej!
>
> Jeg har oprettet en træstruktur. Problemmet er at det først oprettede
> element er roden, hvilket kan resulterer i at, der er mange venstre-sønner
> og kun få højre-sønner eller omvendt. Spørgsmålet er så hvorledes der er
> muligt at få balance i træ-strukturen, så der er lige mange sønner til hver
> side?

Du kan lave et preorder gennemløb hvor du gemmer elementerne i en liste.
Denne liste gennemløber du så hvor du starter med det midterste element som
sættes til rod og den venstre halvdel indsættes i venstre undertræ til denne og
den
højre i højre - nogenlunde således:

preorderBalancing( preorderArray, start, end )
{
half = (end-start) / 2;
node = preorderArray[half];
node.left = preorderBalancing( preorderArray, start, half-1 );
node.right = preorderBalancing( preorderArray, half+1, end );
return node;
}

root = preorderBalancing( preorderArray, 0, preorderArray.length );

Ellers kan du kigge på rød-sorte træer og rotationer.

> Jeg har hørt, der skulle være en API, der skulle kunne klare det meste.

Prøv java.util.TreeMap i JDK 1.2 og over

Ulrik Magnusson

--
"What a surprise! A look of terminal shock in your eyes.
Now things are really what they seem."
Pink Floyd - "Sheep", Animals 1977
Visit my home page: http://www.geocities.com/ulrikm



Ulrik Magnusson (26-05-2001)
Kommentar
Fra : Ulrik Magnusson


Dato : 26-05-01 16:17

Ulrik Magnusson wrote:

> Unen wrote:
>
> > Hej!
> >
> > Jeg har oprettet en træstruktur. Problemmet er at det først oprettede
> > element er roden, hvilket kan resulterer i at, der er mange venstre-sønner
> > og kun få højre-sønner eller omvendt. Spørgsmålet er så hvorledes der er
> > muligt at få balance i træ-strukturen, så der er lige mange sønner til hver
> > side?
>
> Du kan lave et preorder gennemløb hvor du gemmer elementerne i en liste.
> Denne liste gennemløber du så hvor du starter med det midterste element som
> sættes til rod og den venstre halvdel indsættes i venstre undertræ til denne og
> den
> højre i højre - nogenlunde således:

ahem! Det skulle vist være en inorder liste. Sorry

Ulrik Magnusson

--
"What a surprise! A look of terminal shock in your eyes.
Now things are really what they seem."
Pink Floyd - "Sheep", Animals 1977
Visit my home page: http://www.geocities.com/ulrikm



Unen (27-05-2001)
Kommentar
Fra : Unen


Dato : 27-05-01 11:39

Takker mange gange. Nu har jeg noget at arbejde ud fra :0)

"Unen" <**REMOVE**duper@post.tele.dk**REMOVE**> wrote in message
news:9eo9h4$6ik$1@news.inet.tele.dk...
> Hej!
>
> Jeg har oprettet en træstruktur. Problemmet er at det først oprettede
> element er roden, hvilket kan resulterer i at, der er mange venstre-sønner
> og kun få højre-sønner eller omvendt. Spørgsmålet er så hvorledes der er
> muligt at få balance i træ-strukturen, så der er lige mange sønner til
hver
> side?
>
> Jeg har hørt, der skulle være en API, der skulle kunne klare det meste.
>
>
>



Søg
Reklame
Statistik
Spørgsmål : 177552
Tips : 31968
Nyheder : 719565
Indlæg : 6408847
Brugere : 218887

Månedens bedste
Årets bedste
Sidste års bedste