<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
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
Comment