Suchen-Sortieren-Bäume an der Universität Potsdam | Karteikarten & Zusammenfassungen

Lernmaterialien für Suchen-Sortieren-Bäume an der Universität Potsdam

Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Suchen-Sortieren-Bäume Kurs an der Universität Potsdam zu.

TESTE DEIN WISSEN
Lineare Suche,
Binäre Suche
Lösung anzeigen
TESTE DEIN WISSEN
Linear:
- Durchsuchen von vorne bis hinten.
-> O(n)

Binär:
- Liste muss sortiert sein.
- Untersuchung es Elem. in der Mitte.

-> falls kein Treffer erzielt wurde,
     teile die Liste in Hälften.
-> suche in der passenden
     Teilliste weiter.

- Suche verläuft Rekursiv.
-> O(log n)
Lösung ausblenden
TESTE DEIN WISSEN
Selection Sort
Lösung anzeigen
TESTE DEIN WISSEN
In-place Algorithmus.
Jeden Index mit allen davon
rechteren Indizes vergleichen.

-> Austausch, falls ausgewählter
     Index größer als der rechtere.

-> O(n^2)
Lösung ausblenden
TESTE DEIN WISSEN
In-place Algorithmus
Lösung anzeigen
TESTE DEIN WISSEN
Prozedur, die Eingabedaten
im Speicher direkt manipuliert.

-> kein weiterer Speicherbedarf.
-> Nebeneffekt an Eingabedaten.
Lösung ausblenden
TESTE DEIN WISSEN
Insertion Sort
als In-place
Lösung anzeigen
TESTE DEIN WISSEN
Rückwärtiges Durchsuchen
nach korrekter Position für
den ausgewählten Index.

-> vom 2. Element bis zum letzten
     jeweils mit dessen linkeren
     Elementen vergleichen und
     bei Bedarf tauschen.

-> O(n^2)
Lösung ausblenden
TESTE DEIN WISSEN
Mergesort
Lösung anzeigen
TESTE DEIN WISSEN
kein In-place Algorithmus.
Zusammenmischen von sortierten
Teilfolgen, die davor in Sequenzen
der Länge 1 unterteilt wurden.

- rekursives Vorgehen
- Zusammensetzen: lineare Laufzeit.
-> günstig für viele, verschiedene Folgen.

-> O(n log n)
Lösung ausblenden
TESTE DEIN WISSEN
Quicksort
Lösung anzeigen
TESTE DEIN WISSEN
In-place Algorithmus.
Sortieren durch Teilen der Liste
in zwei Teilfolgen unter Auswahl
des Pivot-Elements, mit welchem
alle anderen Elemente verglichen
werden.

Teilfolge1:  alle Elem.   <   Pivot.
Teilfolge2: alle Elem.  >=  Pivot.

- in der teile(L, low, high) Funktion
   mit zwei Laufvariablen von
   Außen nach Innen arbeiten und 
   Seitentausch, wenn Element
   auf falscher Seite ist. Sonst weiter
   nach innen vordringen.

- Lösung: die sortierten Teilfolgen
   konkatenieren.
- kein Mischen erforderlich.
-> in der Praxis oft überlegen.
Lösung ausblenden
TESTE DEIN WISSEN
Entscheidungsbaum
Lösung anzeigen
TESTE DEIN WISSEN
Die Anzahl der Entscheidungen
ist für jede Anordnung der Abstand
des Blattes von der Wurzel.

-> maximal: die Tiefe des Baums.
(Anzahl der Ebenen -1)

- für Folge mit Länge n:
   n! verschiedene Anordnungen.

für Sortieralgorithmen:
-> Binärer Baum.
Lösung ausblenden
TESTE DEIN WISSEN
Baum
Lösung anzeigen
TESTE DEIN WISSEN
Zusammenhängender,
kreisfreier Graph.

Wurzel:
Knoten ohne Vater.
Blatt:
Knoten ohne Kinder.
Innerer Knoten:
Knoten zwischen Wurzel u. Blättern.
Lösung ausblenden
TESTE DEIN WISSEN
Tiefe
Lösung anzeigen
TESTE DEIN WISSEN
Tiefe eines Knotens:
Abstand von der Wurzel
zum Knoten.

Tiefe des Baums:
Größter Abstand von der
Wurzel zu einem Blatt.

:= max{tiefe(v,T): v ist Blatt}
Lösung ausblenden
TESTE DEIN WISSEN
Wald
Lösung anzeigen
TESTE DEIN WISSEN
Kreisfreier Graph.

-> hat Bäume als
     Zusammenhangs-
     komponenten.
Lösung ausblenden
TESTE DEIN WISSEN
Aufspannender Baum
Lösung anzeigen
TESTE DEIN WISSEN
Teilgraph eines Graphen G,
der ein Baum ist und alle
Knoten von G enthält.
Lösung ausblenden
TESTE DEIN WISSEN
Binärer Baum
Lösung anzeigen
TESTE DEIN WISSEN
Ausgangsgrad jedes Knotens
des Baums ist höchstens 2.

- Tiefe d:
-> max. 2^d Blätter.
-> max. 2^(d+1) -1 Knoten.
Lösung ausblenden
  • 62687 Karteikarten
  • 1634 Studierende
  • 116 Lernmaterialien

Beispielhafte Karteikarten für deinen Suchen-Sortieren-Bäume Kurs an der Universität Potsdam - von Kommilitonen auf StudySmarter erstellt!

Q:
Lineare Suche,
Binäre Suche
A:
Linear:
- Durchsuchen von vorne bis hinten.
-> O(n)

Binär:
- Liste muss sortiert sein.
- Untersuchung es Elem. in der Mitte.

-> falls kein Treffer erzielt wurde,
     teile die Liste in Hälften.
-> suche in der passenden
     Teilliste weiter.

- Suche verläuft Rekursiv.
-> O(log n)
Q:
Selection Sort
A:
In-place Algorithmus.
Jeden Index mit allen davon
rechteren Indizes vergleichen.

-> Austausch, falls ausgewählter
     Index größer als der rechtere.

-> O(n^2)
Q:
In-place Algorithmus
A:
Prozedur, die Eingabedaten
im Speicher direkt manipuliert.

-> kein weiterer Speicherbedarf.
-> Nebeneffekt an Eingabedaten.
Q:
Insertion Sort
als In-place
A:
Rückwärtiges Durchsuchen
nach korrekter Position für
den ausgewählten Index.

-> vom 2. Element bis zum letzten
     jeweils mit dessen linkeren
     Elementen vergleichen und
     bei Bedarf tauschen.

-> O(n^2)
Q:
Mergesort
A:
kein In-place Algorithmus.
Zusammenmischen von sortierten
Teilfolgen, die davor in Sequenzen
der Länge 1 unterteilt wurden.

- rekursives Vorgehen
- Zusammensetzen: lineare Laufzeit.
-> günstig für viele, verschiedene Folgen.

-> O(n log n)
Mehr Karteikarten anzeigen
Q:
Quicksort
A:
In-place Algorithmus.
Sortieren durch Teilen der Liste
in zwei Teilfolgen unter Auswahl
des Pivot-Elements, mit welchem
alle anderen Elemente verglichen
werden.

Teilfolge1:  alle Elem.   <   Pivot.
Teilfolge2: alle Elem.  >=  Pivot.

- in der teile(L, low, high) Funktion
   mit zwei Laufvariablen von
   Außen nach Innen arbeiten und 
   Seitentausch, wenn Element
   auf falscher Seite ist. Sonst weiter
   nach innen vordringen.

- Lösung: die sortierten Teilfolgen
   konkatenieren.
- kein Mischen erforderlich.
-> in der Praxis oft überlegen.
Q:
Entscheidungsbaum
A:
Die Anzahl der Entscheidungen
ist für jede Anordnung der Abstand
des Blattes von der Wurzel.

-> maximal: die Tiefe des Baums.
(Anzahl der Ebenen -1)

- für Folge mit Länge n:
   n! verschiedene Anordnungen.

für Sortieralgorithmen:
-> Binärer Baum.
Q:
Baum
A:
Zusammenhängender,
kreisfreier Graph.

Wurzel:
Knoten ohne Vater.
Blatt:
Knoten ohne Kinder.
Innerer Knoten:
Knoten zwischen Wurzel u. Blättern.
Q:
Tiefe
A:
Tiefe eines Knotens:
Abstand von der Wurzel
zum Knoten.

Tiefe des Baums:
Größter Abstand von der
Wurzel zu einem Blatt.

:= max{tiefe(v,T): v ist Blatt}
Q:
Wald
A:
Kreisfreier Graph.

-> hat Bäume als
     Zusammenhangs-
     komponenten.
Q:
Aufspannender Baum
A:
Teilgraph eines Graphen G,
der ein Baum ist und alle
Knoten von G enthält.
Q:
Binärer Baum
A:
Ausgangsgrad jedes Knotens
des Baums ist höchstens 2.

- Tiefe d:
-> max. 2^d Blätter.
-> max. 2^(d+1) -1 Knoten.
Suchen-Sortieren-Bäume

Erstelle und finde Lernmaterialien auf StudySmarter.

Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.

Jetzt loslegen

Das sind die beliebtesten StudySmarter Kurse für deinen Studiengang Suchen-Sortieren-Bäume an der Universität Potsdam

Für deinen Studiengang Suchen-Sortieren-Bäume an der Universität Potsdam gibt es bereits viele Kurse, die von deinen Kommilitonen auf StudySmarter erstellt wurden. Karteikarten, Zusammenfassungen, Altklausuren, Übungsaufgaben und mehr warten auf dich!

Das sind die beliebtesten Suchen-Sortieren-Bäume Kurse im gesamten StudySmarter Universum

Tierseuchen

Universität Giessen

Zum Kurs
Spez. Tierseuchen

Universität Giessen

Zum Kurs
Tierseuchen

Tierärztliche Hochschule Hannover

Zum Kurs
Tierseuchen

Tierärztliche Hochschule Hannover

Zum Kurs
Tierseuchen

Tierärztliche Hochschule Hannover

Zum Kurs

Die all-in-one Lernapp für Studierende

Greife auf Millionen geteilter Lernmaterialien der StudySmarter Community zu
Kostenlos anmelden Suchen-Sortieren-Bäume
Erstelle Karteikarten und Zusammenfassungen mit den StudySmarter Tools
Kostenlos loslegen Suchen-Sortieren-Bäume