AVL-Baum - Testen ob einer vorliegt

A

andi677

Gast
Hey an alle!

Ich muss eine Methode implementieren, die bei gegebenen Binärbaum testet, ob ein AVL Baum vorliegt.
Die Musterlösung gibt folgendes vor:

Java:
public boolean isAVLTree(Knoten root){
if (root==null){
return true;
}
return
Math.abs(getHeight(root.left) - getHeight(root.right)) <= 1 &&
isAVLTree(root.left) &&
isAVLTree(root.right);

// getHeight() gibt einem die Höhe zurück

Nun die Frage: Irgendwie kann ich nicht nachvollziehen, warum man zusätzlich zum rekursiven Aufruf noch die Differenz beim return ermittelt... Wär echt nett, wenn mir jemand das return hier entschlüsseln könnte.

Vielen vielen Dank! :)
 
G

Gast2

Gast
Soweit ich mich erinnern kann muss ein AVL Baum ausbalanciert sein. Das heißt der linke Teilbaum muss genauso hoch wie der rechte Teilbaum sein. Allerdings würde ich dann prüfen ob die Differenz 0 ist, und nicht <= 1. Aber vielleicht passt meine Definition auch nicht ganz.
 
H

hüteüberhüte

Gast
Ja, das ist richtig. Für jeden Knoten muss geprüft werden, ob die Höhe der Teilbäume sich max. um 1 unterscheidet. :)arrow: Dann ist er balanciert.) Also ist rekursives Vorgehen angebracht
 
H

hüteüberhüte

Gast
Aber nicht nur AVL-Bäume sind höhenbalanciert, außerdem lassen sich Bäume auch noch in Arrays/Feldern speichern, je nach dem, wie die Darstellung ist.

War vorhin am überlegen, ob es nicht reichen würde, nur die unteren beiden Ebenen des Baums zu betrachten. Aber vermutlich nicht. :D welche Aufgaben habt ihr noch so in diesen Zusammenhang?
 
Ähnliche Java Themen
  Titel Forum Antworten Datum
D 2,3-Baum rekursiv erstellen Allgemeine Java-Themen 20
D Datentypen 2-3 Baum erstellen mit geordnetem int-array Allgemeine Java-Themen 0
L Dependency Injection für Baum-Einträge Allgemeine Java-Themen 9
M Iterator für trinären Baum Allgemeine Java-Themen 0
N Rekursiv Höhe Baum Allgemeine Java-Themen 3
D Baum zeichnen hilfe Allgemeine Java-Themen 4
D if - else Baum vereinfachen Allgemeine Java-Themen 4
M Eclipse Stackoverflow beim Einlesen von großen Bilder in kd Baum Allgemeine Java-Themen 15
G Datentypen TreeMap nach Color sortiert (kd-Baum) Allgemeine Java-Themen 8
M Baum nach Stack plus Objektkonvertierung Allgemeine Java-Themen 5
S Baum mit vordefinierten Werten befüllen Allgemeine Java-Themen 2
D Datenstruktur für Hierarchie/Baum mit Tiefe 3 Allgemeine Java-Themen 8
D Rot-Schwart-Baum denkfehler im code? Allgemeine Java-Themen 6
M Baum Allgemeine Java-Themen 3
K Dependency Baum erstellen/analysieren Allgemeine Java-Themen 2
J Baum mit Adjazensmatrix Allgemeine Java-Themen 8
MQue Tidy HTML baum durchlaufen Allgemeine Java-Themen 5
C Breitendurchlauf Baum. Vorgehen unklar. Allgemeine Java-Themen 23
C Fehler im Quellcode. Suche in einem Baum Allgemeine Java-Themen 3
R Daten aus Baum entsprechend in jTree einfuegen Allgemeine Java-Themen 2
C Daten möglichst schnell einem Baum zuordnen Allgemeine Java-Themen 2
S Datenstruktur für einen Baum Allgemeine Java-Themen 5
N Baum aus Datei laden. Allgemeine Java-Themen 3
L Erste Schritte TDD testen einer Methode mit injezierten Services? Allgemeine Java-Themen 12
ZeusSeinGrossopa Testen ob neuer Tag beginnt Allgemeine Java-Themen 37
S Habt ihr eine Idee wie man Serializierung testen kann..? Allgemeine Java-Themen 6
B Eclipse WebSocket programmiert, kann es leider nicht testen. Allgemeine Java-Themen 15
H OOP Testen einer Exception mit JUnit Allgemeine Java-Themen 8
perlenfischer1984 TestNG - Enum testen Allgemeine Java-Themen 1
perlenfischer1984 Testng : Funktion mit mehreren Parametern testen Allgemeine Java-Themen 5
J Best Practice Testen von protected Methoden Allgemeine Java-Themen 7
F Testen von Methoden Allgemeine Java-Themen 3
B JUnit Zufalls Operation testen Allgemeine Java-Themen 1
P Testen von UIs Allgemeine Java-Themen 2
T MEthodenauruf testen, wenn instanz erst erzeugt wird Allgemeine Java-Themen 0
M Testen von verschiedenen Produktversionen Allgemeine Java-Themen 3
T EventBus testen Allgemeine Java-Themen 1
L JUnit - automatisiertes vs. manuelles Testen? Allgemeine Java-Themen 3
R Java Performance testen Allgemeine Java-Themen 18
B Mails testen Allgemeine Java-Themen 7
aze JUnit: Testen ob bestimmte Exception nicht auftritt Allgemeine Java-Themen 18
J JUnit - werfen von Exceptions testen Allgemeine Java-Themen 17
X Testen ob ein array leer ist Allgemeine Java-Themen 6
M Server-Responds testen, Code-Redundanz Allgemeine Java-Themen 3
fastjack Unit-Testen mit Mocks Allgemeine Java-Themen 6
B FileWriter / FileReader testen / Mock-Objekt für Unit Tests? Allgemeine Java-Themen 6
H Thread Safety und Deadlocks testen Allgemeine Java-Themen 6
D Muss eine JNI Biblio testen (MAC OS X) Allgemeine Java-Themen 4
T Object auf Double, Int, String testen Allgemeine Java-Themen 5
aokai Testen von Klassen die abhängig von Stdlibs URL sind Allgemeine Java-Themen 3
S Testen einer Anwendung durch klicken von Koordinaten Allgemeine Java-Themen 7
R Testen von Applets - versch. Browser und Java Versionen? Allgemeine Java-Themen 4
V Quellcode auf "Güte" testen? Allgemeine Java-Themen 5
G JAR-DAtei testen Allgemeine Java-Themen 15
J Klasse auf Konstruktor oder Methode testen? Allgemeine Java-Themen 3
A Junit Exceptions testen Allgemeine Java-Themen 3
Z Testen welches BS benutzt wird Allgemeine Java-Themen 3
G Testen von RMI,TCP/IP, Servlets etc. Allgemeine Java-Themen 2
M Welches Linux zum Java testen? Allgemeine Java-Themen 5
P Testen mit JUnit Allgemeine Java-Themen 8
L Java6 update N bekommt neues Browser-Plugin, bitte testen. Allgemeine Java-Themen 7
G testen mit JUnit? Allgemeine Java-Themen 3
K Testen ob Methode existiert? Allgemeine Java-Themen 2
N Cashbook Management Testen Allgemeine Java-Themen 7
A testen ob Primzahl dauert bei größeren zahlen extrem lange Allgemeine Java-Themen 8
M String testen? Allgemeine Java-Themen 2
M String testen? Allgemeine Java-Themen 6
N auf typ testen? Allgemeine Java-Themen 3
M Programmierstill: Bitte testen anhand HTML-Tool Allgemeine Java-Themen 18
K Testen einer Klasse mit File Objekt als Parameter Allgemeine Java-Themen 6
M Bitte Testen: Mein Multi-File Editor Allgemeine Java-Themen 30
T GUI Testen Allgemeine Java-Themen 4
T GUI Testen Allgemeine Java-Themen 5
G Programm zum Testen der Striktheit von Java Allgemeine Java-Themen 9
H Laufwerk testen? Allgemeine Java-Themen 12
F Hilfe: Adjazenzmatrix mittels JUnit testen. Allgemeine Java-Themen 2
M Jemannd mit 1.4/1.3/1.2 zum Testen gesucht. Allgemeine Java-Themen 15
flashfactor Testen ob ein R/3 erreichbar bzw. noch am leben ist. Allgemeine Java-Themen 2
T Datum testen und Einsetzten Allgemeine Java-Themen 5
M Regular Expression - verschiedene Ausdrücke testen (grep | ) Allgemeine Java-Themen 5
P Dateinamen mit regulärem Ausdruck testen Allgemeine Java-Themen 9
P Dateinamen testen? Schreibrechte auf Verzeichnis testen? Allgemeine Java-Themen 8
O Leerzeichen und Umlaute im Pfad einer Java Applikation machen Probleme Allgemeine Java-Themen 13
H Mehrere PNG-Files in einer Datei Allgemeine Java-Themen 9
G Java Editor Löschen doppelter Zahlen einer Liste Allgemeine Java-Themen 2
J JSON Daten von einer Webseite erhalten Allgemeine Java-Themen 2
L RegEx für Teile einer Berechnung Allgemeine Java-Themen 14
J Zerlegen einer Zahl Allgemeine Java-Themen 6
Zrebna Wie kann man endgültig aus einer Rekursion ausbrechen? Allgemeine Java-Themen 14
M Person in einer Arraylist hinzugügen mit Prüfung ? Allgemeine Java-Themen 6
Meeresgott Effizientester Weg um nach der Value einer verschachtelten Map aufzulösen Allgemeine Java-Themen 5
H Mehrere Datentypen in einer Arraylist speichern Allgemeine Java-Themen 9
M Prüfziffer einer EAN Nummer berechnen Allgemeine Java-Themen 4
M Erstellungsdatum einer Datei Allgemeine Java-Themen 10
Drachenbauer Wie kann ich einer existierenden Enum von außerhalb veränderte Werte zuweisen? Allgemeine Java-Themen 5
S HTML den ich von einer URL hole nicht identisch mit dem HTML im Browser Allgemeine Java-Themen 1
S Rückgabe einer HttpURLConnection für eine Seite einlesen bei der man eingeloggt ist..? Allgemeine Java-Themen 5
O Java-Applikation tut in Netbeans, als JAR nicht, wegen Pfadangaben einer benötigten Datei Allgemeine Java-Themen 8
M Hilfe bei einer Java Programmieraufgabe! Ab morgen Montag um 08:00 Uhr Allgemeine Java-Themen 5
J Algorithmen Analyse einer Schleife Allgemeine Java-Themen 6

Ähnliche Java Themen

Anzeige

Neue Themen


Oben