Cтраница 2
Это patricia - дерево, построенное в результате вставки примерно 200 случайных ключей, эквивалентно trie - дереву, приведенному на рис. 15.9, при условии удаления из последнего однонаправленных ветвей. Результирующее дерево является почти идеально сбалансированным. [16]
Шаг 3 является наименее обоснованной частью вышеприведенной процедуры. Результирующее дерево может сильно зависеть от способа, которым вводится расстояние между классами. Эта проблема в настоящее время является предметом исследований в теории иерархической классификации. [17]
Легко видеть, что жадный алгоритм конечен. Минимальность результирующего дерева Т не так очевидна, но это можно доказать следующим образом. Предположим, что Т не является минимумом остовных деревьев. Ясно, что С 1, и так как Т не является минимумом остовных деревьев, то и. [18]
Например, для построения BST-дерева, состоящего из 100000 узлов, с использованием вставки с расширением всегда требуется менее 5 миллионов сравнений. Это не гарантирует, что результирующее дерево поиска будет хорошо сбалансировано и что каждая операция будет эффективной, но тем не менее обеспечивает весьма значительную гарантию в отношении общего времени выполнения; на практике фактическое время выполнения, скорее всего, откажется еще меньшей. [19]
В результате объедим ел и н получаем сортирующее дерево, содсржл - ] [ iee в два раза большее число уэ. Корн иой у а ел с большим значением ключа ста иприте л корнем результирующего дерева ( другой н сходны к корень при этом становится JJOTOMKOM результирующего дерева а его ictioc лодлерево станонится правым поллсрс-другого корневого у: 1ла, Если задано cm зное прелставление деревьев, то операция объединения выполняется За постоянное йре. [20]
Пусть L ( q -) - литера, приписанная ребру а. Удалим из дерева Т4 литеры L ( a), If i q, и обозначим результирующее дерево через Ть. [21]
В результате объедим ел и н получаем сортирующее дерево, содсржл - ] [ iee в два раза большее число уэ. Корн иой у а ел с большим значением ключа ста иприте л корнем результирующего дерева ( другой н сходны к корень при этом становится JJOTOMKOM результирующего дерева а его ictioc лодлерево станонится правым поллсрс-другого корневого у: 1ла, Если задано cm зное прелставление деревьев, то операция объединения выполняется За постоянное йре. [22]
На втором шаге используется тот факт, что каждый вложенный объект должен появляться в плоском списке раньше, чем все его окружения. А и В, если А впереди В, то объект В либо окружается объектом А, либо параллелен ему. Следовательно, процедура построения результирующего дерева может выглядеть следующим образом. [23]
Тривиальной операцией, на которой базируются все биномиальные алгоритмы, является объединение двух сортирующих деревьев степени 2, состоящих из одинакового числа узлов. В результате объединения получаем сортирующее дерево, содержащее в два раза большее число узлов, которое, как показано на рис. 9.16, совсем нетрудно построить. Корневой узел с большим значением ключа становится корнем результирующего дерева ( другой исходный корень при этом становится потомком корня результирующего дерева), а его левое поддерево становится правым поддеревом другого корневого узла. Если задано связное представление деревьев, то операция объединения выполняется за постоянное время: мы всего лишь устанавливаем две связи в вершине. [24]
Тривиальной операцией, на которой базируются все биномиальные алгоритмы, является объединение двух сортирующих деревьев степени 2, состоящих из одинакового числа узлов. В результате объединения получаем сортирующее дерево, содержащее в два раза большее число узлов, которое, как показано на рис. 9.16, совсем нетрудно построить. Корневой узел с большим значением ключа становится корнем результирующего дерева ( другой исходный корень при этом становится потомком корня результирующего дерева), а его левое поддерево становится правым поддеревом другого корневого узла. Если задано связное представление деревьев, то операция объединения выполняется за постоянное время: мы всего лишь устанавливаем две связи в вершине. [25]
Первое, что мы должны уметь делать, - это сравнивать два образца с целью определения того, что один из них является частным случаем ( специализацией) другого. Для этого мы определим функцию порядка 3 так, что Pi 3 PJ тогда и только тогда, когда Sj э Si. Далее мы модифицируем структуру листьев, позволив им содержать список номеров уравнений, а не только один такой номер. Причина такой модификации состоит в том, что теперь нам, возможно, придется сливать два листа, и если окажется, что ни один из их образцов не является специализацией другого, то мы должны поместить в результирующую вершину все номера уравнений сливаемых вершин, ожидая, что в дальнейшем они будут заменены номером уравнения, имеющего более специфичный образец. Если в конце процесса слияния какой-либо лист результирующего дерева сопоставления будет содержать несколько номеров уравнений, тогда набор образцов является неоднозначным. [26]