| Autor |
Beitrag |
liquid air
  
Beiträge: 76
|
Verfasst: Sa 21.08.10 00:57
Hi, ich veruch grad nen AVLTree zu implementieren, bisher klappt wohl auch soweit alles, aber jetzt bin ich ans rebalancing gekommen, und das will einfach nicht so recht. Die Rotate-Methoden scheinen richtig zu sein, jedenfall ist die binäre-Suchbaum-Eigenschaft im Baum immer gegeben, egal wieviel ich rotiere ^^
Also kann es eigentlich nur noch an der rebalance() Methode liegen. Diese wird nach dem add() aufgerufen für den neu geaddeten Knoten, aber ich hab auch eine rebalanceAll() Methode, die ALLE Knoten von unten nach oben einmal rebalanciert. Auch wenn ich diese am Schluss aufrufe, stimmt der Baum manchmal nicht. Es kann also eigentlich nur noch an der rebalance() Methode liegen, denke ich.
Das Problem ist, dass ich am Montag die Klausur dazu schreibe, und schon seit Tagen hammermässig Gas geben muss mitm üben. Und wenn ich nicht bald mal weiterkomm mit dem AVL hier, dann wird das nix gutes mehr werden :'( Also bitte, bitte, helft mir!! xD
Hier mal meine Klassen:
(Sorry falls etwas lange und unübersichtlich, programmiere grade seit langem nochmal zum ersten Mal Java)
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
| package avl_tree_5;
public class AVLNode {
private Object key, value;
private AVLNode left, right, parent;
public AVLNode(Object key) throws Exception {
this(key, key);
}
public AVLNode(Object key, Object value) throws Exception {
if (key == null)
throw new Exception("Uebergebener Parameter Key ist NULL!");
if (value == null)
throw new Exception("Uebergebener Parameter Value ist NULL!");
this.key = key;
this.value = value;
this.setLeft(null);
this.setRight(null);
}
public boolean isLeaf() {
return (this.left == null && this.right == null);
}
public int compareTo(AVLNode n) {
return ((Comparable) this.key).compareTo(n.getKey());
}
public String toString() {
String s = "";
s += "(" + this.key.toString() + ")";
return s;
}
public void setLeft(AVLNode n) throws Exception {
this.left = n;
}
public void setRight(AVLNode n) throws Exception {
this.right = n;
}
public Object getKey() {
return key;
}
public Object getValue() {
return value;
}
public AVLNode getLeft() {
return left;
}
public AVLNode getRight() {
return right;
}
public AVLNode getParent() {
return parent;
}
public void setParent(AVLNode parent) {
this.parent = parent;
}
public void hilfe() {
System.out.println("---");
System.out.println("GetHilfe: ");
System.out.print(this.toString());
System.out.print(" ; left: " + this.getLeft());
System.out.print(" ; right: " + this.getRight());
System.out.print(" ; parent: " + this.getParent());
System.out.println("---");
}
} |
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:
52:
53:
54:
55:
56:
57:
58:
59:
60:
61:
62:
63:
64:
65:
66:
67:
68:
69:
70:
71:
72:
73:
74:
75:
76:
77:
78:
79:
80:
81:
82:
83:
84:
85:
86:
87:
88:
89:
90:
91:
92:
93:
94:
95:
96:
97:
98:
99:
100:
101:
102:
103:
104:
105:
106:
107:
108:
109:
110:
111:
112:
113:
114:
115:
116:
117:
118:
119:
120:
121:
122:
123:
124:
125:
126:
127:
128:
129:
130:
131:
132:
133:
134:
135:
136:
137:
138:
139:
140:
141:
142:
143:
144:
145:
146:
147:
148:
149:
150:
151:
152:
153:
154:
155:
156:
157:
158:
159:
160:
161:
162:
163:
164:
165:
166:
167:
168:
169:
170:
171:
172:
173:
174:
175:
176:
177:
178:
179:
180:
181:
182:
183:
184:
185:
186:
187:
188:
189:
190:
191:
192:
193:
194:
195:
196:
197:
198:
199:
200:
201:
202:
203:
204:
205:
206:
207:
208:
209:
210:
211:
212:
213:
214:
215:
216:
217:
218:
219:
220:
221:
222:
223:
224:
225:
226:
227:
228:
229:
230:
231:
232:
233:
234:
235:
236:
237:
238:
239:
240:
241:
242:
243:
244:
245:
246:
247:
248:
249:
250:
251:
252:
253:
254:
255:
256:
257:
258:
259:
260:
261:
262:
263:
264:
265:
266:
267:
268:
269:
270:
271:
272:
273:
274:
275:
276:
277:
278:
279:
280:
281:
282:
283:
284:
285:
286:
287:
288:
289:
290:
291:
292:
293:
294:
295:
296:
297:
298:
299:
300:
301:
302:
303:
304:
305:
306:
307:
308:
309:
310:
311:
312:
313:
314:
315:
316:
317:
318:
319:
320:
321:
322:
323:
324:
325:
326:
327:
328:
329:
330:
331:
332:
333:
334:
335:
336:
337:
338:
339:
340:
341:
342:
343:
344:
345:
346:
347:
348:
349:
350:
351:
352:
353:
354:
355:
356:
357:
358:
359:
360:
361:
362:
363:
364:
365:
366:
367:
368:
369:
370:
371:
372:
373:
374:
375:
376:
377:
378:
379:
380:
381:
382:
383:
384:
385:
386:
387:
388:
389:
390:
391:
392:
393:
394:
395:
396:
397:
398:
399:
400:
401:
402:
403:
404:
405:
406:
407:
408:
409:
410:
411:
412:
413:
414:
415:
416:
417:
418:
419:
420:
421:
422:
423:
424:
425:
426:
427:
428:
429:
430:
431:
432:
433:
434:
435:
436:
437:
438:
439:
440:
441:
442:
443:
444:
445:
446:
447:
448:
449:
450:
451:
452:
453:
454:
455:
456:
457:
458:
459:
460:
461:
462:
463:
464:
465:
466:
467:
468:
469:
470:
471:
472:
473:
474:
475:
476:
477:
478:
479:
480:
481:
482:
483:
484:
485:
486:
487:
488:
489:
490:
491:
492:
493:
494:
495:
496:
497:
498:
499:
500:
501:
502:
503:
504:
505:
506:
507:
508:
509:
510:
511:
512:
513:
514:
515:
516:
517:
518:
519:
520:
521:
522:
523:
524:
525:
526:
527:
528:
529:
530:
531:
532:
533:
534:
535:
536:
537:
538:
539:
540:
541:
542:
543:
544:
545:
546:
547:
548:
549:
550:
551:
552:
553:
554:
555:
556:
557:
558:
559:
560:
561:
562:
563:
564:
565:
566:
567:
568:
569:
570:
571:
572:
573:
574:
575:
576:
577:
578:
579:
580:
581:
582:
583:
584:
585:
586:
587:
588:
589:
590:
591:
592:
593:
594:
595:
596:
597:
598:
599:
600:
601:
602:
603:
604:
605:
606:
607:
608:
609:
610:
611:
612:
613:
614:
615:
616:
617:
618:
619:
620:
621:
622:
623:
624:
625:
626:
627:
628:
629:
630:
631:
632:
633:
634:
635:
636:
637:
638:
639:
640:
641:
642:
643:
644:
645:
646:
647:
648:
649:
650:
651:
652:
653:
654:
655:
656:
657:
658:
659:
660:
661:
662:
663:
664:
665:
| package avl_tree_5;
import java.awt.print.Printable;
import java.util.Stack;
public class AVLTree {
public AVLNode root;
public AVLNode nodeIt;
private boolean found;
private int heigthCounter;
private boolean avlNature;
public AVLTree() {
root = null;
}
boolean debugMode = false;
protected void debugMsg(String message) {
if (debugMode) System.out.println(this.getClass() + ": " + message);
}
public void add(Object key) throws Exception {
System.out.println("\n -> Mache add(" + key + ")");
AVLNode n = new AVLNode(key);
if (isEmpty()) {
root = n;
} else {
if (key.getClass() != root.getKey().getClass())
throw new Exception("der Key des neuen Objekts hat andere "
+ "Klasse als die anderen Keys im Baum");
findKey(key);
if (n.compareTo(nodeIt) < 1)
nodeIt.setLeft(n);
else
nodeIt.setRight(n);
n.setParent(nodeIt);
System.out.println("\n -> Mache Baum Rebalancieren");
rebalance(n);
System.out.println("\n -> Baum erfolgreich rebalanciert");
}
ausgabe2();
}
public void rebalanceAll() throws Exception { rebalanceAll(root);
}
public void rebalanceAll(AVLNode n) throws Exception {
if (n.getLeft() != null)
rebalance(n.getLeft());
if (n.getRight() != null)
rebalance(n.getRight());
rebalance(n);
}
public void rebalance(AVLNode n) throws Exception {
try {
AVLNode gf = n.getParent().getParent(); if (!isAVLNode(gf)) {
if (gf.getLeft() != null) {
if (gf.getLeft().getLeft() == n) ror(findKeyNode(gf.getKey()));
else if (gf.getLeft().getRight() == n) doppelRor(findKeyNode(gf.getKey()));
}
if (gf.getRight() != null) {
if (gf.getRight().getLeft() == n) doppelRol(findKeyNode(gf.getKey()));
else if (gf.getRight().getRight() == n) rol(findKeyNode(gf.getKey()));
}
}
if (n.getParent() != null) rebalance(n.getParent());
} catch (Exception e) {
System.out.println(e);
System.out.println("fertig mit rebalance");
}
}
public boolean isEmpty() {
return (this.root == null);
}
public boolean findKey(Object key) throws Exception {
if (key.getClass() != root.getKey().getClass())
throw new Exception("der Key des gesuchten Objekts hat andere "
+ "Klasse als die anderen Keys im Baum");
AVLNode seekedNode = new AVLNode(key);
found = false;
nodeIt = null;
return (findKey(root, seekedNode));
}
public AVLNode findKeyNode(Object key) throws Exception {
if (findKey(key))
return nodeIt;
else
return null;
}
private boolean findKey(AVLNode n, AVLNode seekedNode) {
if (seekedNode.compareTo(n) == 0) {
found = true; nodeIt = n; } else if (n.isLeaf()) {
nodeIt = n;
} else {
if (seekedNode.compareTo(n) < 1) {
if (n.getLeft() == null)
nodeIt = n;
else
findKey(n.getLeft(), seekedNode);
} else { if (n.getRight() == null)
nodeIt = n;
else
findKey(n.getRight(), seekedNode);
}
}
return found;
}
public int getHeigthTree() { return (getHeigthNode(getRoot()));
}
public int getHeigthNode(AVLNode n) { if (n == null) return -1; else { heigthCounter = 0;
getHeigth(n, 0);
return heigthCounter;
}
}
private void getHeigth(AVLNode n, int heigth) {
if (heigth > heigthCounter)
heigthCounter = heigth;
if (n.getLeft() != null)
getHeigth(n.getLeft(), heigth + 1);
if (n.getRight() != null)
getHeigth(n.getRight(), heigth + 1);
}
public boolean isAVLTree() { if (!isEmpty()) {
avlNature = true;
isAVL(root);
return avlNature;
} else
return true;
}
private void isAVL(AVLNode n) {
if (!isAVLNode(n))
avlNature = false;
else {
if (n.getLeft() != null)
isAVL(n.getLeft());
if (n.getRight() != null)
isAVL(n.getRight());
}
}
public boolean isAVLNode(AVLNode n) { int a = getHeigthNode(n.getLeft());
int b = getHeigthNode(n.getRight());
if (a == b)
return true;
else if (a + 1 == b || a == b + 1)
return true;
else
return false;
}
public void toStringDirectOut() {
System.out.println("");
toStringDirectOut(root);
}
private void toStringDirectOut(AVLNode n) {
if (n.getLeft() != null)
toStringDirectOut(n.getLeft());
System.out.println(n.toString() + " Vater: " + n.getParent()); if (n.getRight() != null)
toStringDirectOut(n.getRight());
}
public AVLNode rol(AVLNode n) throws Exception {
System.out.println("\n -> Mache rol(" + n + ")");
if (n == null)
throw new Exception(n + " ist null -> kein ROL möglich!");
if (n.getRight() == null)
throw new Exception(n + " hat kein RightChild -> kein ROL möglich!");
boolean nIsLeftChild;
AVLNode grandParent = n.getParent();
AVLNode kind = n.getRight();
AVLNode innererEnkel = kind.getLeft();
if (grandParent != null) {
if (grandParent.getLeft() == n) nIsLeftChild = true;
else
nIsLeftChild = false;
}
n.setParent(kind);
n.setRight(innererEnkel);
kind.setLeft(n);
kind.setParent(null);
if (innererEnkel != null)
innererEnkel.setParent(n);
if (grandParent != null) {
kind.setParent(grandParent);
if (grandParent.getLeft() == n) grandParent.setLeft(kind);
else
grandParent.setRight(kind);
}
AVLNode it = n;
while (it.getParent() != null)
it = it.getParent();
root = it;
ausgabe2();
return kind; }
public AVLNode ror(AVLNode n) throws Exception {
System.out.println("\n -> Mache ror(" + n + ")");
if (n == null)
throw new Exception(n + " ist null -> kein ROR möglich!");
if (n.getLeft() == null)
throw new Exception(n + " hat kein LeftChild -> kein ROR möglich!");
boolean nIsLeftChild;
AVLNode grandParent = n.getParent();
AVLNode kind = n.getLeft();
AVLNode innererEnkel = kind.getRight();
if (grandParent != null) {
if (grandParent.getRight() == n) nIsLeftChild = true;
else
nIsLeftChild = false;
}
n.setParent(kind);
n.setLeft(innererEnkel);
kind.setRight(n);
kind.setParent(null);
if (innererEnkel != null)
innererEnkel.setParent(n);
if (grandParent != null) {
kind.setParent(grandParent);
if (grandParent.getRight() == n) grandParent.setRight(kind);
else
grandParent.setLeft(kind);
}
AVLNode it = n;
while (it.getParent() != null)
it = it.getParent();
root = it;
ausgabe2();
return kind; }
public void doppelRor(AVLNode n) throws Exception {
System.out.println("\n -> Mache doppelRor(" + n + ")");
try {
AVLNode temp = n.getLeft();
rol(temp);
ror(n);
System.out.println("\n -> doppelRor erfolgreich");
} catch (Exception e) {
System.out.println("\n -> " + e);
System.out.println("\n -> doppelRor klappte nicht");
}
ausgabe2();
}
public void doppelRol(AVLNode n) throws Exception {
System.out.println("\n -> Mache doppelRol(" + n + ")");
try {
AVLNode temp = n.getRight();
ror(temp);
rol(n);
System.out.println("\n -> doppelRol erfolgreich");
} catch (Exception e) {
System.out.println("\n -> " + e);
System.out.println("\n -> doppelRol klappte nicht");
}
ausgabe2();
}
public void getHilfeTree() {
getHilfeTree(root);
}
private void getHilfeTree(AVLNode n) {
n.hilfe();
System.out.println(n + " is AVL: " + isAVLNode(n));
if (n.getLeft() != null)
getHilfeTree(n.getLeft());
if (n.getRight() != null)
getHilfeTree(n.getRight());
}
private String[][] arr;
private int hoch;
private String leerFeld = " ";
public void ausgabe2() {
System.out.println("\n==== Ausgabe2: Hierarchisch ====");
if (isEmpty()) System.out.println("\n null");
else if (root.getLeft() == null && root.getRight() == null)
System.out.println("\n " + root);
else if (getHeigthTree() == 1) {
arr = new String[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
arr[i][j] = leerFeld;
}
}
arr[0][1] = root.toString();
if (root.getLeft() != null && root.getRight() != null) {
arr[1][1] = "--+--";
arr[2][0] = "" + root.getLeft();
arr[1][0] = " .--";
arr[2][2] = "" + root.getRight();
arr[1][2] = "--. ";
} else {
if (root.getLeft() != null) {
arr[1][1] = "--+ ";
arr[2][0] = "" + root.getLeft();
arr[1][0] = " .--";
} else { arr[1][1] = " +--";
arr[2][2] = "" + root.getRight();
arr[1][2] = "--. ";
}
}
for (int i = 0; i < 3; i++) { System.out.print("\n ");
for (int j = 0; j < 3; j++) {
System.out.print(arr[i][j]);
}
}
System.out.println("");
} else {
int tiefe = this.getHeigthTree();
int breit = (int) (Math.pow(2, (tiefe + 1))) - 1;
hoch = (2 * tiefe) + 1;
arr = new String[hoch][breit];
for (int i = 0; i < hoch; i++) {
for (int j = 0; j < breit; j++) {
arr[i][j] = leerFeld;
}
}
arr[0][(breit / 2)] = root.toString();
arr[1][breit / 2] = " + ";
if (root.getLeft() != null)
xwert(root.getLeft(), (breit / 2), ((int) Math.pow(2,
getHeigthNode(root))), 1, 0);
if (root.getRight() != null)
xwert(root.getRight(), (breit / 2), ((int) Math.pow(2,
getHeigthNode(root))), 2, 0);
int ersteBeschriebeneSpalte = 0;
boolean boo = false;
; for (int i = 0; i < breit; i++) {
for (int j = 0; j < hoch; j++) {
if (arr[j][i] != leerFeld)
boo = true;
}
if (!boo)
ersteBeschriebeneSpalte++;
}
for (int i = 0; i < hoch; i++) { System.out.print("\n ");
for (int j = ersteBeschriebeneSpalte; j < breit; j++) {
System.out.print(arr[i][j]);
}
}
System.out.println("");
}
System.out.print("\n======== / Ausgabe2 ==========\n");
}
private void xwert(AVLNode thisNode, int vater, int potenz, int richtung,
int ywert) {
int ergebnis;
if (richtung == 1)
ergebnis = (vater - (potenz / 2));
else
ergebnis = (vater + (potenz / 2));
if (richtung == 1) {
arr[(ywert + 1)][ergebnis] = " .---";
int ii = ergebnis;
while (arr[(ywert + 1)][ii + 1] == leerFeld) {
ii++;
arr[(ywert + 1)][ii] = "------";
}
} else {
arr[(ywert + 1)][ergebnis] = "---. ";
int ii = ergebnis;
while (arr[(ywert + 1)][ii - 1] == leerFeld) {
ii--;
arr[(ywert + 1)][ii] = "------";
}
}
arr[(ywert + 2)][ergebnis] = "" + thisNode;
if (thisNode.getLeft() != null && thisNode.getRight() != null)
arr[(ywert + 3)][ergebnis] = "--+--";
else if (thisNode.getLeft() != null)
arr[(ywert + 3)][ergebnis] = "--+ ";
else if (thisNode.getRight() != null)
arr[(ywert + 3)][ergebnis] = " +--";
if (thisNode.getLeft() != null)
xwert(thisNode.getLeft(), ergebnis, (potenz / 2), 1, (ywert + 2));
if (thisNode.getRight() != null)
xwert(thisNode.getRight(), ergebnis, (potenz / 2), 2, (ywert + 2));
}
public AVLNode getRoot() {
return this.root;
}
public static void main(String[] args) throws Exception {
AVLTreeTest.main(args);
}
} |
Edit: Ohje, Format is furchtbar. Tut mir leid, keine Java Tags gefunden, und die C# Tags verschnippeln das Java Format völlig...Sorry...
|
|
Xion
Beiträge: 1952
Erhaltene Danke: 128
Windows XP
Delphi (2005, SmartInspect), SQL, Lua, Java (Eclipse), C++ (Visual Studio 2010, Qt Creator), Python (Blender), Prolog (SWIProlog), Haskell (ghci)
|
Verfasst: Sa 21.08.10 07:19
Ja...ich hab das nur mal überflogen...du machst das irgendwie anders als ich...aber Fehler suchen...
Ich hab ne (für mich) einfachere Idee 
Theorie: www.tu-ilmenau.de/fa...-Kap-4-blaettern.pdf
Irgendwo weiter unten gehts um AVL-Bäume
Java-Implementation (im Anhang)
ACHTUNG
 Der Code hat einen Fehler, und zwar werden die neuen Balancefactoren nach den Doppelrotationen falsch berechnet. In dem pdf sind weiter unten 2 kleine Tabellen dargestellt, die müsste man da wohl noch einbauen.
Ich hab zuerst einen einfachen Binärbaum programmiert. Wenn man den Konstruktor mit (False) bedient kriegt man deswegen nur einen einfachen Binärbaum. Dann habe ich die AVL Eigenschaften draufgesetzt. Alle Methoden, die mit AVL zu tun haben, beginnen mit AVL_.
Achja, und wenn du ihn einfach nur kopierst (copy und paste) wärs nett wenn du meinen Namen drin stehen lässt 
Einloggen, um Attachments anzusehen!
_________________ a broken heart is like a broken window - it'll never heal
In einem gut regierten Land ist Armut eine Schande, in einem schlecht regierten Reichtum. (Konfuzius)
|
|
liquid air 
Beiträge: 76
|
Verfasst: Sa 21.08.10 15:44
Grad rausgefunden was los war...Hab vergessen bei der add() Methode abzufragen dass keine doppelten Elemente vorkommen können. Dabei is die rebalance Methode davon ausgegangen, und is deshalb net mit doppelten Elementen klargekommen. Und in so nem Fall is dann die Ordnung ganz kaputtgegangen...^^ Aber jetzt gehts endlich : )))
|
|
|
