Deutsch
Menü

Datenstrukturen und Algorithmen

Die Werte 1, 2, 3, …, 1000 werden in dieser Reihenfolge in einen leeren binären Suchbaum eingefügt (ohne Rebalancierung). Mit wie vielen Knoten wird bei der Suche nach 1000, beginnend an der Wurzel, verglichen, bis der Wert gefunden ist?

  1. A10
  2. B500
  3. C1000
Antwort und Erläuterung anzeigen

Antwort: C. 1000

Werden die Werte aufsteigend eingefügt, wird jeder neue Wert zum rechten Kind des bisherigen Maximums, und der Baum wird zu einer einzigen Kette, die nur nach rechts wächst (Höhe 999). 1000 liegt ganz unten und wird daher mit allen 1000 Knoten 1, 2, …, 1000 verglichen; das ist O(n), genau wie das Durchlaufen einer verketteten Liste von vorn. Ein ausgeglichener Baum hätte nur etwa log₂ 1000 ≈ 10 Ebenen; ein selbstbalancierender binärer Suchbaum wie ein AVL-Baum oder ein Rot-Schwarz-Baum, der sich bei jedem Einfügen und Löschen umformt, hält den schlechtesten Fall daher bei O(log n).

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. Was ist der Hauptgrund dafür, dass für Indizes in Datenbanken und Dateisystemen B-Bäume (einschließlich B+-Bäumen) statt binärer Suchbäume weit verbreitet sind?
  2. Wie lässt sich ein dünn besetzter Graph, also einer mit wenigen Kanten im Verhältnis zur Zahl der Knoten, etwa ein Straßennetz mit rund 1 Million Knoten und 3 Millionen Kanten, geeignet im Speicher ablegen?
  3. In einem Graphen mit ungewichteten Kanten soll die kleinste Zahl von Kanten vom Startknoten zu jedem anderen Knoten bestimmt werden. Welche Kombination aus Suchverfahren und Datenstruktur ist geeignet?
  4. In einem ungerichteten Graphen sind die Nachbarn der Knoten A: B, C / B: A, D, E / C: A, F / D: B / E: B, F / F: C, E. Eine rekursive Tiefensuche beginnt bei Knoten A. Die Nachbarn werden in der angegebenen Reihenfolge geprüft, und sobald ein unbesuchter Knoten gefunden wird, geht die Suche zu ihm weiter. In welcher Reihenfolge werden die Knoten besucht?
  5. In einem ungerichteten Graphen haben die Kanten die Gewichte (Entfernungen) S−A: 4, S−B: 1, A−B: 2, A−C: 1, B−C: 5, C−T: 3 und A−T: 6. Welcher kürzeste Weg von S nach T und welche Länge ergeben sich mit dem Dijkstra-Algorithmus?