Java ArrayList dynamisch vergrößern

[cl0udt]

Hallo zusammen,

bastle grad an einem Tree herum und möchte, wenn ich einen neuen Knoten hinzufüge, gleich den Index mit angeben, der sich wie folgt berechnet:

i = Vater
2i+1 = linker Sohn
2i+2 = rechter Sohn

Grundlage ist eine ArrayList.
Wenn ich jetzt 2x hintereinander einen rechten Sohn hinzufüge, dann wäre das (vorausgesetzt ich fange bei index 0 an) der index 2 und 6. Zwischendrin wäre der Array allerdings leer...dadurch wirft er mir eine Exception. Bin jetzt während dem schreiben auf die Idee gekommen, den rest mit nulls oder so zu füllen, gefällt mir aber nicht so gut. Welche art von array würde sich da anbieten, bzw. welche bessere Methode?

Danke schonmal!

 

[Yuuri]

Bastelst du eine Liste oder einen Baum? Beides zusammen geht nur schwer.

 

[cl0udt]

Naja möchte den Baum in einer Liste abbilden...eigentlich.

theoretisch könnte ich einfach sagen new int[10000] und da könnte ich schön rumhantieren mit dem index, leider unpraktisch, weil ich net weiß, wie groß der baum wird. Aber in ner ArrayList z.b. darf ich halt an Stelle 6 nix setzen, wenn an Stelle 5 nix sitzt.

mit diesen kleinen gleichungen oben, kann ich dann schön wieder den Vater von nem knoten finden und den Sohn von nem vater usw. in dem ich zurückrechne.

Is vll net ganz so einfach nachzuvollziehen, wenn man das hie rjetzt in 3 sätzen erklärt bekommt, aber von der logik her geht das eigentlich.

 

[maxFrisch]

so ganz verstehe ich das problem nicht. du hast eine liste mit einem element, dem vater. nun fügst du einen rechten sohn an. der ist dann das zweite element in der liste mit index x. dann fügst du dazu einen rechten sohn an, der ist dann element 3 in der liste mit index xy. wo genau soll da eine exception kommen?
wenn die knoten eh eine exakte id haben, mit der sich genau ausrechnen lässt, an welcher stelle vom baum sie stehen, ist es doch egal an welcher stelle der liste sie stehen.

 

[SgtBrightEyes]

Willst du denn nen fertigen Baum abbilden oder soll der noch wachsen können (wobei dann deine Liste ebenfalls mitwachsen soll)?

Wenn der Baum schon fertig ist, dann kannst du doch einfach aus der Tiefe des Baumes die Arraygröße bestimmen.

Wenn der noch wachsen kann, würde sich eher ne Kette anbieten, bei der du dann nachträglich Elemente hinzufügen und entfernen kannst. Oder du hantierst halt mit remove() und set() herum, was aber eigentlich aufs gleiche hinauskommt.

 

[xbrtll]

Naja möchte den Baum in einer Liste abbilden...eigentlich.

Und warum das?

Ein Baum besteht aus Knoten, die Eltern und Kinder haben (können). Ist doch eigentlich wie geschaffen für Objektorientierung.

Wenn du unbedingt willst, kannst du dann "darüber" noch eine Liste setzen, in der du alle Knoten abspeicherst.

 

[Redirion]

es gibt eine TreeMap in Java. Wozu also das Rad umständlich neu erfinden?

 

[xbrtll]

Zur Übung vielleicht?

Oder wenn man Anforderungen an die Datenstruktur hat, denen eine TreeMap nicht genügt.

 

[cl0udt]

Ich will nen sequentiellen Baum erstellen. Wenn ich einfach für jeden Knoten den Vater, linken und rechten Sohn speichere, brauch ich keinen Index mehr.

@SgtBrightEyes
er muss noch wachsen können

@maxFrisch
wenn ich dann aber den Vater vom Knote mit dem index-Attribut 38 finden will, kann ich net in der Array-Liste nach dem index 38 suchen, da ja im array alle nacheinander eingefügt werden. Dann müsste ich ja mit ner vorschleife über alle elemente gehen und das mit dem index-attribut 38 suchen

 

[xbrtll]

Ich will nen sequentiellen Baum erstellen. Wenn ich einfach für jeden Knoten den Vater, linken und rechten Sohn speichere, brauch ich keinen Index mehr.

Du kannst ja den Index trotzdem verwenden und so versuchen, die Datenstrukturen zu kombinieren.

Wenn du die Elemente ohne die Eltern-Kind-Beziehungen in eine Liste abbildest, müsstest du im Endeffekt einfach eine sortierte Liste erhalten - der "gedachte Baum" bringt dir dabei keine Vorteile mehr. (wobei ich mir das jetzt nicht allzu detailliert überlegt habe, sollte aber dennoch stimmen...)

 

[Killkrog]

Schau dir die Hashstrukturen an. HashMap, Hashtable, HashSet...
Ansonsten wären mehr Angaben hilfreich, was du genau mit dem Ding machen willst, damit man sich ne ordentliche Implementierung überlegen kann.

 

[Funart]

Wenn du unbedingt eine Liste oder derartiges verwenden willst tus aber an sich ist das kein Fall wo ich eine Liste verwenden würde.

Einfach ein Object mit parent und child objecten als member.
Wennst unbedingt ne Liste verwenden willst das gleiche nur speicherst die Objecte halt noch in der Liste ab.
Im normalfall ist aber nur das Root element direkt erreichbar.

 

[Loopo]

public class Mensch {
	private Mensch vater = null;
	private List<Mensch> soehne = new List<Mensch>();

	public Mensch(Mensch vater) {
		this.vater = vater;
	}

	public void setVater(Mensch vater) {
		this.vater = vater;
	}

	public void addSohn(Mensch sohn) {
		soehne.add(sohn);
	}

	public Mensch getVater() {
		return vater;
	}

	public Mensch getSoehne() {
		return soehne;
	}
}

War doch gar nicht so schwer!

 

[Whiz-zarD]

Wenn du unbedingt eine Liste oder derartiges verwenden willst tus aber an sich ist das kein Fall wo ich eine Liste verwenden würde.

Warum nicht?
Man kann auch einen allgemeinen Baum (mit n Knoten) mit hilfe eines Binären Baums abbilden, indem der linke und der rechte Knoten ebenfalls eine Liste ist.
http://de.wikipedia.org/wiki/Baum_(Graphentheorie)#B.C3.A4ume_als_Datenstruktur

 

[cl0udt]

@deepfritz
So eine Liste würde ich aber nur erhalten, wenn ich den Baumd er Reihe nach aufbaue, wenn ich dich richtig verstehe. Allerdings könnte ich die Knoten nach ihrem Index-Attribut sortieren, das wäre allerdings ne Möglichkeit. (ALlerdings wird das ziemlich rechenaufwendig bei vielen Knoten, denke ich)

@Loopo
Ja, so ähnlich hab ich mirs vorgestellt. Die sache ist nur, ich wollte die Söhne ja an einem bestimmten Index in der Liste haben, damit ich durch zurückrechnen auf den Sohn / Vater komme, den ich haben will

 

[xbrtll]

Die Frage ist eben, was du damit vorhast. Nur wenn du das verrätst, kann man sich sinnvoll über eine geeignete Datenstruktur unterhalten.

Bei einem Baum habe ich das noch nicht gemacht, aber eine Prioritätsschlange (als Heap) habe ich mal so implementiert, dass alle Elemente wieder einen "Rückbezug" auf die Position im Array haben (also die Indexstelle kennen, an der sie dort stehen).

 

[Killkrog]

Hat dir Hashing nix gebracht?
Um was für einen Binärbaum handelt es sich? Ist er balanciert?

 

[Zhak]

Falls du unbedingt ein Array verwenden möchtest, dann mach es halt dynamisch. D.h. immer wenn die Größe nicht mehr ausreicht verdopple es(z.B. IndexOutOfBoundsException abfangen und dann array = Arrays.copyOf(array,array.length*2).
Aber eigentlich nimmt man für Binäre Suchbäume keine Arrays da diese dynamisch wachsen sollen. Für Heaps ist das was anderes da diese sich von links auffüllen und man durch ein Array so an Effizienz gewinnt. Und wenn du nicht grad eine Übung machst solltest du die naive Implementierung eines binären Suchbaumes sowieso nicht verwenden, da der Baum dann ausartet.
Dafür gibt es dann balancierte Bäume(Rot-Schwarz/AVL,AB,...), die in Java schon implemenetiert sind. Ansonsten gäbe es auch noch die Skiplist, die dann ähnlich gut ist wie ein balancierter Baum und nicht so schwer zu implementieren ist bzw. auch schon in Java implementiert sein sollte.

 

[CoolHandLuke]

wenn du unbedingt die Indexrechnerrei behalten möchtest, könntest du auch eine HashMap<Integer, DeinDatenTyp> nutzen. Dabei speicherst du deinen Index als Integer.

map.put(2i+1, blah)

Ansonsten, wenn man eine Datenstruktur wie im "Mensch" Bsp. nutzt, (wobei ich "Söhne" auch noch nicht gehört habe in diesem Zusammenhang. Geschlechtsneutral: "Child" oder "Kindknoten", ja) benötigt man den Index nicht, da jeder Knoten sein parent kennt und weiterhin eine Liste aller Kindknoten enthält.

 

[IceMatrix]

Bastelst du eine Liste oder einen Baum? Beides zusammen geht nur schwer.

Stimmt nicht.

Einen Binärbaum kannst du wunderbar in ein einzelnes Array/Liste verpacken. Es wird in der Praxis auch genau so gemacht -> "Heap" .

Die "Löcher" kann man aber nicht komplett verhindern, solange der Baum nicht vollständig balanciert und voll gefüllt ist.