Hallo ich soll das Einfügen eines neuen Knotens in einen AVL-Baum implementieren. mittels Inorder-Traversierung. Ich glaub ich habs nicht ganz so richtig gemacht und mit Postorder verwechselt oder?
Für Korrekturen bzw. Verbesserungsvorschläge wäre ich sehr dankbar!
lg
Code:
import java.lang.Math;
public class AVLTree<T extends Comparable<T>> {
protected AVLNode<T> root;
protected int size;
//Initialisiert den AVL-Baum
public AVLTree() {
size = 0;
}
// Gibt die Anzahl der im AVL-Baum gespeicherten Elemente zurück
public int size() {
return size;
}
// Liefert die Höhe des Baumes
public int height() {
return height(root);
}
// Hilfsfunktion welche die Höhe des Teilbaumes n liefert
private int height(AVLNode<T> n) {
if (n == null)
return -1;
return n.height;
}
// gibt true zurück, wenn val1 kleiner oder gleich val2 ist
private boolean isSmaller(T val1, T val2) {
return val1.compareTo(val2) <= 0;
}
// gibt true zurück, wenn node1 kleiner oder gleich node2 ist
private boolean isSmaller(AVLNode<T> node1, AVLNode<T> node2) {
return isSmaller(node1.data, node2.data);
}
private void updateHeights(AVLNode<T> n) {
boolean changed = true;
n = n.parent;
while (n != null && changed) {
int max = 1 + Math.max(height(n.left), height(n.right));
if (max != n.height) {
n.height = max;
} else
changed = false;
n = n.parent;
}
}
private void insert(T elem, AVLNode<T> startnode) {
if (isSmaller(elem, startnode.data)) {
if (startnode.left == null) {
startnode.left = new AVLNode<T>(elem);
startnode.left.parent = startnode;
size++;
updateHeights(startnode.left);
restructure(startnode.left);
} else
insert(elem, startnode.left);
} else {
if (startnode.right == null) {
startnode.right = new AVLNode<T>(elem);
startnode.right.parent = startnode;
size++;
updateHeights(startnode.right);
restructure(startnode.right);
} else
insert(elem, startnode.right);
}
}
// Fügt neues Element elem in den AVL-Baum ein (null-Elemente sind nicht erlaubt)
public void insert(T elem) throws IllegalArgumentException {
if (elem == null) {
throw new IllegalArgumentException("The argument can't be null!");
}
if (root == null) {
root = new AVLNode<T>(elem);
root.parent = null;
size = 1;
root.height = 0;
} else {
insert(elem, root);
}
}
// Gibt das erste Element mit Schlüssel key zurück, null falls es nicht gefunden wurde
public T find(T key) throws IllegalArgumentException {
if (key == null) {
throw new IllegalArgumentException("The argument can't be null!");
}
AVLNode<T> node = findNode(key, root);
if (node != null)
return node.data;
return null;
}
// findet den Schlüssel im Baum, beginnend vom Startknoten
// und gibt Knoten der Schlüssel enthält zurück, falls gefunden,
//sonst null
private AVLNode<T> findNode(T key, AVLNode<T> startnode) {
if (startnode == null)
return null;
if (startnode.data.equals(key))
return startnode;
if (isSmaller(key, startnode.data))
return findNode(key, startnode.left);
return findNode(key, startnode.right);
}
// Liefert eine Array-Repräsentation der gespeicherten Elemente (Inorder-Traversierung)
public Object[] toArray() {
Object[] array = new Object[size];
if (root != null)
inorder(root, 0, array);
return array;
}
private int inorder(AVLNode<T> n, int index, Object[] array) {
if (n.left != null) {
index = inorder(n.left, index, array);
}
if (n.right != null) {
index = inorder(n.right, index, array);
}
array[index] = n.data;
return ++index;
}
// gibt true zurück wenn Unterbaum (verwurzelt in n) is AVLTree
private boolean isAVLTree(AVLNode<T> n) {
return (Math.abs(height(n.left) - height(n.right)) < 2);
}
// Parent für Node n einrichten
private void setParent(AVLNode<T> n, AVLNode<T> parent) {
if (n != null)
n.parent = parent;
}
private void restructure(AVLNode<T> n) {
AVLNode[] arr = new AVLNode[7];
AVLNode<T> x = null, y = null, z = n;
while (z != root && isAVLTree(z)) {
x = y;
y = z;
z = z.parent;
}
if (isAVLTree(z))
return;
AVLNode<T> prev = z.parent;
AVLNode<T> a, b, c;
a = null;
b = null;
c = null;
boolean xy = isSmaller(x, y);
boolean yz = isSmaller(y, z);
// find a,b,c
if (yz) {
a = xy ? x : y;
b = xy ? y : x;
c = z;
} else {
a = z;
b = xy ? x : y;
c = xy ? y : x;
}
arr[0] = a.left;
arr[1] = a;
arr[2] = xy && yz ? a.right : b.left;
arr[3] = b;
arr[4] = !yz && !xy ? c.left : b.right;
arr[5] = c;
arr[6] = c.right;
// Unterbaum in z ersetzen mit neuem Unterbaum in b
if (prev == null) {
root = b;
} else {
if (isSmaller(prev, b))
prev.right = b;
else
prev.left = b;
}
b.parent = prev;
b.left = arr[1];
setParent(b.left, b);
b.right = arr[5];
setParent(b.right, b);
b.left.left = arr[0];
setParent(b.left.left, b.left);
b.left.right = arr[2];
setParent(b.left.right, b.left);
b.right.left = arr[4];
setParent(b.right.left, b.right);
b.right.right = arr[6];
setParent(b.right.right, b.right);
// neue Höhen für nodes a,b,c festlegen
a.height = 1 + Math.max(height(a.left), height(a.right));
c.height = 1 + Math.max(height(c.left), height(c.right));
b.height = 1 + Math.max(height(b.left), height(b.right));
updateHeights(b);
}
private void print(AVLNode<T> n) {
System.out.print(n.data.toString() + " ");
}
private void inorder(AVLNode<T> n) {
if (n.left != null) {
inorder(n.left);
}
if (n.right != null) {
inorder(n.right);
}
print(n);
}
public void print() {
if (root == null)
return;
inorder(root);
}
}Für Korrekturen bzw. Verbesserungsvorschläge wäre ich sehr dankbar!
lg
...!! 