建築及在Smalltalk

查詢樣品一般樹使用在SqueakSource B樹包（或者你可以知道任何其他），並給出以下樹建築及在Smalltalk

-Root 
| 
--Node1 
| 
--Node2 
---Node21 
---Node22 
---Node23 
----Node231 
----Node232 
-----Node2321 
----Node233 
| 
--Node3

我試着寫以下但沒有成功：

構建樹
鑑於Node23回答它的直接孩子
由於節點2回答所有的孩子
由於任何節點，回答其父
收集所有的孩子

這不是功課，我爲什麼要請一個基本的例子的原因是因爲在B樹的情況下，文件是幾乎不存在，而且測試對於理解基本用法來說還不夠好，實際上，示例中混合了斷言和使用便利方法。

來源

2011-08-19 user869097

如果您不太關心執行速度，那麼SqueakSource中有一個廣泛文檔化的軟件包用於此目的，最初爲VisualWorks發佈該軟件包http://www.squeaksource.com/TreeLW.html。

您可以用來構建樹的一個類是SKPVTreeLW，它支持值，子樹，超樹和一個鍵。你可以實現你的例子實現這樣的事情：

t := SKPVTreeLW 
    key: '1' 
    value: 'N' 
    subTrees: { 
     (SKPVTreeLW key: '2' value: 'A') . 
     (SKPVTreeLW key: '3' value: 'B' subTrees: { 
      (SKPVTreeLW key: '31' value: 'C' subTrees: { (SKPVTreeLW key: '311' name value: 'D') }) . 
      (SKPVTreeLW key: '32' value: 'E' subTrees: Array empty) }) . 
     (SKPVTreeLW key: '4' value: 'F') . 
     (SKPVTreeLW key: '5' value: 'G') . 
     (SKPVTreeLW key: '6' value: 'H') }. 
" Subtrees of node 'B' " 
t recursiveDetect: [ : s | s value = 'B' ] 
     inclusive: true 
     topDown: true 
     breadthFirst: true. 
" or searching by key " 
t atKey: '3' 
" Childrens as nodes " 
t recursiveSubTrees: true. 
" Direct children " 
t values.

來源

2011-08-24 16:56:07

A B-Tree是將鍵與值相關聯的排序數據結構。 B樹允許您處理大量的數據，並保證在對數時間內的搜索，插入和刪除。上SqueakSource的BTree Package如下的Smalltalk的Dictionary的協議：

at:和at:ifAbsent:被用於搜索給定的關鍵值，
at:put:用於插入一個鍵和值的對，和
removeKey:用於刪除密鑰。

此外，從Dictionary知道所有的迭代器功能的支持（do:，keysDo:，valuesDo:，keysAndValuesDo:，...）;以及幾個重複範圍的鍵（from:do:,from:to:do:,upTo:do:，...）。通常情況下，除非內置的Dictionary類出現性能問題，否則應用程序代碼中不應該需要B-Tree集合。

在我看來，你試圖修改一個B-Tree的內部工作。你不應該這樣做，BTree類會自動自動重組，以始終提供最有效的表示（這主要是測試驗證的內容）。如果你想管理你自己的樹，爲什麼不創建你自己的Node類包含OrderedCollection子節點和一個父鏈接？

來源

2011-08-19 16:31:41

建築及在Smalltalk

回答

相關問題