Ключевые термины. Деревья цифрового (поразрядного) поиска

Деревья цифрового (поразрядного) поиска

Методы цифрового поиска достаточно громоздки и плохо иллюстрируются. Рассмотрим бинарное дерево цифрового поиска. Как и в деревьях, рассмотренных выше, в каждой вершине такого дерева хранится полный ключ, но переход по левой или правой ветви происходит не путем сравнения ключа-эталона со значением ключа, хранящегося в вершине, а на основе значения очередного бита аргумента. Реализация цифрового поиска происходит поразрядно (побитово).

Поиск начинается от корня дерева. Если содержащийся в корневой вершине ключ не совпадает с аргументом поиска, то анализируется самый левый бит аргумента. Если он равен 0, происходит переход по левой ветви, если 1 – по правой. Если не обнаруживается совпадение ключа с аргументом поиска, то анализируется следующий бит аргумента и т.д. Поиск завершается, когда будут проверены все биты аргумента либо встретится вершина с отсутствующей левой или правой ссылкой.

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

Двоичное (бинарное) дерево – это иерархическая структура, в которой каждый узел имеет не более двух потомков.

Идеально сбалансированное дерево – этодерево, у которого для каждой вершины выполняется требование: число вершин в левом и правом поддеревьях различается не более чем на 1.

Ключ поиска – это поле, по значению которого происходит поиск.

Оптимальное бинарное дерево поиска – это бинарное дерево поиска, построенное в расчете на обеспечение максимальной производительности при заданном распределении вероятностей поиска требуемых данных.

Поиск – это процесс нахождения конкретной информации в ранее созданном множестве данных.

Сбалансированное по АВЛ дерево – это дерево, для каждой вершины которого выполняется требование: высота левого и правого поддеревьев различаются не более, чем на 1.

Случайные деревья поиска – это упорядоченные бинарные деревья поиска, при создании которых элементы вставляются в случайном порядке.

Упорядоченное двоичное дерево – это двоичное дерево, в котором для любой его вершины x справедливы свойства: все элементы в левом поддереве меньше элемента, хранимого в x; все элементы в правом поддереве больше элемента, хранимого в x; все элементы дерева различны.

Частично упорядоченное бинарное дерево – это упорядоченное бинарное дерево, в котором встречаются одинаковые элементы.

Дата добавления: 2014-01-04