Deutsch
Menü

Datenstrukturen und Algorithmen

Ein binärer Heap wird mit der Wurzel in a[0] in einem Array a[0], a[1], a[2], … gespeichert, wobei jede Ebene von oben beginnend von links nach rechts aufgefüllt wird. Welches sind die Kinder und der Elternknoten von a[4]?

  1. AKinder a[9] und a[10], Elternknoten a[1]
  2. BKinder a[8] und a[9], Elternknoten a[2]
  3. CKinder a[9] und a[10], Elternknoten a[2]
Antwort und Erläuterung anzeigen

Antwort: A. Kinder a[9] und a[10], Elternknoten a[1]

Liegt die Wurzel in a[0], sind die Kinder von a[i] die Elemente a[2i+1] und a[2i+2], und der Elternknoten ist a[(i−1) ÷ 2, abgerundet]. Für i = 4 sind die Kinder a[9] und a[10], und der Elternknoten ist a[(4−1) ÷ 2] = a[1]. Liegt die Wurzel in a[1], sind die Kinder a[2i] und a[2i+1] und der Elternknoten a[i ÷ 2]; es ist daher wichtig zu prüfen, welche Konvention gilt. Da ein Heap ein vollständiger Binärbaum ist, lässt er sich ohne Zeiger in einem Array speichern, und Eltern und Kinder werden allein durch Indexrechnung gefunden.

Dieses Thema üben Zur Themenseite

Weitere Fragen zu Datenstrukturen und Algorithmen

  1. Ein Max-Heap, in dem der Wert jedes Elternknotens mindestens so groß ist wie die Werte seiner Kinder, wird in einem Array mit der Wurzel in a[0] gespeichert. Zum Heap 50, 30, 40, 10, 20, 35 wird 45 hinzugefügt, indem es ans Ende gesetzt und dann mit seinem Elternknoten vertauscht wird, solange es größer als dieser ist. Wie sieht das resultierende Array aus?
  2. Wie sind die Werte der besuchten Knoten angeordnet, wenn ein binärer Suchbaum in In-Order (symmetrische Reihenfolge: erst der linke Teilbaum, dann der Knoten, dann der rechte Teilbaum) durchlaufen wird? Alle Werte seien verschieden.
  3. Die Werte 50, 30, 70, 20, 40, 60, 80 werden in dieser Reihenfolge in einen leeren binären Suchbaum eingefügt. In welcher Reihenfolge werden die Knoten besucht, wenn der Baum in Post-Order (erst der linke Teilbaum, dann der rechte Teilbaum, dann der Knoten) durchlaufen wird?
  4. 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?
  5. 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?