Hallo!!
Ich habe mal wieder mit der wöchentlichen Aufgabe zu kämpfen ...
Dieses Mal soll ich eine Klasse für einen AVL-Baum implementieren, bestehend aus int-Zahlen zu dem nur Elemente hinzugefügt oder gelöscht werden können.
Jeder Knoten soll die Höheninformation beinhalten. Die Gesamthöhe soll mittels der Methode hoehe() wiedergegeben werden und der 2erlogarithmus der Anzahl der Knoten mit der Methode logAnzKnoten().
Folgendermaßen sieht meine Datei bisher aus:
nun - ich denke ich liege mit meinen überlegungen ganz richtig.
deshalb komme ich auch nicht darauf, warum ich beim testen (hinzufügen, löschen) immer eine nullpointerexception habe. das einzige wo ich mir relativ sicher bin ist, dass es etwas mit der höheninformation zu tun hat (durch die zeilenangaben).
hilfe??
Ich habe mal wieder mit der wöchentlichen Aufgabe zu kämpfen ...
Dieses Mal soll ich eine Klasse für einen AVL-Baum implementieren, bestehend aus int-Zahlen zu dem nur Elemente hinzugefügt oder gelöscht werden können.
Jeder Knoten soll die Höheninformation beinhalten. Die Gesamthöhe soll mittels der Methode hoehe() wiedergegeben werden und der 2erlogarithmus der Anzahl der Knoten mit der Methode logAnzKnoten().
Folgendermaßen sieht meine Datei bisher aus:
Java:
public class MyAVLTree {
private Node root; // Wurzelknoten
public MyAVLTree() {
// Konstruktor; leerer Baum
root = null;
}
public void insert(int item) {
//fuegt item ein; unwirksam falls vorhanden
root = insert(root, item);
}
private Node insert(Node n, int i) {
// private Methode um rekursiv verwenden zu können
if (n == null) {
return new Node(new Node(), i, new Node()); // Baum leer, füge einfach hinzu
}
else if (i < n.data) { // links einfügen
n.left = insert(n.left, i);
n = updateHeight(n); // Höheninformationen updaten
if (n.left.height - n.right.height == 2) { // rechtsrotation notwendig
if (i < n.left.data) {
n = rotateRight(n);
}
else {
n.left = rotateLeft(n.left);
n = rotateRight(n);
}
return n;
}
}
else if (i > n.data) { // rechts einfügen
// analog
n.right = insert(n.right, i);
n = updateHeight(n);
if (n.right.height - n.left.height == 2) {
if (i > n.right.data) {
n = rotateLeft(n);
}
else {
n.right = rotateRight(n.right);
n = rotateLeft(n);
}
return n;
}
}
else { // item vorhanden, tue nichts
return n;
}
return n; // für den Compiler
}
private Node rotateRight (Node n) {
// Rechtsrotation
Node temp = new Node();
temp = n.left;
n.left = temp.right;
temp.right = n;
return temp;
}
private Node rotateLeft (Node n) {
// Linksrotation
Node temp = new Node();
temp = n.right;
n.right = temp.left;
temp.left = n;
return temp;
}
public void delete(int item) {
//loescht item, falls vorhanden; sonst unwirksam
if (isElem(item)) {
root = delete(root, item);
}
}
private Node delete (Node n, int i) {
// private Methode für rekursiven Aufruf, analog zu "insert"
if (isElem(i)) {
if (i < n.data) { // links löschen
n.left = delete(n.left, i);
n = updateHeight(n);
if (n.left.height - n.right.height == 2) {
if (i < n.left.data) {
n = rotateRight(n);
}
else {
n.left = rotateLeft(n.left);
n = rotateRight(n);
}
return n;
}
}
else if (i > n.data) { // rechts löschen
n.right = delete(n.right, i);
n = updateHeight(n);
if (n.right.height - n.left.height == 2) {
if (i > n.right.data) {
n = rotateLeft(n);
}
else {
n.right = rotateRight(n.right);
n = rotateLeft(n);
}
return n;
}
}
}
return null; // nur für den Compiler!!!!
}
public boolean isElem(int item) {
// liefert true, wenn item im AVL-Baum schon vorhanden ist
return isElem(root, item);
}
private boolean isElem(Node n, int i) {
// private Methode für rekursiven Aufruf
if (n == null) {
return false; // Baum leer - Element nicht vorhanden
}
else if (n.data == i) {
return true; // Element vorhanden
}
else {
return (isElem(n.left, i) || isElem(n.right, i));
}
}
public double logAnzKnoten() {
//gibt 2er-Logarithmus der Anzahl der aktuell im Baum vorhandenen Knoten
int anzKnoten = AnzKnoten(root);
// log_b(a)=ln(a)/ln(b) wobei b ... Basis
return (Math.log(anzKnoten)/Math.log(2));
}
private int AnzKnoten(Node n) {
if (n == null) {
return 0;
}
else {
return (1 + AnzKnoten(n.left) + AnzKnoten(n.right));
}
}
public int hoehe() {
//gibt aktuelle Hoehe des Baums
return root.height;
}
private Node updateHeight(Node n) {
// um die Höhe upzudaten wird der Baum neu aufgebaut, durch den Konstruktor ändert sich die Instanzvariable
n = new Node(updateHeight(n.left), n.data, updateHeight(n.right));
return n;
}
// ------------- Ausgeben des Baums zur Kontrolle
public void printTree(){ //wrapper
printTree(root, 1);
}
private void printTree(Node n, int h){ //recursion
if (n!=null){ //like inorder
printTree(n.right, h+1);
printNode(n,h);
printTree(n.left, h+1);}
}
private void printNode(Node n, int h){
//single node
for(int i=0;i<h;i++) System.out.print(" ");
System.out.println(n.data);
}
//-------------- innere Klasse für Knoten
private class Node {
int data;
Node left, right;
int height; // Höheninformation
Node() {
height = -1; // Baum leer --> Höhe = -1
}
Node(Node l, int i, Node r) {
data = i;
left = l;
right = r;
height = (1 + Math.max(left.height, right.height));
}
}
}nun - ich denke ich liege mit meinen überlegungen ganz richtig.
deshalb komme ich auch nicht darauf, warum ich beim testen (hinzufügen, löschen) immer eine nullpointerexception habe. das einzige wo ich mir relativ sicher bin ist, dass es etwas mit der höheninformation zu tun hat (durch die zeilenangaben).
hilfe??
Zuletzt bearbeitet:
