Cтраница 2
Наконец, при использовании методов хеширования нужно свято верить в теорию вероятностей, ибо они эффективны лишь в среднем, а худший случай просто ужасен. Поэтому они не всегда подходят для работы в реальном масштабе времени, например, для управления движением транспорта, поскольку на карту поставлены человеческие жизни. Алгоритмы, использующие сбалансированные деревья, гораздо безопаснее, ведь они имеют гарантированную верхнюю границу времени поиска. [16]
Посмотрим, что включает в себя понятие сбалансированного дерева. Ясно, что полностью сбалансированные деревья являются частным случаем сбалансированных деревьев и среди сбалансированных деревьев они являются деревьями с минимальной высотой при заданном числе узлов. Посмотрим, что представляют собой сбалансированные деревья максимальной высоты. [17]
Структурно эти деревья идентичны деревьям, показанным на рис. 2.5. В соответствии с определением только четыре структуры из этих 14 ( д, е, н, п) являются полностью сбалансированными бинарными деревьями. Эти примеры убедительно свидетельствуют о том, что полностью сбалансированные деревья крайне редки даже в случае бинарных деревьев. [18]
Можно также надеяться, что в среднем время поиска также будет связано с количеством узлов логарифмической зависимостью, поскольку первый вставляемый элемент становится корнем дерева. В действительно произвольной ситуации корнем может быть любой ключ, и поэтому полностью сбалансированные деревья встречаются исключительно редко, соответственно, без особых усилий не удастся сохранять дерево полностью сбалансированным после каждой вставки. [19]
Обобщением двоичных деревьев является сбалансированное ( или регулярное) дерево. В сбалансированном дереве количество исходящих узлов из любого произвольного узла может быть больше двух, однако обязательно из каждого произвольного узла ( кроме концевого) исходит одинаковое количество порожденных узлов. Процесс включения новых узлов в сбалансированное дерево выполняется сверху вниз, а на каждом уровне дерева - слева направо. Сбалансированные деревья используются для построения индексов файлов. [20]
Сложность операции балансировки предполагает, что сбалансированные деревья следует использовать только тогда, когда поиск информации происходит значительно чаще, чем ее включение. Это утверждение особенно верно, поскольку вершины дерева поиска для экономии памяти обычно хранятся в виде плотно упакованных записей. Поэтому решающим фактором, определяющим эффективность операции балансировки, часто бывают доступность показателя балансировки и простота его изменения, ведь для его представления нужно всего два разряда. Опыт показывает, что сбалансированные деревья сразу же теряют почти всю свою привлекательность, как только речь заходит о плотной упаковке для записей. И действительно, простой и очевидный алгоритм включения в дерево превзойти трудно. [21]
На рис. 13.13 представлено посроение 2 - 3 - 4-дерева для тестового набора ключей. В отличие от стандартных BST-деревьев, которые разрастаются вниз от вершины, эти деревья разрастаются вверх от нижней части. Поскольку 4-узлы разделяются на пути от вершины вниз, деревья называются нисходящими 2 - 3 - 4-деревьями. Этот алгоритм важен, поскольку он создает практически идеально сбалансированные деревья поиска, хотя в процессе прохождения по дереву выполняются всего лишь несколько локальных преобразований. [22]