Краткие итоги. 1.Поиск данных предполагает использование соответствующих алгоритмов в зависимости от ряда факторов: способ представления данных

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

2. Двоичные деревья представляют собой иерархическую структуру, в которой каждый узел имеет не более двух потомков. Поиск на двоичных деревьях не дает выигрыша по времени по сравнению с линейными структурами.

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

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

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

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

7. В деревьях цифрового поиска осуществляется поразрядное сравнение ключей.

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