Hi!
Ich habe Probleme in einem AVL-Tree Nodes zu löschen.
Die zwei ersten Schritte müssten ja so sein, wie in einem Binärbaum, d.h.:
1.) Man findet den Knoten mit dem Wert, den man löschen will.
2.) Man löscht den Knoten auf eine Weise, die davon abhängt, ob Fall 1 (kein NF), Fall 2 (nur ein NF - einfach "umhängen) oder Fall 3 (2 NF) zutrifft.
Nun müsste man aber an dieser Stelle prüfen, ob die AVL-Eigenschaft noch gegeben ist und falls nicht, dann nnotfall rotieren.
Ich weiß nicht an welcher Stelle ich es prüfen soll.
Wenn man einen Knoten löscht, dann kann ja nun der Teilbaum auf der anderen Seite zu hoch sein (Höhen_Betrag > 1).
Um die andere Seite aber bzgl. ihrer AVL-Eigenschaft zu prüfen, bräuchte ich ja den Vorgänger des gelöschten Knotens, weil dieser ja die Wurzel von beiden Seiten (Teilbäumen) darstellt?
Jedoch denke ich nicht, dass unser Prof sich das so gedacht hat und daher ist meine Idee wohl falsch.
Ich denke ich poste mal den gesamten Code und danach nochmal nur separat die Delete-Funktion, zur besseren Übersicht.
Die AVL-Eigenschaft wird bei mir mittels den Funktionen "checkRotationLeft" oder "checkRotsationRight" überprüft.
Falls ein Teilbaum zu hoch ist, dann wird in einer dieser Funktionen auch die benötigte Rotations-Operation aufgerufen (entweder Einfach-oder Doppelrotation).
Der Code ist an meine Vorlesung und Übung angelegt und soll bzgl. der Implementation auch weitgehend so wenig, wie möglich verändert werden (gibt ja im Internet viele diverse Möglichkeiten zu finden...).
Ich will nur verstehen, wie und wo ich nach dem Löschen eines Knotens die AVL-Eigenschaft prüfen und ggf. wiederherstellen muss?
Für Hilfe bin ich wie immer dankbar
Hier dann erstmal der gesamte Code:
Nur Codesnippet von der Delete-Funktion:
edit:
Diesen Hinweis habe ich noch in meinen Vorlesungsunterlagen zum 3tem Schritt (also nachdem der Knoten gelöscht wurde) gefunden:
" Wiederherstellung der AVL Eigenschaft:
Such -/Löschpfad wird von „unten nach oben“ durchlaufen
AVL Eigenschaft prüfen und ggf. durch Rotationen wiederherstellen "
Leider bleiben meine Fragen erhalten
Ich weiß z.B. nicht wie ich den Baum von unten nach oben durchlaufen soll, wenn wir in dieser Implementierung keine Referenzen auf die parentNodes haben. Auch wüßte ich nicht wie und an welchen Stellen genau die AVL-Eigenschaft geprüft werden soll, d.h.
wohl die 'checkRotaion/Left/Right'-Funktion aufgerufen werden soll.
Ich habe Probleme in einem AVL-Tree Nodes zu löschen.
Die zwei ersten Schritte müssten ja so sein, wie in einem Binärbaum, d.h.:
1.) Man findet den Knoten mit dem Wert, den man löschen will.
2.) Man löscht den Knoten auf eine Weise, die davon abhängt, ob Fall 1 (kein NF), Fall 2 (nur ein NF - einfach "umhängen) oder Fall 3 (2 NF) zutrifft.
Nun müsste man aber an dieser Stelle prüfen, ob die AVL-Eigenschaft noch gegeben ist und falls nicht, dann nnotfall rotieren.
Ich weiß nicht an welcher Stelle ich es prüfen soll.
Wenn man einen Knoten löscht, dann kann ja nun der Teilbaum auf der anderen Seite zu hoch sein (Höhen_Betrag > 1).
Um die andere Seite aber bzgl. ihrer AVL-Eigenschaft zu prüfen, bräuchte ich ja den Vorgänger des gelöschten Knotens, weil dieser ja die Wurzel von beiden Seiten (Teilbäumen) darstellt?
Jedoch denke ich nicht, dass unser Prof sich das so gedacht hat und daher ist meine Idee wohl falsch.
Ich denke ich poste mal den gesamten Code und danach nochmal nur separat die Delete-Funktion, zur besseren Übersicht.
Die AVL-Eigenschaft wird bei mir mittels den Funktionen "checkRotationLeft" oder "checkRotsationRight" überprüft.
Falls ein Teilbaum zu hoch ist, dann wird in einer dieser Funktionen auch die benötigte Rotations-Operation aufgerufen (entweder Einfach-oder Doppelrotation).
Der Code ist an meine Vorlesung und Übung angelegt und soll bzgl. der Implementation auch weitgehend so wenig, wie möglich verändert werden (gibt ja im Internet viele diverse Möglichkeiten zu finden...).
Ich will nur verstehen, wie und wo ich nach dem Löschen eines Knotens die AVL-Eigenschaft prüfen und ggf. wiederherstellen muss?
Für Hilfe bin ich wie immer dankbar
Hier dann erstmal der gesamte Code:
Java:
public class Element {
public int height;
public int value;
// references
Element right;
Element left;
}
class AVLTree {
Element root;
public AVLTree() {
root = null;
}
public static void main(String[] args) {
AVLTree tree = new AVLTree();
int[] arr = {15, 5, 3, 20, 14, 16, 25, 24, 27, 18, 19};
for(int i = 0; i < arr.length; i++) {
tree.insert(arr[i]);
}
System.out.println("current tree:");
tree.print();
tree.delete(18);
System.out.println("tree after deleting the value '18'");
tree.print();
}
//------------------ private logic----------------------------------------------
private int max(int a, int b) {
if(a < b)
return b;
else
return a;
}
private int getHeight(Element element) {
if(element == null)
return -1;
else
return element.height;
}
private void updateHeight(Element element) {
element.height = 1 + max(getHeight(element.left), getHeight(element.right));
}
private Element rotateLeft(Element a) {
Element b = a.right; // future root
a.right = b.left; // linker Nachfolger von b, wird zum rechtem Nachfolger von a (vorherige root)
b.left = a; // a kommt links zu b nach unten
a = b; // b wird zu neuen root
updateHeight(a.left);
updateHeight(a);
return a;
}
private Element rotateRight(Element a) {
Element b = a.left;
a.left = b.right; // b.right wird zu a.left
b.right = a;
a = b;
updateHeight(a.right);
updateHeight(a);
return a;
}
private Element doubleRotationLeft(Element a) {
a = rotateRight(a.right);
a = rotateLeft(a);
return a;
}
private Element doubleRotationRight(Element a) {
a = rotateLeft(a.left);
a = rotateRight(a);
return a;
}
private Element checkRotationRight(Element element) {
if(element != null) {
if(element.left != null) {
if(getHeight(element.left) - getHeight(element.right) == 2) {
if(getHeight(element.left.right) > getHeight(element.left.left)) {
element = doubleRotationRight(element); // da innerer Teilbaum zu hcch ist
} else {
element = rotateRight(element); // äußerer Teilbaum zu hoch -> muss einfach-rotiert werden
}
} else {
updateHeight(element);
}
} else {
updateHeight(element);
}
}
return element;
}
private Element checkRotationLeft(Element element) {
if(element != null) {
if(element.right != null) {
if(getHeight(element.right) - getHeight(element.left) == 2) {
if(getHeight(element.right.left) > getHeight(element.right.right)) {
element = doubleRotationLeft(element); // da innerer Teilbaum zu hcch ist
} else {
element = rotateLeft(element); // äußerer Teilbaum zu hoch -> muss einfach-rotiert werden
}
} else {
updateHeight(element);
}
} else {
updateHeight(element);
}
}
return element;
}
private Element insert(Element element, int value) {
if(element == null) {
element = new Element();
element.height = 0;
element.value = value;
element.left = null;
element.right = null;
return element;
} else {
if(value <= element.value) {
element.left = insert(element.left, value);
element = checkRotationRight(element);
} else {
element.right = insert(element.right, value);
element = checkRotationLeft(element);
}
}
return element;
}
/**
* Step 1: find node with value to be deleted
* Step 2: delete node (3 cases and algo same as in binary linked search tree)
* step 3: verify/recreate avl-property
* -> examine from bottom to top
*
* @param element -> current one
* @param value to be deleted
* @return
*/
private Element delete(Element element, int value) {
if(element.value == value) {
// Fall 1: kein NF
if(element.left == null && element.right == null) {
element = null;
element = checkRotationRight(element);
element = checkRotationLeft(element);
return element;
}
// Fall 2: Nur genau 1 NF
if(element.left == null) {
element = element.right;
element = checkRotationRight(element);
return element;
}
if(element.right == null) {
element = element.left;
element = checkRotationLeft(element);
return element;
}
// Fall 3: 2 NF -> find direct inorder-successor-value
int smallestVal = findMinVal(element.right);
element.value = smallestVal;
// delete inOrder-Node from right sub-tree
element.right = delete(element.right, smallestVal);
element = checkRotationRight(element);
element = checkRotationLeft(element);
return element;
// search code
} else {
if(value < element.value) {
element.left = delete(element.left, value);
return element;
} else {
element.right = delete(element.right, value);
return element;
}
}
}
private int findMinVal(Element current) {
if(current.left == null) {
return current.value;
} else {
return findMinVal(current.left);
}
}
private void print(Element root) { // in order: left - rootOutput - right
if(root != null) {
System.out.print("(");
print(root.left);
System.out.print("," + root.value + ",");
print(root.right);
System.out.print(")");
} else {
System.out.print("n");
}
}
//------------------ public logic----------------------------------------------
public Element insert(int value) {
root = insert(root, value);
return root;
}
public Element delete(int value) {
root = delete(root, value);
return root;
}
public void print() {
print(root);
System.out.println();
}
}
Nur Codesnippet von der Delete-Funktion:
Java:
/**
* Step 1: find node with value to be deleted
* Step 2: delete node (3 cases and algo same as in binary linked search tree)
* step 3: verify/recreate avl-property
* -> examine from bottom to top
*
* @param element -> current one
* @param value to be deleted
* @return
*/
private Element delete(Element element, int value) {
if(element.value == value) {
// Fall 1: kein NF
if(element.left == null && element.right == null) {
element = null;
element = checkRotationRight(element);
element = checkRotationLeft(element);
return element;
}
// Fall 2: Nur genau 1 NF
if(element.left == null) {
element = element.right;
element = checkRotationRight(element);
return element;
}
if(element.right == null) {
element = element.left;
element = checkRotationLeft(element);
return element;
}
// Fall 3: 2 NF -> find direct inorder-successor-value
int smallestVal = findMinVal(element.right);
element.value = smallestVal;
// delete inOrder-Node from right sub-tree
element.right = delete(element.right, smallestVal);
element = checkRotationRight(element);
element = checkRotationLeft(element);
return element;
// search code
} else {
if(value < element.value) {
element.left = delete(element.left, value);
return element;
} else {
element.right = delete(element.right, value);
return element;
}
}
}
edit:
Diesen Hinweis habe ich noch in meinen Vorlesungsunterlagen zum 3tem Schritt (also nachdem der Knoten gelöscht wurde) gefunden:
" Wiederherstellung der AVL Eigenschaft:
Such -/Löschpfad wird von „unten nach oben“ durchlaufen
AVL Eigenschaft prüfen und ggf. durch Rotationen wiederherstellen "
Leider bleiben meine Fragen erhalten
Ich weiß z.B. nicht wie ich den Baum von unten nach oben durchlaufen soll, wenn wir in dieser Implementierung keine Referenzen auf die parentNodes haben. Auch wüßte ich nicht wie und an welchen Stellen genau die AVL-Eigenschaft geprüft werden soll, d.h.
wohl die 'checkRotaion/Left/Right'-Funktion aufgerufen werden soll.
Zuletzt bearbeitet: