vor- und nachteile von array, v-listen und bäumen

hi,
habe bereits ein paar sachen gefunden, wäre aber nett wenn ihr mir noch was helfen könntet.. das können ja nicht alle sein

arrays
+ schneller und direkter "random-access" durch bspw. einen index
- großer speicher aufwand
- aufwendiges (durch-)suchen
- aufwendiges sortieren

verkettete listen
+ es werden soviele knoten erzeugt wie benötigt, nicht benötigte knoten können wieder gelöscht werden
+ sehr effizientes einfügen und herausnehmen
+ knoten lassen sich mit wenig aufwand mitten in der liste einschieben oder herausnehmen
- langsamer "random-access"
- um auf irgendein element zugreifen zu können, muss dieses erst in der ganzen liste vom kopf an gesucht werden
- aufwendige verwaltung
- jeder knoten muss einzeln allokiert und freigegeben werden. dafür ist eine sorgfältige und komplizierte implementierung notwendig

binäre bäume
+ ein element kann schnell gefunden werden
+ elemente sind in einer reihenfolge abgelegt
- können nicht mit doppelten/gleichen/gleichwertigen elementen umgehen
(- haben keinen sinn? j/k)

danke für ergänzungen!
gruß, the fin

rüdiger

- großer speicher aufwand

Nein, du hast ja nicht mehr aufwand bei der Speicherung eines Arrays mit 255 Variablen oder 255 Variablen, da bei Arrays ja kein Mehraufwand wie zusätzliche Zeiger benutzt werden

- aufwendiges (durch-)suchen
- aufwendiges sortieren

das stimmt doch auch nicht ganz, da du schnell auf die Elemente zugreifen kannst, dass kopieren kann natürlich je nachdem recht aufwendig sein

- langsamer "random-access"
- um auf irgendein element zugreifen zu können, muss dieses erst in der ganzen liste vom kopf an gesucht werden

ist das nicht ungefähr das gleiche

- großer speicher aufwand
damit dachte ich an den index des arrays. ist zwar nur eine speicheradresse, aber mehr als bei einer liste, oder?

- langsamer "random-access"
- um auf irgendein element zugreifen zu können, muss dieses erst in der ganzen liste vom kopf an gesucht werden
hmm, hast recht - ist das gleiche..

verdammt, haben array denn garkeine nachteile? und wie seiht es mit den anderen aus?

danke bis dann,
fin

rüdiger

damit dachte ich an den index des arrays. ist zwar nur eine speicheradresse, aber mehr als bei einer liste, oder?

Nein! Denk mal nach, du benutzt als Iterator ein Pointer und kannst dadurch durch das ganze Array iterieren, Listen brauchen ja schon für jeden Eintrag mindestens einen Pointer für das nächste Element, also steigt die Anzahl linear mit der Anzahl der Elemente, bei Arrays hat man den Overhead nicht

verdammt, haben array denn garkeine nachteile?

Eine Menge und du hast sie ja schon aufgezählt

-langsam beim löschen/einfügen
-effiziente Implementierungen halten oft mehr Speicher besetzt, als benutzt (ist 1. günstiger ein großen Block Speicher zu reservieren 2. ist es sehr teuer das Array umkopieren zu müssen, weil jemand auf die Idee kam ein Element zu löschen)

[ Dieser Beitrag wurde am 11.03.2003 um 17:22 Uhr von kingruedi editiert. ]

Headhunter

+ ein element kann schnell gefunden werden

ok
Wenn du eine Millionen Elemente hast, benötigst du im worst case ca. 20 "verästelungen" (bei einem perfekt sortiertem Tree)

+ elemente sind in einer reihenfolge abgelegt

ok
Wobei das einfügen allerdings auch recht langsam ist

- haben keinen sinn?

*erstensteinwerf*
Doch hamse ! Bäume werden in beinahe jedem 3D Game zur Einteilung des 3D Raumes verwendet -innerhalb von wenigen Schritten kann man *Riesenteile* des Levels wegwerfen (d.h. nicht zeichnen). Informier dich mal nach BSP Trees...
John Carmack war übrigens der Erste der gemerkt hat, wie toll es ist Bäume in Games zu verwenden -und er hat Doom erschaffen. Ohne Bäume wäre das *absolut* undenkbar

Daniel E.

Ein Array kann ich auch als binären Baum betrachten.

Übrigens: Datenstrukturen ohne spezifischen Verwendungszweck in zu vergleichen ist irgendwie nicht so sinnvoll ...

@headhunter
is ja interessant.. dh. die aktuelle position in einem 3d-level eines ego-shooters ist im grunde genommen die position im binären baum und gibt an welche äste momentan nicht verfügbar sein müssen etc. ?

@daniel
dann sag das mal unserem lehrer.. zu dem thema schreiben wir eine arbeit und eine der fragen wird garantiert sein: "nenne n vor- und nachteile von arrays/verketteten listen/binären bäumen"

danke für eure hilfe!
fin

kartoffelsack

können nicht mit doppelten/gleichen/gleichwertigen elementen umgehen

doch, können sie schon. Nur ist deren Reihenfolge nicht bestimmt.