Поддеревья

Cтраница 3

После сжатия этого дерева, сворачивая, где возможно, поддеревья в один лист, мы получим дерево, изображенное на рис. 13.8. Такое же дерево будет построено алгоритмом ID3 на этих восьми обучающих примерах. [31]

В каждом из Т / 1, л можно также выделить поддеревья, для которых / - я вершина будет корнем. [32]

Потом формируется множество вершин в дереве Т, у которых все поддеревья уже разрезаны. [33]

Несбалансированность, возникшая из-за включения.| Восстановление сбалансированности. [34]

Схематично эти случаи представлены на рис. 4.32, где прямоугольниками обозначены поддеревья, причем добавленная при включении высота отмечена перечеркиванием. Простые преобразования сразу же восстанавливают желанную сбалансированность. Их результат приведен на рис. 4.33. Обратите внимание, что допускаются лишь перемещения в вертикальном направлении, в то время как относительное горизонтальное расположение показанных вершин и поддеревьев должно оставаться без изменения. [35]

Поиск начинается с кор -: н дерева и распространяется на поддеревья. [36]

При работе с деревом принято использовать стек для временного хранения указателей на поддеревья, которые еще не были просмотрены. Метод в основном заключается в следующем: начиная с корня ( головы главного списка), главный список просматривается до тех пор, пока не встретится точка ветвления; выбирается одно поддерево для продолжения, а указатель на другое помещается в стек. Когда достигается конец поддерева, берется указатель с вершины стека и просматривается поддерево, на которое он указывает. Вначале стек содержит только указатель на корень дерева. Постройте алгоритм для обработки дерева таким методом в предположении, что дерево имеет представление, изображенное на рис. 3.18, а стек представляется последовательно. [37]

На рис. 17.1 экземпляры сегментов типа С, D и F определяют примитивные поддеревья, так как это сегменты самого низкого уровня. Сегменты Е1 и ЕЗ также определяют примитивные поддеревья. Для оценки памяти удобно рассматривать поддерево как совокупность одного экземпляра некоторого сегмента и всех поддеревьев сегментов, непосредственно подчиненных данному сегменту. [38]

Из прямого псрядка нам известен корень, из обратного - левое и правое поддеревья; известно также расположение узлов этих поддеревьев в прямом и обратном порядках. [39]

Каждый узел должен содержать один ключ и два указателя на левое и правое поддеревья. [40]

Некоторые части дерева секвенций D, сами являющиеся деревьями секвенций, будем называть поддеревья ми дерева D. Поддеревья D находятся во взаимно однозначном соответствии с вхождениями секвенций в дерево D. Если D состоит из единственной секвенции, то само D и является единственным своим поддеревом. [41]

Обратный обход ( снизу вверх), при котором мы посещаем левое и правое поддеревья, а затем узел. [42]

Дерево поиска с указанием частот обращения. [43]

Однако оптимальные деревья обладают одним важным свойством, которое помогает их обнаруживать: все их поддеревья тоже оптимальны. Если, например, дерево на рис, 4.37 оптимально, то поддерево с ключами k3 и 1м, как показано, также оптимально. Такая особенность предполагает алгоритм, который систематически находит все большие и большие деревья, начиная с отдельных вершин как наименьших возможных поддеревьев. [44]

В этом случае дерево игры имеет вид, представленный на рис. 6, где треугольниками изображены поддеревья, корнями которых являются вершины i, Ts... [45]

Страницы: 1 2 3 4 5