Типы двоичных деревьев поиска

января 23, 2020

Существует много типов двоичных деревьев поиска. Деревья AVL и красно-черные деревья являются формами самобалансирующихся двоичных деревьев поиска. Splay дерево - это двоичное дерево поиска, которое автоматически перемещает часто используемые элементы ближе к корню. В treap (куче дерева) каждый узел также имеет (случайно выбранный) приоритет, а родительский узел имеет более высокий приоритет, чем его дочерние элементы. Деревья танго - это деревья, оптимизированные для быстрого поиска. T-деревья - это двоичные деревья поиска, оптимизированные для сокращения объема памяти, широко используемые для баз данных в памяти.

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

Сравнение производительности

D. A. Heger (2004) представил сравнение производительности двоичных деревьев поиска. Было обнаружено, что Treap имеет лучшую среднюю производительность, в то время как красно-черное дерево имеет наименьшее количество вариаций производительности.

Оптимальные двоичные деревья поиска

Вращения деревьев - это очень распространенные внутренние операции в двоичных деревьях для поддержания идеального или почти идеального внутреннего баланса в дереве.

Если мы не планируем модифицировать дерево поиска и точно знаем, как часто будет осуществляться доступ к каждому элементу, мы можем построить оптимальное двоичное дерево поиска, которое представляет собой дерево поиска, в котором средняя стоимость поиска элемента (ожидаемая стоимость поиска) сведена к минимуму.

Даже если у нас есть только оценки стоимости поиска, такая система может значительно ускорить поиск в среднем. Например, если у нас есть BST английских слов, используемых в средстве проверки правописания, мы можем сбалансировать дерево на основе частоты слов в текстовых корпусах, поместив такие слова, как the ближе к корню, а слова, подобные agerasia, около листьев. Такое дерево можно сравнить с деревьями Хаффмана, которые также стремятся разместить часто используемые элементы рядом с корнем, чтобы получить плотное кодирование информации; однако деревья Хаффмана хранят элементы данных только в виде листьев, и эти элементы не нужно упорядочивать.

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

Алфавитные деревья - это деревья Хаффмана с дополнительным ограничением порядка или, что то же самое, деревья поиска с модификацией, согласно которой все элементы хранятся в листьях. Существуют более быстрые алгоритмы для оптимальных буквенных двоичных деревьев (OABT).

Поиск по этому блогу

Alex tools