Forum:  Algorithmen / Datenstrukturen
Thema: Pseudo-Code Algorithmus Binärer Suchbaum
Themen-Übersicht
Mitness
Junior
Dabei seit: 11.01.2019
Mitteilungen: 14
Aus:
Themenstart: 2019-01-12 17:39

Moin!

Ich brauche einen rekursiven Algorithmus im form eines Pseudo-codes, der in einem Binären Suchbaum jedem Knoten ein Label h(v) gibt, welches die Höhe des Knotens im Baum beschreibt, wenn angenommen wird, dass h(nil) = 0 global definiert ist.  


Ich habe schon dutzende male bei Google danach gesucht, aber kann nichts dazu finden mad , vielleicht könnt ihr mir ja weiterhelfen  smile !


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 5086
Aus: Milchstraße
Beitrag No.1, eingetragen 2019-01-12 18:44

Hallo Mitness,

für einen Knoten v, der kein Blatt ist, seien k1(v) und k2(v) die beiden Kindknoten.

Du kannst die Funktion rekursiv definieren:
Funktion H(v,n) (input: Knoten v und Wert n)
  setze h(v) = n
  wenn v ein Blatt ist: return
  rufe H(k1(v),n+1) und H(k2(v),n+1) auf
  return

Rufe dann H(w,0) auf, wobei w die Wurzel des binären Baums ist.


Mitness
Junior
Dabei seit: 11.01.2019
Mitteilungen: 14
Aus:
Beitrag No.2, vom Themenstarter, eingetragen 2019-01-12 18:57

2019-01-12 18:44 - StrgAltEntf in Beitrag No. 1 schreibt:
Hallo Mitness,

für einen Knoten v, der kein Blatt ist, seien k1(v) und k2(v) die beiden Kindknoten.

Du kannst die Funktion rekursiv definieren:
Funktion H(v,n) (input: Knoten v und Wert n)
  setze h(v) = n
  wenn v ein Blatt ist: return
  rufe H(k1(v),n+1) und H(k2(v),n+1) auf
  return

Rufe dann H(nil,0) auf.

Ich danke dir :)!


Mitness
Junior
Dabei seit: 11.01.2019
Mitteilungen: 14
Aus:
Beitrag No.3, vom Themenstarter, eingetragen 2019-01-12 19:26

2019-01-12 18:44 - StrgAltEntf in Beitrag No. 1 schreibt:
Hallo Mitness,

für einen Knoten v, der kein Blatt ist, seien k1(v) und k2(v) die beiden Kindknoten.

Du kannst die Funktion rekursiv definieren:
Funktion H(v,n) (input: Knoten v und Wert n)
  setze h(v) = n
  wenn v ein Blatt ist: return
  rufe H(k1(v),n+1) und H(k2(v),n+1) auf
  return

Rufe dann H(w,0) auf, wobei w die Wurzel des binären Baums ist.

Also ich verstehe was der Pseudocode macht, soweit so gut, nur ist es gefordert den Pseudocode in dieser Konvention zu schreiben:
example

kannst du mir deinen Pseudocode auf diese art einmal schreiben? Damit ich weiß wie ich sowas in Zukunft abstrahiere smile

PS: Diese Aufgabe ist lediglich eine Übungsaufgabe und wird nicht bewertet!


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 5086
Aus: Milchstraße
Beitrag No.4, eingetragen 2019-01-12 19:38

Eigentlich musst du es nur ins Englische übersetzen wink
function H(v,n)
  h[v] <- n
 
  if left[v] != NIL then
    H(left[v],n+1)
  end if
 
  if right[v] != NIL then
    H(right[v],n+1)
  end if
 
  return
end function


Mitness
Junior
Dabei seit: 11.01.2019
Mitteilungen: 14
Aus:
Beitrag No.5, vom Themenstarter, eingetragen 2019-01-12 19:45

2019-01-12 19:38 - StrgAltEntf in Beitrag No. 4 schreibt:
Eigentlich musst du es nur ins Englische übersetzen wink
function H(v,n)
  h[v] <- n
 
  if left[v] != NIL then
    H(left[v],n+1)
  end if
 
  if right[v] != NIL then
    H(right[v],n+1)
  end if
 
  return
end function

Ich danke dir vielmals biggrin
Jetzt habe ich ein Beispiel wie ich die nächsten Übungen angehe  smile



Mitness
Junior
Dabei seit: 11.01.2019
Mitteilungen: 14
Aus:
Beitrag No.6, vom Themenstarter, eingetragen 2019-01-12 20:12

2019-01-12 19:38 - StrgAltEntf in Beitrag No. 4 schreibt:
Eigentlich musst du es nur ins Englische übersetzen wink
function H(v,n)
  h[v] <- n
 
  if left[v] != NIL then
    H(left[v],n+1)
  end if
 
  if right[v] != NIL then
    H(right[v],n+1)
  end if
 
  return
end function


Weißt du denn auch, wie ich zeigen kann, dass die Lauftzeit von O(n) eingehalten wird mit diesem Pseudocode? smile


matph
Senior
Dabei seit: 20.11.2006
Mitteilungen: 5506
Aus: A
Beitrag No.7, eingetragen 2019-01-12 21:19

Hallo,

Du könntest das Akra-Bazzi-Theorem verwenden smile

--
mfg
matph


StrgAltEntf
Senior
Dabei seit: 19.01.2013
Mitteilungen: 5086
Aus: Milchstraße
Beitrag No.8, eingetragen 2019-01-12 21:21

2019-01-12 20:12 - Mitness in Beitrag No. 6 schreibt:
Weißt du denn auch, wie ich zeigen kann, dass die Lauftzeit von O(n) eingehalten wird mit diesem Pseudocode? smile

Mache dir klar, dass die Funktion H für jeden Knoten genau ein Mal aufgerufen wird. Damit bist du eigentlich fertig.

(Übrigens solltest du, wenn n die Anzahl der Knoten bezeichnet, die Variable n im Pseudocode durch k ersetzen.)

[Die Antwort wurde nach Beitrag No.6 begonnen.]




Dieses Forumbeitrag kommt von Matroids Matheplanet
https://https://matheplanet.de

Die URL für dieses Forum-Thema ist:
https://https://matheplanet.de/default3.html?topic=239735=5103
Druckdatum: 2019-08-21 09:41