На этом шаге мы рассмотрим такое дерево.

Определение (по [1, с. 492]).

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

Определение (по [1, с. 514]).

Самоорганизующееся (самонастраивающееся, самоустанавливающееся) бинарное дерево поиска (от англ. self-ajust) - это бинарное дерево поиска, предназначенное для сохранения часто посещаемых узлов в окрестности вершины дерева.

    Самоорганизующееся BST-дерево получается в результате изменения функции для рекурсивного поиска элемента в BST-дереве таким образом, чтобы она помещала найденный узел в корень дерева.

    Приведем пример такого дерева.

   ; Демонстрация функции, моделирующей операцию "построение
   ; самоорганизующегося бинарного дерева поиска".
   ;  Запуск функции на выполнение:
   ;
   ;  >muLISP85 SplTree.sys 201-05.LSP
   ;
   ; ; Автор: И.А.Кудрявцева (04.07.2006)
   ; ------------------------------------
   (DEFUN TEST (LAMBDA NIL
      (PRINT "Построение числового бинарного дерева поиска:")
      (SETQ Tree NIL)
      (LOOP
         (PRIN1 "Введите очередной элемент дерева (окончание !): ")
         (SETQ X (READ))
         ( (EQ X '!) )
         (PRINT (SETQ Tree (AddInRoot X Tree)))
         (PRINT "Числовое бинарное дерево поиска:") 
         (PRINT (OutTree Tree 0))
      )  
   ))
   (RDS)

    На следующем шаге мы рассмотрим скошенные деревья.

Предыдущий шаг Содержание Следующий шаг