# AVL Baum



## Gast (27. Jan 2009)

```
public class Baum {

	Knoten wurzel;

	private class Knoten {

		Knoten Links;
		Knoten Rechts;
		Integer zahlenwert;

	}

	public boolean exists(int element) {
		Knoten Ba = wurzel;

		boolean exists = false;
		while (Ba != null) {
			exists = Ba.zahlenwert.equals(element);
			if (element > Ba.zahlenwert) {
				Ba = Ba.Rechts;

			}

			else {
				Ba = Ba.Links;
			}

			if (exists == true) {
				System.out.println("Das Element existiert bereits!");
				return exists;
			}

		}
		return exists;
	}

	public void insert(int element) throws ElementExistsException {
		Knoten Ba = wurzel;
		Knoten Blatt = new Knoten();
		Blatt.zahlenwert = element;
		Knoten tmp = Ba;
		if(wurzel == null){
			wurzel = Blatt;
		}
		if (true == exists(Blatt.zahlenwert)) {
		}
		else{
		while(Ba != null){
			if(Blatt.zahlenwert > Ba.zahlenwert){
				tmp = Ba;
				Ba = Ba.Rechts;
				if(Ba == null){
					tmp.Rechts = Blatt;
				}
			}
			else {
				tmp = Ba;
				Ba = Ba.Links;
				if(Ba== null){
					tmp.Links = Blatt;
					
				
				}
			}
		}

	}
	} // Anzahl Knoten abfrage anhand von einem Zähler.....
	public int NumberofNodes() {
		int k = 10;
		return k;
	}

	public int getHeight() {
		Knoten Ba = wurzel;
		int zaehlerlinks = 0;
		int zaehlerrechts = 0;
	
		while(Ba != null){
			if(Ba.Rechts!=null){
				zaehlerrechts =getHeight(Ba.Rechts);
			}
			else if (Ba.Links != null){
				zaehlerlinks = getHeight(Ba.Links);
				
			}
			else{
				return Math.max(zaehlerlinks, zaehlerrechts)+1;
			}
		}
	return 0;	
	}
	private int getHeight(Knoten wurzel){
		Knoten Ba = wurzel;
		int zaehlerlinks = 0;
		int zaehlerrechts = 0;
	
		while(Ba != null){
			if(Ba.Rechts!=null){
				zaehlerrechts = getHeight(Ba.Rechts);
			}
			else if (Ba.Links != null){
				zaehlerrechts = getHeight(Ba.Links);
				
			}
			else{
				return Math.max(zaehlerlinks, zaehlerrechts)+1;
			}
		}
	return 0;	
	}
//Kleinster Eintrag im Baum
	public int getMinimum() {

	}
//größter Eintrag im Baum
	public int getMaximum() {

	}
// Überprüfen ob AVL Baum und mit hilfe der Hilfsfunktion private boolean isAVLTree(Knoten wurzel)lösen!
	public boolean isAVLTree() {

	}

	private boolean isAVLTree(Knoten wurzel) {

	}

}
```


Hallo leute!
Ich hab komm  bei der aufgabe nicht weiter....einiges habe ich schon geschrieben aber die letzten 4 Einträge,weiß ich nicht wie ich lösen soll und wie ich die anzahl der Knoten des Baums anhand eines Zählers realisieren kann? 
Die aufgabenstellung ist kommentiert.
Wäre dankbar für eure hilfe...

lg


----------



## 0x7F800000 (27. Jan 2009)

Wie fast immer bei irgendwelchen Aufgaben mit Bäumen. Du überlegst dir, wie du die aufgabe für einen einzelnes Leaf zu lösen ist, und dann überlegst du dir, wie das problem zu lösen ist, wenn du das problem für die Kinder schon gelöst hast. Beide teilaufgaben bergen keine Tücken und sind für jedermann mit ein wenig Abstraktionsvermögen innerhalb von höchstens 10 Minutne machbar. Also mach zumindest mal einen Lösungsvorschlag ("kA wie anfangen" zählt nicht als Lösungsvorschlag)
Sag mal, bist du nicht zufällig noch einer aus einer gewissen "ainf" veranstaltung von einem gewissen Hr. Prof. O. V. ? ???:L Hab mir deren Vorlesungsplan durchgeschaut, sowas wie AVL-Bäume dürfte da grad ganz gut reinpassen :roll: ...


----------



## Bä*m (27. Jan 2009)

Keine Sorge, den muss man  bei uns nicht iimplementieren diese Woche. 
Wir haben was schöneres gefunden, das noch nicht da war.

Aber stimmt, ist erstaunlich passend.


----------



## 0x7F800000 (27. Jan 2009)

@Bä³m: Na seht ihr, jetzt hab ich euretwegen Paranoia^^ 
@OP: Okay, back 2 topic. Lösungsvoschläge?


----------



## Gast (27. Jan 2009)

ainf? und den prof kenne ich auch nicht........bei mir heißt es GDI
also für getMinimum() habe was geschrieben nur ist es falsch.....




```
public int getMinimum() {
		
		Knoten k=wurzel;
		while(k.Links)
			k=k.Links.Knoten;
		return k.zahlenwert;
	
		
	}
```


----------



## Bä*m (27. Jan 2009)

Wunderbar. Das wollten wir erreichen.

Das Minimum in einem AVL-Baum steht immer ganz links, das Maximum ganz rechts.


----------



## Gast (27. Jan 2009)

das weiß ich schon lange nur wie kann ich genau auf den kleinsten wert zugreifen.....?


----------



## 0x7F800000 (27. Jan 2009)

Gast hat gesagt.:
			
		

> also für getMinimum() habe was geschrieben nur ist es falsch.....


Doch, vom Sinn her ist das anscheinend sogar einigermaßen richtig, nur ist das kein Java :roll: kein korrektes java jedenfalls...


```
public int getMinimum() {	
		Knoten k=wurzel;
		while(k.Links)                    //das hier ist kein C, hier werden zeiger nicht explizit nach 0 bzw false gecastet
                                                       //da muss !=null hin
			k=k.Links.Knoten;     //was soll dieses ".Knoten" bedeuten?
		return k.zahlenwert;
	}
```


----------



## 0x7F800000 (27. Jan 2009)

Gast hat gesagt.:
			
		

> GDI


 hey, das will ich gar nicht wissen :roll: ^^


----------



## Gast (27. Jan 2009)

```
public int getMinimum() {
		
		Knoten k=wurzel;
		while(k.Links!=null)
			k=k.Links;
		
		return k.zahlenwert;
	
		
	}
//größter Eintrag
	public int getMaximum() {
		Knoten k=wurzel;
		while(k.Rechts!=null)
			k=k.Rechts;
		return k.zahlenwert;
```

.knoten sollte bedeuten das er auf die klasse knoten zugreifen soll.......
stimmt das was ich für die beiden geschrieben habe?


----------



## Guest (27. Jan 2009)

Andrey hat gesagt.:
			
		

> Gast hat gesagt.:
> 
> 
> 
> ...



GDI=Grundlagen der Informatik  :wink:


----------



## 0x7F800000 (27. Jan 2009)

Gast hat gesagt.:
			
		

> stimmt das was ich für die beiden geschrieben habe?


sinnfreie Fragestellung. Lass es doch einfach laufen und gug dir das Ergebnis an, der compiler braucht dafür 7ms ich brauche dafür >2.8 Sekunden. Menschen können da einfach nicht mithalten. Schließende Klammer vergessen, übrigens... -.- ^^


----------



## Bä*m (27. Jan 2009)

Gast hat gesagt.:
			
		

> das weiß ich schon lange nur wie kann ich genau auf den kleinsten wert zugreifen.....?


Hättest du das schon im Eingangsposting erwähnt, wäre ich nicht mit diesen Trivialitäten angekommen.

Damit ein Baum AVL-Baum ist, darf sich die Höhe des linken Teilbaums und des rechten Teilbaums jedes Knotens im Baum nur um maximal 1 unterscheiden. Eine Höhenmethode hast du ja schon, die musst du also nur entsprechend oft abfeuern oder ein bisschen modifizieren.


----------



## Gast (28. Jan 2009)

```
public class ElementExistsException extends Exception {

	
	public ElementExistsException() {
	}

	public ElementExistsException(String s) {
		super(s);
	}



	public static void main(String[] args) {
		
		try {
			throw new ElementExistsException();
		} catch (ElementExistsException e) {

			System.out.println(e.getMessage());

		}

	}

}
```
 
 er soll eine exception werfen.....wenn der eingebene wert existiert und den ausgeben....wie gibt er den wert aus? bzw wie greife ich auf die klasse baum-->insert()?


----------



## 0x7F800000 (28. Jan 2009)

mal ganz langsam.
wer bist du? immer noch derselbe gast mit demselben AVL-baum?
Und was ist das für eine Exception? "ElementExistsException" klingt für mich schonmal ziemlich sinnfrei...
_"Whaa, ich bin ein Baum und hab Elemente, die Welt geht unter..."_ :?: :bahnhof:


----------



## Gast (28. Jan 2009)

Ich bin der selbe gast....Mit dieser Exception will ich sorgen das kein wert 2 mal eingegeben wird, d.h Sollte ich ein wert 2 mal eingeben,dann soll sich das Exception auslösen und dazu noch denn eingegeben wert ausgeben?


----------



## 0x7F800000 (28. Jan 2009)

achso, ja, das kannst du natürlich machen, aber das ist eigentlich absolut nicht die übliche vorgehensweise
(was soll man damit erreichen? dadurch wird der User nur gezwungen, vorher selbst redundante elemente rauszufiltern, das könnte je nach situation ätzend sein)
Normalerweise würde man die "add()" methode mit einem boolean-rückgabewert versehen, der angibt, ob sich an deinem baum was verändert hat. Siehe zB hier: Set#.add(). Exceptions werden da keine geworfen, jedenfalls.

Aber gut, mal angenommen du willst die exception doch aus irgendeinem grund werfen... Was ist dein Problem damit? sieht doch soweit in ordnung aus?


----------



## Gast (28. Jan 2009)

Mein Problem ist das er das eingegene wert ausgibt.....nur wie schreibbe ich das in dem programm bzw exception rein?


----------



## 0x7F800000 (29. Jan 2009)

definiere doch die Integer-membervariable in deiner exception, und passe den Konstruktor entsprechend an, was soll man denn da großartig neuerfinden?


----------



## Gast (29. Jan 2009)

Integer-membervariable? wie meinst du das mit definieren? Ich dachte ich greife einfach nur auf die Klasse baum zu und dort soll der letzte eingegebene wert gespeichert werden...(deswegen die frage wie ich daruaf zugreifen kann)...


----------



## 0x7F800000 (29. Jan 2009)

Wieso soll denn die exception auf den baum zugreifen, der auch noch _für die Exception_ irgendetwas speichert? Spaghettiproduktion?


```
class ZuVielZeigsexception extends Exception{
   private int zeugsDasZuvielIst;
   public ZuVielZeugsException(int wasIstDennZuVielMannooo){
      super("Irgendwas zu viel oder so "+wasIstDennZuVielMannooo);
      zeugsDasZuvielIst=wasIstDennZuVielMannoooo; //kA wozu du das brauchst, und ob überhaupt...
   }
}


//sonstwo
throw new ZuVielZeugsException(123); //123 ist eindeutig zuviel!!!
```


----------

