Stack, Verkettete Listen, Queue & Co.

[Hagen Reddmann]

<i>Aber dennoch entspricht diese Definition dem, was ich unter einem BTree verstehe. Dies scheint aber das zu sein was Du einen Node Baum nennst.(?) </i>

Nein, diese Definition ist exakt richtig für einen Binären Baum = BTree.

Ein verkettete Liste hat eine Anfang Node die einen Zeiger .Next auf die nächste Node enthält. Somit hat man ein Rootnode und diese zeugt auf Node1^.Node2^.Node3^.Node4^ usw. usw. Will man ein Element in so eine verkettete Liste einfügen so muß man ausgehen von der Rootnode diese Kette durchspringen. Ein BTRee hat eine Node mit einem Zeiger auf .LeftNode und .RightNode mehr nicht.

Ein Nodebaum hat eine Node mit einen Nodezeiger Children der die Rootnode einer verketteten List oder arrays of Node ist.

<pre>
type
PBTrieNode = ^TBTrieNode;
TBTrieNode = packed record
Symbol: Char;
Left: PBTrieNode;
Right: PBTrieNode;
end; <br>

PLinkNode = TLinkNode;
TLinkNode = packed record
Symbol: Char;
Next: PLinkNode;
end; <br>

PDoubleLinkNode = ^TDoubleLinkNode;
TDoubleLinkNode = packed record
Symbol: Char;
Next: PDoubleLinkNode;
Prev: PDoubleLinkNode;
end;<br>

PTreeNode = ^TTreeNode;
TTreeNode = packed record
Symbol: Char;
Children: PLinkNode;
// Children: PDoubleLinkNode;
// Children: array of PTreeNode;
end;<br>

PBTreeNode = ^TBTreeNode;
TBTreeNode = packed record
Symbol: Char;
Left: PBTreeNode;
Right: PBTreeNode;
Children: PBTreeNode;
// Children: PLinkNode;
// Children: PDoubleLinkNode;
end;<br>

</pre>

TBTreeNode = Node eines binären Baumes<br>
TLinkNode = Node einer einfach verketteten Liste<br>
TDoubleLinkNoe = Node einer doppelt verketteten Liste<br>
TTreeNode = Node eines Nodebaumes, bzw. einer hierarichen verlinkten Liste<br>
TBTreeNode = Node eines Binären Nodebaumes der zu jedem Binären Elemente weitere Unterelemente enthalten kann<br>

Man sieht das bei normalen BTree's keine verlinkten Listen entstehen können. Das Einfügen eines beliebigen Symbols führt immer dazu das die relative Gewichtung der beide untergeordneten Binären Bäume in .Left und .Right ausgewogen ist. D.h. die Anzahl der untergeordtenen Nodes in .Left und .Right ist im Idealfall nun um +-1 unterschiedlich. Egal ob man nun sortierte oder zufällige Werte einfügt.

Gruß Hage

[Uwe Merckens]

Hallo!

@Hagen<br>
<I>Ich verstehe auch nicht so richtig worauf deine Frage eigentlich hinauslaufen soll ?!
Werbung für ADT's, Frust an der OOP ?</I><br><br>
Also, wie gesagt, ich beschäftige mich hauptsächlich mit kfmn. Datenbankanwendungen und ich habe neulich ein Buch von Wolgang Müller "Grundlagen der Programmierung" in die Finger bekommen und mir den Stoff 'reingezogen'. Ich kann auch zugegebenermaßen nicht mit eurem Know How mithalten und habe mich daher gefragt, warum dieser gigantische Aufwand nötig ist, wenn ein RDBMS diese Aufgaben auch übernehmen kann. Aber neulich stiess ich eben auf die Notwendigkeit, ein "SELECT SUM GROUP BY" nachzubauen, weil die Abbildung einer temporären Tabelle, das Einlesen der notwendigen Daten, die darauffolgende Abfrage und das abschließende Löschen der temporären Tabelle sich nicht realisieren ließ (der Programmablauf war schneller wie der Zugriff auf die Datenbank und es hagelte Fehlermeldungen, dass die temporäre Tabelle in der Datenbank nicht zu finden sei).<br>
Vielleicht sind die von mir erstellten Applikationen, respektive die Problemstellungen, nicht anspruchsvoll genug gewesen so dass sich die Notwendigkeit des Einsatzes von ADT's bisher nicht ergeben hat. Nun habe ich aber damit angefangen und deswegen will ich es auch beherrschen. Daher meine Fragerei. Und ich war der Meinung, dass dieses Forum hier der richtige Ort dafür wäre.
<br>
Ich danke nochmals recht herzlich, für die kompetente Diskussion und die daraus resultierenden Anregungen.

Gruss
Uw

[Jochen Reichenberg]

Hallo nochmal.

@Uwe: Sorry, ich weiß, ich bin hier ein bißchen vom Thema abgekommen. Aber ich würde gerne noch ein bißchen weiter diskutieren, da ich anscheinend einem Denkfehler aufgesessen bin und ich das eben gerne geklärt hätte.

@Hagen: Ich hoffe, Du machst Dir die Mühe mir noch mal zu antworten. Ich hab' mir Deinen Source mal angesehen. Mir fehlt da ein wichtiger Punkt, der Zeiger auf das Datenobjekt. So mach' ich das in C++:
<PRE>
struct TBTreeNode
{
void* AObjectPointer; // Zeiger auf beliebiges Datenobjekt
TBTreeNode* LeftNode;
TBTreeNode* RightNode;
}
TBTreeNode* RootNode;
</PRE>
Um nochmal auf mein Beispiel von irgendwo weiter oben zurückzukommen: Die Datenobjekte sind vom Typ int. Es gibt 100 Stück. Wertebereich 1 - 100. Wenn ich nun in RootNode das Objekt mit Wert '1' einfüge, habe ich bereits eine Seite des Baums verloren, weil alle folgenden Werte größer sind, als der in der RootNode. Die LeftNode des RootNode bleibt ungenutzt. Beim Einfügen der '2' passiert das gleiche mit dem RightNode aus RootNode. Und so weiter: <BR>
<PRE>
1 <BR>
| <BR>
+---+---+ <BR>
x 2 <BR>
| <BR>
+---+---+ <BR>
x 3 <BR>
| <BR>
+---+---+ <BR>
x 4 <BR>
</PRE>
Die x stellen jeweils ungenutzte Nodes dar. Somit 'verkommt' der Baum zu einer 'verketteten Liste', weil die Daten sortiert eingefügt werden. Alle linken Nodes bleiben ungenutzt.<BR>
Wo mache ich denn den Denkfehler?

Grüße Joche

[Jochen Reichenberg]

@Hagen: Ich hab' mích mal ein bißchen über Red/Black Tree informiert. Das ist das was ich (leichtsinnigerweise) als 'BTree mit Logik' bezeichnet habe. Und somit gehe ich mal davon aus, daß sich die (Veständnis-)Probleme gelöst haben. Du wirst wohl einen BTree immer als z.B. Red/Black-Tree implementieren und nicht wie in dem simplen Beispiel meines vorherigen Postings. (Wobei sich dann nur noch die Frage stellt, ob man das überhaupt schon als BTree bezeichnen darf.)

Grüße Joche

[Hagen Reddmann]

@Jochen, korrekt wenn ich Binäre Bäume meine dann meine ich immer "ausbalancierte" Binäre Bäume, alle anderen Binäre Bäume die keine Ausbalancierung haben sind im Grunde keine "Binären Bäume". Das Problem ist wiedermal der Mensch, der als Programmierer die Definitionen der Methematiker nicht verstanden hat. Mit der Zeit wurden nicht balancierte Bäume in die gleiche Schublade wie die balancierten Binären Bäume gesteckt. Dies ist aber falsch, denn der erste Binäre Baum Algorithmus war von Anfang an ein balancierter Binärer Baum -> der AVL-Baum.

<I>Somit "verkommt" der Baum zu einer "verketteten Liste" </i>

Und ich meine das diese verkettete Liste im Bestfall zu einem binären Baum verkommt

Gruß Hage

[Hagen Reddmann]

Ach übrigens, die "Datenobjecte" habe ich absichtlich nicht in meinen Nodes explizit dargestellt. Ich persönlich würde IMMER die Nodes um diese Datenobjecte direkt erweitern, statt wiederum Zeiger auf dynamische Daten zu verwalten. Dies hat mehrere Gründe:
<li>hohe Performance
<li>meinsten sind es Daten mit fester Länge somit sind die Nodes fester Größe. Dadurch kann man wiederum statt mit dynamisch allozierten Nodes mit Nodes arbeiten die Bestandteil eines großen preallozierten Node arrays sind.
<li>wenn man solche Algorithmen verwednetet dann ist es immer am besten sich vom Gedanken der "Universalität" zu verabschieden. Der Algorithmus als Idee ist universell dessen Anwendung aber nie. Nur durch die Anpassung dieser Idee an die speziellen Bedürfnisse bringt den optimalen Erfolg.<br>

Gerade der letzte Punkt ist mein Argument für OOP und gegen ADT.

Gruß Hage

[Jochen Reichenberg]

@Hagen: Dann sind wir uns ja jetzt einig. ;-) <BR>Zumindest was die Definition angeht. Was die Implementation angeht, werde ich mich da wohl nochmal eingehender mit beschäftigen müssen. Na ja, in den zwei Anwendungen, in denen ich Bäume verwende, sind diese ausreichend schnell - obwohl komplett dynamisch erzeugt...

Grüße, Danke und Schönes Wochenende,

Joche

[Uwe Merckens]

Hallo Ihr Beiden!

Muß sagen - bin mächtig beeindruckt! Willkommen auf der Delphi Uni! So muß es sein.

Ebenfalls schönes Wochendende

Uwe

Nicht Geiz - Lernen ist gei

[Matthias F.]

Hallo an alle!

Mit Interesse habe ich die Diskussion in diesem Forum verfolgt. Hut ab - saubere Diskussion.

Ich für meinen Teil kann mir nicht mehr vorstellen ohne das TList Objekt zu arbeiten. Eine Implementierung des ADT Verkettete Liste. Alle Operationen zum Einfügen, Löschen, Suchen etc. sind dort implementiert. Ich muss mich also nicht mehr selbst um das Verzeigern (ich hasse diese ^ und @) kümmern.

An dieser Stelle schlägt die OO voll zu:

1. Es ist egal, welche Objekte ich in der Liste verwalte - die Funktionen bleiben immer gleich.
2. Will ich es komfortabler haben und nicht mit Cast's auf Pointern rumwerken, leite ich die Liste ab, überlade ein paar properties, functions und procedures und fertig.
3. Brauche ich einen Stack (FCLS) oder eine Queue (FCFS), schwupps abgelitten, Funktionalität dazu und fertig.

Die Bezeichnung ADT tragen diese Dinger nicht umsonst. Sie sind eben abstrakte theoretische!!! Datentypen. Für konkrete Implementierungen müssen diese mit Hilfe von OO Mittel spezifiziert werden.

So ergänzt sich OOP und ADT auf wundersam, elegante Weise.

ABER: Da wo es hingehört. Ich würde mir niemals anmaßen, SQL Serverfunktionalität selbst zu programmieren. Die Theorie dieser Dinger ist nicht umsonst älter als die OO Theorien.

Grüße FU