Vector oder Baum?

daishi

Hi, ich wollte mal wissen, ob sich der folgende Sachverhalt besser mit einem Baum oder einer Vector abhandeln läßt.

void smf(const int x1, const int y1,const int x2, const int y2, const int tiefe)
{
  bool chk;
  //Test auf irgendwas chk wird true oder false gesetzt

  if(chk)
  {
    smf(x1,y1,((x2+x1)/2),((y2+y1)/2),tiefe+1);
    smf(((x2+x1)/2),y1,x2,((y2+y1)/2),tiefe+1);
    smf(x1,((y2+y1)/2),((x2+x1)/2),y2,tiefe+1);
    smf(((x2+x1)/2),((y2+y1)/2),x2,y2,tiefe+1);
  }

  else
  {
    //speichere Werte
  }

Also ich rufe eine Fukntion rekursiv auf und will dann die Werte speichern.
Da gibt es doch einmal die Möglichkeit daß über einen Baum abzuhandeln, indem ich jedesmal einen Zeiger auf daß aktuelle Element übergebe und dann die Werte speichere. Oder ich nehme einen Vector den ich dann via Iterator linear bearbeiten kann.

Also nun die Frage, was ist die bessere Lösung und was die schnellere?

prolog

HI

Ein Baum ist in der Regel schneller.
Du hast ja selbst gesagt das du im schlimmsten fall über dem ganzen Vector iterieren musst. Bei einem Baum tust du dies nicht.
Vorausgesetzt er ist synchronisiert, bei sehr regelmäßigen Daten bzw. Schluesseln zu empfehlen.

Kurzum der Baum zeigt ein besseres Laufzeitverhalt was die Suche angeht.
Ich hoffe du meinst das überhaupt. Wenn nicht tschuldigung.

daishi

Doch, ist schon richtig.
Ich dacht nur, da ich beim Vector den Iterator mit ++ oder ähnlichem ändern kann ist die handhabung ja einfacher. Bei einem Baum brauche ich da ja 2 Pointer für Hin- und Rückweg brauche.

prolog

Hi

Ja aber du benutzt bei nem Baum immer den kürzesten weg.

daishi

Ok, hab es gerade mal probiert.
Mit dem Vector ist es ziemlich lahm, also probiere ich jetzt mal den Baum und hoffe auf mehr Geschwindigkeit.

volkard

hashtable?