Построение и запрос образца общего дерева в Smalltalk - PullRequest
Новая
       1

Построение и запрос образца общего дерева в Smalltalk

1 голос
/ 19 августа 2011

Используя пакет BTree в SqueakSource (или любой другой, который вы можете знать) и учитывая следующее дерево 

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

Я пытался написать следующее, но безуспешно:

  • Построй дерево
  • Дано Node23 ответом своим прямым детям
  • Учитывая Node2, ответьте всем своим детям
  • Учитывая любой узел, ответьте его родителю
  • Собери всех детей

Это НЕ домашнее задание, причина, по которой я прошу базовый пример, заключается в том, что в случае BTree документация почти отсутствует, а тесты недостаточно хороши для определения базового использования, на самом деле примеры смешиваются с утверждениями и используя удобные методы.

Ответы [ 2 ]

3 голосов
/ 24 августа 2011

Если вас не очень интересует скорость выполнения, для этой цели в SqueakSource имеется документально оформленный пакет http://www.squeaksource.com/TreeLW.html, который изначально был выпущен для VisualWorks.

Один класс, который вы можете использовать дляПостроение вашего дерева - это 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.
3 голосов
/ 19 августа 2011

A B-Tree - это отсортированная структура данных, связывающая ключи со значениями.B-деревья позволяют обрабатывать огромное количество данных и гарантировать поиск, вставку и удаление в логарифмическом времени. BTree Package на SqueakSource следует протоколу Smalltalk Dictionary:

  • at: и at:ifAbsent: используются для поиска значений, заданных ключом,
  • at:put: используется для вставки пары ключ-значение, а
  • removeKey: используется для удаления ключа.

Кроме того, все функции итератора, которые вы знаете изDictionary поддерживаются (do:, keysDo:, valuesDo:, keysAndValuesDo:, ...);а также еще несколько для перебора диапазонов ключей (from:do:, from:to:do:, upTo:do:, ...).Обычно вам не нужны коллекции B-Tree в коде приложения, если только у вас нет проблем с производительностью встроенного класса Dictionary.

Мне кажется, что вы пытаетесь изменить внутреннюю работуB-дерево.Вы не должны этого делать, класс BTree автоматически реорганизуется, чтобы всегда обеспечивать наиболее эффективное представление (это в основном то, что проверяют тесты).Если вы хотите управлять своим собственным деревом, почему бы не создать свой собственный класс Node, содержащий OrderedCollection дочерних узлов и родительскую ссылку?

...