Binäre Suchbäume in der Informatik einfach erklärt

Binaerbaum Beispiel

Binärbaum In diesem Beitrag wird es um binäre Suchbäume gehen. Aus diesem Grund erkläre ich zunächst, was denn überhaupt ein Binärbaum ist. Ein Binärbaum ist ein Spezialfall von einer Baum-Datenstruktur. Jeder Knoten hat maximal Zwei Kind-Knoten, einen Linken und einen Rechten. Ein vollständiger Binärbaum hat 2^d Blätter und 2^(d + 1) – 1 Knoten. Binäre Suchbäume …

Weiterlesen …

Bedeutung von ‘? super T’, ‘? extends T’ und ‘?’ in Java für generische Typen

HTML Code

Was bedeuten die Ausdrücke ? super T, ? extends T und ? in Java? Bei dem hier genannten ‚?’ handelt es sich um sogenannte Wildcards. Diese Wildcard repräsentieren einen unbekannten Typ, daher kann man es auch mit einem Platzhalter vergleichen. Im Gegensatz zu einem Typ-Parameter wie ‚<T>’, können Wildcards nicht als Platzhalter für Typ-Parameter weiter genutzt werden. Wildcards …

Weiterlesen …

Durchsuchen von Array-Listen – Lineare und Binäre Suche

Durchsuchen von Array Listen Binäre Suche

Einleitung In diesem Beitrag beschäftigen wir uns mit dem Durchsuchen von Array-Listen und gehen näher auf das lineare und binäre Suchverfahren ein.  Durchsuchen von Array-Listen mit der linearen Suche Eine lineare Suche durchläuft alle Elemente der Reihe nach und prüft, ob das gegeben Suchkriterium für das aktuelle Element gilt. Üblicherweise wird am Ende der List – falls kein …

Weiterlesen …

Sequentielle Datentypen

Sequentielle Datentypen Queue

In diesen Beitrag behandeln wir die Themen rund um sequentiellen Datentypen. Sequentielle Datentypen ist eine Datenstruktur, die als Folge von gleichartigen Elementen definiert ist. Die Elemente liegen in einer geordneten Reihenfolge vor, sodass man mit einem Index auf sie zugreifen kann.  Array Ein Array ist wie folgt definiert: Es besitzt eine feste Anzahl von Elementen. …

Weiterlesen …

Algorithmische Techniken – Brute Force, Greedy, Teile und Herrsche, Dynamische Programmierung und Backtracking

Algorithmische Techniken Fibonacci Folge mit dynamischer Programmierung

In diesem Beitrag beschäftigen wir uns mit den gängigen algorithmischen Techniken wie Brute Force, Gier, Teile und Herrsche und der dynamischen Programmierung.  Brute Force Bei dieser Technik wird völlig willkürlich versucht eine Lösung für ein bestehendes Problem zu finden. Der Algorithmus endet erst, wenn die Menge der möglichen Lösungen für das Problem erschöpft ist (keine Lösung …

Weiterlesen …

Lazy Evaluation und Streams

Lazy Evalutian Unter „lazy evaluation” (=faule/bequeme Auswertung) versteht man das aneinanderreihen von Befehlen, ohne sie jedoch sofort auszuwerten, sondern erst auszuführen, wenn deren Ergebnis benötigt wird. Dies hat den Vorteil, dass unnötiges Kopieren von Daten vermieden wird. Theoretisch erlaubt diese Methode den Umgang mit unendlichen Datenmengen, denn es entsteht ein sogenannter Datenstrom. (siehe Streams) Streams …

Weiterlesen …

Die Liste als abstrakter Datentyp

Die Liste als abstrakter Datentyp Verkettete Liste

In diesem Beitrag werden wir uns mit dem Typ “Liste” als abstrakten Datentyp beschäftigen. Eine Liste ist abstrakter Datentyp, der eine veränderliche Anzahl von Elementen in fester Ordnung über einen ganzzahligen Index speichern kann.  Ein abstrakter Datentyp wird über sein Verhalten definiert. Das heißt, man beschreibt die möglichen Operationen und Effekte (siehe Interface), die man mit einem Objekt von diesen …

Weiterlesen …

Korrektheitsbeweise von Klassen und Schleifen

Korrektheitsbeweise Um einen Programm-Code auf Korrektheit zu prüfen, gibt es die sogenannten Korrektheitsbeweise. Diese unterteilen sich in Schleifeninvarianten und in Klasseninvarianten. Schleifeninvariante Eine Schleifeninvarianten beweist man häufig mit der Methode der vollständigen Induktion. Dabei schaut man sich ein bekanntes Element, beispielsweise mit dem Index 0 oder 1 an und prüft, ob-die Aussage gilt. Danach prüft …

Weiterlesen …

Der Graph als abstrakter Datentyp

Der Graph als abstrakter Datentyp Verketteter Graph

In diesem Beitrag werden wir uns mit Graphen als abstrakte Datentypen beschäftigen. Ein Graph besteht aus einer Menge von Knoten und Kanten. Ein Knoten speichert die eigentlichen Daten und wird auch „Ecke” oder „Vertex” genannt. Eine Kante verbindet Knoten mit einander und wird auch „Edge” genannt. Ein einfacher Graph könnte beispielsweise folgendermaßen definiert sein. Dieser Graph …

Weiterlesen …

Baum Datenstruktur als abstrakter Datentyp mit Beispielen

Baum als Datentyp vollständiger Baum

Baum Datenstruktur In diesem Beitrag wird die Baum Datenstruktur als abstrakter Datentyp betrachtet. Ein Baum enthält üblicherweise drei Arten von Knoten: Wurzelknoten: Ist der Ursprung und besitzt keine Elternknoten, dafür aber beliebig viele Kindknoten. Innerer Knoten: Befinden sich im Inneren eines Baums und hab einen Eltern Knoten und mindestens einen Kindknoten. Äußere Knoten: nennt man auch Blattknoten. Sie haben keine …

Weiterlesen …