Implementierung eines AVT-Baums

[Lukases2]

Hallo,

wie kann ich bei nachfolgendem Code die Wurzel des Baums festlegen? Ich bekomme immer die Fehlermeldung "Tree has no root".

import java.util.Random;

public class AvlTree<Key extends Comparable<Key>, Value> {
	// Repräsentiert einen Knoten des Baums
	private static class Node<Key extends Comparable<Key>, Value> {
		private final Key key;
		private Value value;
		
		private Node<Key, Value> parent;
		private Node<Key, Value> right;
		private Node<Key, Value> left;
		
		// Tiefe(rechter Teilbaum) - Tiefe(linker Teilbaum)
		private int balance;

		public Node(Key key) {
			this.key = key;
		}

		public void print() {
			print("");
		}
		
		private void print(String prefix) {
			System.out.println(prefix + key + " -> " + value + ", balance: " + balance);
			
			if(left == null && right == null)
				return;

			if(left != null) {
				left.print(prefix + "    ");
			}else{
				System.out.println(prefix + "    (no left child)");
			}
			if(right != null) {
				right.print(prefix + "    ");
			}else{
				System.out.println(prefix + "    (no right child)");
			}
		}
	}
	
	// Wurzel des Baums
	private Node<Key, Value> root;
	
	// Fügt ein Element in der Baum ein, bzw. ändert seinen Wert,
	// falls das Element bereits vorhanden ist.
	// Gibt true zurück, wenn ein neues Element eingefügt wurde,
	// ansonsten wird falsche zurückgegeben.
	public boolean addOrSet(Key key, Value value) {
		// Bitte implementieren Sie diese Methode!
		return true;
	}
	
	// Gibt den Wert, der zu einem bestimmten Schlüssel gehört, zurück.
	// Gibt null zurück, falls der Schlüssel nicht existiert.
	public Value get(Key key) {
		System.out.print(key.hashCode()+ " ");
		// Bitte implementieren Sie diese Methode!
		return null;
	}
	
	// Rechtsrotation (n bezeichnet das gegebene Node):
	//   w                 w
	//   |                 |
	//   u                 n
	//  / \      -->      / \
	// x   n             u   y
	//    / \           / \
	//   v   y         x   v
	// Man beachte, dass x und y unverändert gelassen werden
	private void rotateLeft(Node<Key, Value> n) {
		// Bitte implementieren Sie diese Methode!
	}

	// Rechtsrotation (n bezeichnet das gegebene Node):
	//     w             w
	//     |             |
	//     u             n
	//    / \    -->    / \
	//   n   x         y   u
	//  / \               / \
	// y   v             v   x
	// Man beachte, dass x und y unverändert gelassen werden
	private void rotateRight(Node<Key, Value> n) {
		// Bitte implementieren Sie diese Methode!
	}

	// Wird aufgerufen, um die Balance-Invariante wiederherzustellen,
	// nachdem die Tiefe von n sich (um 1) erhöht hat.
	// Vorbedingung: Der Teilbaum mit Wurzel n ist ein AVL-Baum
	//    und entweder n.balance != 0 oder n ist ein Blatt
	// Nachbedingung: Der Teilbaum mit Wurzel u = n.parent ist ein AVL-Baum
	private void fixAfterDepthIncrement(Node<Key, Value> n) {
		// Bitte implementieren Sie diese Methode!
	}

	private void checkIntegrity() {
		if(root != null)
			checkIntegrity(root);
	}

	// Überprüft, ob die Invarianten des AVL-Baums eingehalten werden
	// Gibt die Tiefe des Baums zurück
	private int checkIntegrity(Node<Key, Value> node) {
		int left_depth = 0;
		int right_depth = 0;

		if(node.left != null) {
			if(node.left.key.compareTo(node.key) > 0)
				throw new RuntimeException("Broken search tree invariant");
			left_depth = checkIntegrity(node.left);
		}
		
		if(node.right != null) {
			if(node.right.key.compareTo(node.key) < 0)
				throw new RuntimeException("Broken search tree invariant");
			right_depth = checkIntegrity(node.right);
		}

		if(node.balance != right_depth - left_depth)
			throw new RuntimeException("Broken balance invariant");
		
		return 1 + Math.max(left_depth, right_depth);
	}

	public static void main(String[] args) {
		String input = "The quick brown fox jumps over the lazy dog";

		AvlTree<Character, Integer> occurrences = new AvlTree<Character, Integer>();
		for(int i = 0; i < input.length(); i++) {
			Integer count = occurrences.get(input.charAt(i));
			
			if(count == null) {
				if(!occurrences.addOrSet(input.charAt(i), 1))
					throw new RuntimeException("addOrSet() returned false even though '"
							+ input.charAt(i) + "' is not part of the tree");
			}else{
				if(occurrences.addOrSet(input.charAt(i), count + 1))
					throw new RuntimeException("addOrSet() returned true even though '"
							+ input.charAt(i) + "' is already part of the tree");
			}
		}

		if(occurrences.root == null)
			throw new RuntimeException("Tree has no root");

		System.out.println("Tree counting the occurrences of characters in '" + input + "':");
		occurrences.root.print();
		
		occurrences.checkIntegrity();
		System.out.println("This is a valid AVL-tree!");
		
		if(occurrences.get(' ') != 8)
			throw new RuntimeException("But ' ' occurs 8 times");
		if(occurrences.get('o') != 4)
			throw new RuntimeException("But 'o' occurs 4 times!");
		if(occurrences.get('i') != 1)
			throw new RuntimeException("But 'i' occurs exactly once!");

	}
}

 

[VfL_Freak]

Moin,

habe den Code jetzt nur überfolgen ... wo genau denn die Meldung ??

Gruß Klaus

 

[InfectedBytes]

Das Problem kommt, weil du die Methoden nicht implementiert hast.
Die ganzen Methoden machen bisher rein gar nichts, daher ist logischerweise auch die Wurzel null.

	// Fügt ein Element in der Baum ein, bzw. ändert seinen Wert,
	// falls das Element bereits vorhanden ist.
	// Gibt true zurück, wenn ein neues Element eingefügt wurde,
	// ansonsten wird falsche zurückgegeben.
	public boolean addOrSet(Key key, Value value) {
		// Bitte implementieren Sie diese Methode!
		return true;
	}

Z.b. sollte die addOrSet Methode die Wurzel setzen, falls es bisher noch keine Wurzel gibt und ansonsten eben den Wert korrekt einfügen.