Cтраница 1
Алгоритм вставки можно использовать для создания двоичного дерева поиска, начиная с нулевого дерева и последовательно добавляя новые данные в удобном для нас порядке. [1]
Алгоритм вставки вставляет новые вершины ( ключи вставок) в двоичное дерево поиска, создавая при этом новую вершину слева или справа от уже существующей. [2]
Требуется разработать алгоритмы вставки ключа в структуру данных и поиска в структуре данных с целью определения, был ли вставлен заданный ключ. [3]
Программа 15.5 содержит реализацию алгоритма вставки н piitricia - дсрсво. [4]
Программа 15.5 содержит реализацию алгоритма вставки в patricia - дерево. Код вытекает непосредственно из описания, приведенного в предыдущем абзаце, с учетом одного дополнительного обстоятельства, что выполняется просмотр связей с узлами, содержащими индексы разрядов, длина которых не превышает индекс текущего разряда и которые служат связями с внешними узлами. Код вставки просто проверяет это свойство связей, но не должен перемещать ключи или связи. На первый взгляд направленные вверх связи в patricia - деревьях кажутся странными, но выбор связей, которые должны использоваться при вставке каждого узла, удивительно прост. Суть же заключается в том, что использование одного типа узла вместо двух существенно упрощает код. [5]
Поскольку R К, мы применяем алгоритм вставки к правому поддереву вершины К. [6]
А теперь давайте рассмотрим альтернативный подход к разработке алгоритма с использованием сбалансированного дерева, заключающийся в полном игнорировании абстракции 2 - 3 - 4-дерева и формулировании алгоритма вставки, который сохраняет определяющее свойство сбалансированных RB-деревьев бинарного поиска за счет применения ротаций. Например, использование восходящего алгоритма соответствует присоединению нового узла в нижней части пути поиска с помощью R-связи, затем продвижению вверх по пути поиска с выполнением ротаций или изменений цвета, как это делалось в случаях, представленных на рис. 13.17, с целью разбиения любой встретившейся пары последовательных R-связей. Основные операции не отличаются от выполняемых в программе 13.6 и в ее восходящем аналоге, но при этом имеются незначительные различия, поскольку 3-узлы могут быть ориентированы в любом направлении, операции могут выполняться в ином порядке и различные решения в отношении различных ротаций могут приниматься с равным успехом. [7]
Алгоритм поиска для TST-деревьев существования столь прост, что читатели вполне могли бы описать его самостоятельно. Алгоритм вставки несколько сложнее, но прямо отражает вставку в trie - деревьях существования. Для выполнения поиска первый символ в ключе сравнивается с символом в корне. Если он меньше, поиск продолжается по левой связи, если больше - по правой, а если равен, поиск выполняется вдоль средней связи и осуществляется переход к следующему символу ключа. В любом случае алгоритм применяется рекурсивно. Поиск завершается промахом, если встречается нулевая связь или конец искомого ключа встречается раньше, чем NULLdigit. Поиск завершается попаданием, если пересекается средняя связь в узле, символ которого - NULLdigit. Для вставки нового ключа выполняется поиск, а затем добавляются новые узлы для символов в заключительной части ключа, как это имело место в trie - деревьях. [8]
Удаление двоичного дерева) В этом упражнении мы обсудим удаление элементов данных из двоичного дерева поиска. Алгоритм удаления не так прост, как алгоритм вставки. При удалении элемента данных возможен один из трех случаев: элемент данных содержится в листе ( т.е. узле, не имеющем потомков), в узле, имеющем одного потомка, или в узле, имеющем двух потомков. [9]
Удаление из двоичного дерева) В этом упражнении мы обсудим удаление элементов из дерева двоичного поиска. Алгоритм удаления не является таким простым, как алгоритм вставки. При удалении элемента могут быть три случая: элемент находится в концевом узле дерева ( не имеет узлов-потомков); элемент находится в узле, в которого есть один узел-потомок; элемент находится в узле, у которого имеется два узла-потомка. [10]
Поскольку 4-узлы не играют никакой специальной роли в алгоритме с использованием 2 - 3 - 4-деревьев, сбалансированные деревья можно строить по существу так же, используя только 2-узлы и 3-узлы. Построенные таким образом деревья называют 2 - 3-деревьями. Такие деревья были исследованы Хопкрофтом ( Hopcroft) в 1970 г. 2 - 3-деревья не обладают достаточной гибкостью, чтобы можно было построить удобный алгоритм нисходящей вставки. Кроме того, RB-структура может упростить реализа-цию % но восходящие 2 - 3-деревья не обеспечивают особых преимуществ по сравнению с восходящими 2 - 3 - 4-деревьями, поскольку для поддержания баланса по-прежнему требуются одиночные и двойные ротации. Восходящие 2 - 3 - 4-деревья несколько лучше сбалансированы и обладают тем преимуществом, что для каждой вставки требуется максимум одна ротация. [11]
Для вставки ключа в trie - дерево вначале, как обычно, выполняется поиск. Если поиск завершается на нулевой связи, она, как обычно, заменяется связью с новым содержащим ключ листом. Но если поиск заканчивается в листе, необходимо продолжить перемещение вниз по дереву, добавляя внутренний узел для каждого разряда, значение которого для искомого и найденного ключей совпадает; этот процесс должен завершиться тем, что оба ключа в листьях, являющихся дочерними узлами внутреннего узла, будут соответствовать первому разряду, в котором они отличаются. Пример поиска и вставки в trie - дереве показан на рис. 15.6; процесс построения trie - дерева за счет вставки ключей в первоначально пустое дерево представлен на рис. 15.7. Программа 15.3 представляет собой полную реализацию алгоритма вставки. [12]