Методы поиска по дереву

Определение: Деревом называется конечное множество, состоящее из одного или более элементов, называемых узлами, таких, что:

• 1. между узлами имеет место отношение типа «исходный-порожденный» ;
• 2. есть только один узел, не имеющий исходного. Он называется корнем;
• 3. все узлы за исключением корня…

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

В задачах поиска предполагается, что все данные хранятся в памяти с определенной идентификацией и, говоря о доступе, имеют в виду прежде всего доступ к данным (называемым ключами), однозначно идентифицирующим связанные с ними совокупности данных.

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

Существуют два класса методов, реализующих доступ к данным по ключу:

методы поиска по дереву, методы хеширования.

Типы и структуры данных представляют собой фундамент, на котором строится вся современная технология программирования. Программирования в широком смысле, включая не только непосредственно написание и отладку программ, но и проектирование программных систем разной сложности; проектирование, реализацию и использование баз данных и информационных систем и т. д. Сегодня только большие любители обходятся без использования безтиповых языков программирования (например, языков ассемблера) или неструктурированных и/или нетипизированных хранилищ данных во внешней памяти. В этой части книги, не прибегая к излишним формализмам и теоретическим изыскам, мы приводим систематическое обсуждение основных типов и структур данных, применяемых в современных языках программирования, а также соответствующих концепций, используемых в распространенных реляционных и перспективных объектно-реляционных системах.