BinNode

Bachelor Algorithmen und Datenstrukturen
1

Frage zur Aufgabenstellung

Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.

2

BinNode
hallo,

in der Aufgabenstellung wird zwischen Bäumen mit natürlicher ordnung und solchen ohne natürliche Ordnung unterschieden.

Sollen wir das auch implementieren, denn Bisher erschein mir jeder weg, der theoretisch möglich wäre um das Generic von AbstractBinNode zu umgehen recht absurd.

3

In unserem Fall haben die Werte im Baum immer eine natürliche Ordnung (durch den Generic, bzw. dessen Eingrenzung).
Da diese aber nur bei Suchbäumen relevant ist, dürfen in Nicht-Suchbäumen auch values == null eingefügt werden.
Da allerdings in einem Suchbaum die values miteinander verglichen werden würden, sind dort values == null verboten.

1 „Gefällt mir“
4

Ah, ok… Also wird das geprüft, wenn geprüft wird, ob es ein Suchbaum ist… Ok…

5

Noch eine weitere Frage:

Bei den Heaps steht etwas von links-vollständig.

Was genau ist damit gemeint?

6

Zwei Eigenschaften müssen erfüllt sein:
Jede Ebene bis auf die unterste muss komplett gefüllt sein.
In der untersten Ebene müssen alle Knoten so weit links wie möglich sein.

7

Genau…

Und dann steht da noch:

It is not required that the tree is almost complete, since this method is working on a tree structure rather than an array embedded heap.

bzw. im Aufgabentext in etwa dasselbe nur mit links-vollständig statt almost complete.

Ich frage mich, ob das eben noch irgendeine Bedeutung hat, also z.B. dass Knoten ohne Wert in dem geordnetem Baum so betrachtet werden, als wären sie nicht vorhanden, um rechte Teilbäume zu erzeugen, ohne einen linken dazu…

8

Je nachdem welches Lehrbuch man befragt, gibt es verschiedene Definitionen von “complete” bei Binärbäumen; meist bezeichnet nur man solche Bäume als complete:

       o
   o        o
o  o      o   o

Die also komplett aufgefüllt sind (vollständig sind)

Hier ist aber lediglich almost complete gemeint, was meiner Meinung nach gleichbedeutend mit linksvollständig ist. Da würde folgender Baum sich dafür qualifizieren, obwohl er nach obiger Definition nicht complete ist. (und auch nicht full, da nicht jeder Knoten entweder Blatt ist oder genau 2 Kinder hat)

       o
  o        o
o  o     o

Solche semantischen Fragen muss man aber immer von Vorlesung zu Vorlesung klären; das ist gefühlsmäßig überall anders definiert.

9

Hm, ok…Das beim Verständnis, ob in der Aufgabe noch etwas anderes verlangt ist nicht wirklich weiter, da das linksvollständig dann äquivalent mit der Heapeigenscahft wäre.

Ich danke euch für eure Hilfen und Mühen!

10

Korrigiere: Ich meinte das links-vollständig mit dem shape, nicht mit dem heap property übereistimmt und dieses sollen wir aber erfüllen:

Definiert wird dieses Attribut über den Wikipediaartikel:

Das widerspricht sich leider mit dem Aufgabenblatt, in dem links-vollständig nicht vorausgesetzt wird und ausdrücklich gesagt wird, dass dieses nicht vorausgesetzt wird.

In der Vorlesung wurde „links-vollständig“ kurz angesprochen und entspricht der Definition des Shape Properties.