Алгоритмы и структуры данных на С++. Аксёнова Е.А - 74 стр.

74                                                   Глава 6. Поиск


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


                     6.2. Бинарный поиск

  Этот метод используется при поиске в упорядоченной таблице.
Пусть K1 ≤ K2 ≤ ... ≤ Kn . Нужно найти в таблице ключ K.

     Алгоритм бинарного поиска:

      B1: l = 1; u = n;
      B2: если u < l, то НЕУДАЧА;
           иначе i = b u+l
                        2 c;
      B3: если K > Ki , то перейти к шагу B4;
           если K = Ki , то УДАЧА;
           u = i − 1; перейти к шагу B2;
      B4: l = i + 1; перейти к шагу B2;
     Среднее время вычисляется по формуле T = C · log2 n.


              6.3. Поиск по бинарному дереву

   Бинарным деревом поиска называется такое бинарное дерево клю-
чей, в котором все ключи левого поддерева каждого узла меньше клю-
ча данного узла, а правого – больше (рис. 6.1).
   Пусть узел бинарного дерева поиска состоит из ключа, информа-
ционной части (массива символов) и указателей на левое и правое
поддеревья:

struct node{int key; char info[20]; node *llink; node *rlink;}.

   Следующая функция осуществляет поиск ключа K в дереве, на
корень которого указывает указатель t. Если ключа в данном дереве
нет, то он вставляется в дерево поиска.