7 Aufwände von Operationen in Listen, Warteschlangen und Bäumen

7 Aufwände von Operationen in Listen, Warteschlangen und Bäumen

Welche Aufwände O(n) haben die folgenden Operationen bei nicht optimierten Implementierungen?

  • Einfügen eines Elements am Kopf einer Liste
  • Suchen eines Elements in einer Liste
  • Finden eines Elements in einem balancierten Baum
  • Finden eines Elements in einem Feld(Array) bei bekanntem Index
  • Finden eines Elements in einem Feld(Array) wenn der Zugriffsindex nicht bekannt ist

Die Antwort finden Sie hinter der nächsten Frage (URL rechts unten klicken).

Niveau 2
Schwierigkeitsgrad mittel
Zeit 5 Minuten

Antwort zu Frage 6: Binär- und Bruderbäume

  • Jeder innere Knoten hat einen oder zwei Söhne
  • Jeder unäre Knoten hat einen binären Bruderknoten
  • Alle Söhne haben die gleiche Tiefe
javafrage Tue, 03/18/2014 - 08:36

Anonymous (not verified)

Sat, 05/20/2017 - 13:08

Vielen Dank für die Javafragen!
Sollte der letzte Stichpunkt der Antwort zu Frage 6 und 8 nicht heißen:
- Alle Blattknoten haben die gleiche Tiefe
Bei Fragen 8 und 9 ist mir außerdem aufgefallen, dass die Kommentarfunktion deaktiviert ist.

habe die Kommentarfunktion wieder eingeschaltet. Das gab es mal böse Robots...
Zu den Söhnen. Das passt schon. Jeder Vater hat Söhne mit der gleichen Tiefe. Es können nicht alle Blattknoten im Baum die gleiche Höhe haben. Ein Vater ist immer um eins höher als sein Sohn.