binäre suchbäume

    • denyo7788
      denyo7788
      Bronze
      Dabei seit: 06.05.2007 Beiträge: 264
      Hab hier in meinen Unterlagen den pseudocode für blattorientierten suchbaum und für knotenorientierten. ist beide male derselbe was doch eigentlich nicht sein kann oder?
      der code: Feld A[l...r] (vorsortiert)

      Baum(A,l,r) {
      if(l == r) then return v;

      v = new bin_node;
      m = (l+r)/2;
      v.key = A[m];
      v.left = Baum(A,l,m);
      v.right = Baum(A, m+1,r);
      return v;
      }
  • 4 Antworten
    • Lifeisabug
      Lifeisabug
      Bronze
      Dabei seit: 30.12.2007 Beiträge: 1.629
      Ist schon lange her bei mir mit Datenstrukturen. Das Ergebnis sieht jetzt erstmal wie ein blattorientierter Suchbaum aus. Aber ist es nicht spaeter bei der Suche nicht eine frage der Interpretation? Wenn ich meinen Baum als blattorientiert interpretiere gehe ich den Pfad ueber alle Knoten bis zu einem Blatt wo meine Information steht. Ist es ein knotenorientierter Baum, bin ich mit Suchen fertig sobald ich einen Knoten mit diesem Wert finde.
      Dein Algorithmus generiert einen Baum, den ich sowohl blattorientiert als auch knotenorientiert durchsuchen kann.
      Ist aber nur eine Vermutung.
    • denyo7788
      denyo7788
      Bronze
      Dabei seit: 06.05.2007 Beiträge: 264
      ... -----------------------15
      -------------7 ---------------------23
      -------3 ---------13 ---------20----------29
      (---|3| -|7|--|13|--|15|--|20|-|23|---|29|)

      ich dachte mir das es da nen unterschied geben muss?!? also beim obigen beispiel dachte ich baut der algorithmus aus einem feld A[3,7,13,15,20,23,29]
      alles bis auf die letzte zeile auf.. wenn ich bei diesem code von einem aufbau eines blattorientierten baumes ausgehen würde und zb nach der 7 suche würde ich sie doch nicht finden , da die Blätter 3, 13,20 und 29 wären?
    • Lifeisabug
      Lifeisabug
      Bronze
      Dabei seit: 30.12.2007 Beiträge: 1.629
      Ja der Code ist hier etwas ungenau finde ich aber du koenntest recht haben.
      Es geht ja um die Zeile
      if(l == r) then return v;

      Es ist halt aetzend den Wert einer Variablen zurueckzugeben, die noch niergends definiert wurde. v vor dem Aufruf von Baum() ist nicht sichtbar, und selbst wenn es so sein sollte, wuerde der Algorithmus bei der eingabe einer initial einelementigen Menge scheitern. Wenn du in diesem Fall v==NULL doer aehnliches interpretierst erhaelst du natuerlich einen richtigen knotenbasierten Baum. Ich bin beim lesen auch ueber die Zeile gestolpert aber habe intuitiv angenommen, dass sie return A[r] oder return A[l] meinen.
    • noelte
      noelte
      Silber
      Dabei seit: 13.05.2007 Beiträge: 2.205
      Baum(A,l,r) {
      v = new bin_node;
      if(l == r) then v.key = A[l];
      else
      {
      m = (l+r)/2;
      v.key = A[m];
      v.left = Baum(A,l,m);
      v.right = Baum(A, m+1,r);
      }
      return v;
      }