Greife auf kostenlose Karteikarten, Zusammenfassungen, Übungsaufgaben und Altklausuren für deinen Grundlagen der Algorithmen und Datenstrukturen Kurs an der Universität Würzburg zu.
Wie werden die Informationen bei Bäumen gespeichert?
Hierarchisch bzw mehrdimensional
Reguläre Ausdrücke in Python
import re
Wie groß ist der Aufwand bei der sequentiellen Suche im Durchschnitt bei der erfolglosen Suche?
n
Was ist ein Suchbaum?
• Jeder Baumknoten enthält Schlüssel und Datenelement
• Ordne die Knoten im Baum anhand ihrer Schlüssel an
Algorithmus
Ein Algorithmus ist eine eindeutige Beschreibung eines in mehreren Schritten
durchgeführten (Bearbeitungs-) Vorganges.
Wie groß ist der Aufwand bei der sequentiellen Suche im besten und im schlechtesten Fall?
• # 1 : bester Fall
• # n : schlechtester Fall
Voller Binärbaum:
alle Ebenen außer der letzten Ebene sind "voll besetzt"
(Ebene 𝑘 besitzt genau 2^𝑘 Knoten)
Binärbaum:
Jeder Knoten hat max. 2 Nachfolger
Nenne alle Elemente eines Baums
Knoten, innerer Knoten
Kanten
Pfad
Wurzel
Beschreibe die Preorder Traversierung
"Wurzel zuerst"
• Zuerst der Knoten selbst, dann rekursiv die Traversierung des linken
und danach des rechten Teilbaums.
Zentrale Aufgaben der Informatik
• systematische Verarbeitung von Informationen und
• Maschinen, die diese Verarbeitung automatisch leisten
Beschreibe die schrittweise Suche in Suchbäumen
• Starte mit Wurzel des Baums als aktueller Knoten
• Vergleiche mit Schlüssel des
aktuellen Knotens
• Steige rekursiv in linken oder rechten Teilbaum,
wenn Suchschlüssel kleiner oder
größer als aktueller Knotenschlüssel ist
• Wenn aktueller Knoten ein Blatt
ist, dann nicht gefunden.
Greife kostenlos auf tausende geteilte Karteikarten, Zusammenfassungen, Altklausuren und mehr zu.
Jetzt loslegen