Полезное для программистов:

Фриланс
Новости
Статьи
   
Рубрики:


Деревья со случайным поиском (часть 2)

Поиск:
Конструкторы и деструкторы

    

Конструктор RandomizedsearchTree инициализирует новое дерево случайного поиска, представляемое изолированным головным узлом с минимальным приоритетом, равным -1,0:
[code==cpp]

template<class  T> RandomizedSearchTree<T>::RandomizedsearchTree (int (*с) (Т, Т) , int seed):
   cmp©
{
  win = root = new RandomizedNode<T> (NULL, seed); 
  root->_priority = -1.0;
}
[/code]

Деструктор удаляет дерево поиска:

Код

template<class T>
RandomizedSearchTree<T>::~RandomizedsearchTree (void)
{
  delete root;
}


Использование ленты


    

Компонентные функции next, prev, val, inorder, isFirst, isLast, isHead и is Empty определяются подобно их аналогам в классе
BraidedSearchTree :

Код

template<class Т> Т RandomizedSearchTree<T>::next (void)
{
  win = win->next();
  return win->val;
}

template<class T> Т RandomizedSearchTree<T>::prev (void)
{
  win = win->prev();
  return win->val;
}

template<class T> Т RandomizedSearchTree<T>::val (void)
{
  return win->val;
}

template<class T>
void RandomizedSearchTree<T>::inorder (void (*visit) (T) )
{
  RandomizedNode<T> *n = root->next();
  while (n != root) {
    (*visit) (n->val);
    n = n->next();
  }
}

template<class T>
bool RandomizedSearchTree<T>::isFirst (void)
{
  return (win == root->next() ) && (root != root->next ( ) );
}

template<class T>
bool RandomizedSearchTree<T>::isLast (void)
{
  return (win == root->prev() ) && (root != root->next() );
}

template<class T>
bool RandomizedSearchTree<T>::isHead (void)
{
  return (win == root);
}

template<class T>
bool RandomizedSearchTree<T>::isEmpty (void)
{
  return (root == root->next() );
}


Поиск


    

Компонентные функции find и findMin применяются также подобно их аналогам в классе BraidedSearchTree :

Код

template<class Т> Т RandomizedSearchTree<T>::find (T val)
{
  RandomizedNode<T> *n = root->rchild ( );
  while (n) {
    int result = (*cmp) (val, n->val);
    if (result < 0)
      n = n->lchild();
    else if (result > 0)
      n = n->rchild();
    else {
      win = n;
      return n->val;
    }
  }
  return NULL;
}

template<class T> Т RandomizedSearchTree<T>::findMin (void)
{
  win = root->next();
  return win->val;
}


Теперь мы введем новую операцию поиска locate. При обращении к функции locate с аргументом val возвращается наибольший элемент в дереве, который не больше, чем значение val. Если в дереве присутствует элемент со значением val, то возвращается значение val. Если такого значения нет, то возвращается значение меньше, чем val, если же в дереве и такого значения нет, то возвращается NULL.

Для выполнения этой операции будем отслеживать путь по дереву поиска до значения val. По мере продвижения вниз запоминается последний (самый нижний) узел b, в котором поворачиваем вправо — узел b является самым нижним узлом, обнаруженным на пути поиска, для которого правый потомок также лежит на пути поиска. Если в дереве находится значение val, то оно просто возвращается. В противном случае, если мы не найдем значение val в дереве — путь поиска завершается на внешнем узле — то возвращается элемент, запомненный в узле b.

Операция реализуется компонентной функцией locate, в которой окно перемещается на обнаруженный элемент и возвращается этот элемент.

Код

template<class Т> Т RandomizedSearchTree<T>::locate (T val)
{
  RandomizedNode<T> *b = root;
  RandomizedNode<T> *n = root->rchild();
  while (n) {
    int result = (*cmp) (val, n->val);
    if (result < 0)
      n = n->lchild();
    else if (result > 0) {
      b = n;
      n = n->rchild();
    } else {
      win = n;
      return win->val;
    }
  }
  win = b;
  return win->val;
}


Каким же образом получается правильный результат? Он вполне очевиден, если значение val точно находится в дереве. Но предположим, что такого значения в дереве нет, поэтому поиск значения val завершается на внешнем узле. Поскольку указатель n сигнализирует об окончании поиска, значение b показывает на наибольший элемент, который меньше всех остальных, содержащихся в поддереве с корнем в узле n. Легко видеть, что это условие сохраняется всегда. Каждый раз, когда в процессе поиска в узле n мы переходим на левую ветвь, условие продолжает сохраняться, поскольку каждый элемент в левом поддереве узла n меньше элемента в узле n. При переходе в узле n на правую ветвь присваивание b значения, равного n, восстанавливает условие, поскольку: (1) каждый элемент в правом поддереве узла n больше элемента, хранящегося в n и (2) элемент, хранящийся в узле n больше, чем элемент, на который указывало значение b до его изменения. И, наконец, когда n указывает на внешний узел, то b будет наибольшим элементом в дереве, который меньше любого другого элемента, который может легально заменить внешний узел, среди которых находится также и val.

Включение элементов

Для внесения нового элемента в дерево случайного поиска сначала найдем внешний узел, к которому он принадлежит (этап 1), а затем будем его поднимать по дереву по направлению к корню в соответствии с его приоритетом (этап 2). Компонентная функция insert заносит элемент val в текущее дерево случайного поиска и затем перемещает окно на этот элемент и возвращает указатель на этот элемент:
Код

template<class T> T RandomizedSearchTree<T>::insert (T val)
{
                                          // этап 1
  int result = 1;
  RandomizedNode<T> *p = root;
  RandomizedNode<T> *n = root->rchild();
  while (n) {
    p = n;
    result = (*cmp) (val, p->val);
    if (result < 0)
      n = p->lchild();
    else if (result > 0)
      n = p->rchild();
    else
      return NULL;
  }
  win = new RandomizedNode<T>(val);
  win->_parent = p;
  if (result < 0) {
    p->_lchild = win;
    p->prev()->Node::insert(win);
  } else {
    p->_rchild = win;
    p->Node::insert(win);
  }
                                          //  этап 2
  win->bubbleUp ();
  return val;
}


Удаление элементов


    

Компонентная функция remove удаляет элемент в окне и затем перемещает окно в предшествующую позицию. Компонентная функция removeMin (удаляет наименьший элемент и возвращает его. Если окно находилось на этом элементе, то оно перемещается в головную позицию:
Код


template<class T> void RandomizedSearchTree<T>::remove(void)
{
  if (win != root)
    _remove(win);
}

template<class T> Т RandomizedSearchTree<T>::removeMin(void)
{
  Т val = root->next()->val;
  if (root != root->next() )
    _remove(root->next());
  return val;
}


Обе эти функции основаны на внутренней компонентной функции _remove. Для удаления узла n функция _remove увеличивает приоритет узла n до 1.5 и затем опускает его вниз до тех пор, пока он не станет внешним узлом. Приоритет 1.5 превышает приоритет любого элемента в дереве, но меньше, чем приоритет внешних узлов (2.0). После этого функция удаляет узел n из дерева случайного поиска. Если окно было на узле, подлежащем удалению, то окно перемещается на предшествующую позицию. Алгоритм реализуется в виде функции _remove, которая удаляет узел n из екущего дерева поиска.

Код

template<class T>
void RandomizedSearchTree<T>::_remove(RandomizedNode<T> *n)
{
  n—>_priority = 1.5;
  n->bubbleDown();
  RandomizedNode<T> *p = n->parent();
  if (p->lchild() == n);
    p->_lchild = NULL;
  else
    p->_rchild = NULL;
  if (win == n)
    win = n->prev();
  n->Node::remove();
  delete n;
}


На рис. 3, если его анализировать от (г) до (а), показано удаление элемента 6 из самого правого дерева поиска, для которого приоритет был увеличен до 1.5. Процесс удаления обратен процессу внесения элемента 6 в дерево (а), поскольку правая и левая ротации взаимно обратны.

Для удобства введем вторую компонентную функцию remove, которая, при передаче ей элемента, удаляет его из дерева случайного поиска. Если окно находится на элементе, подлежащем удалению, то окно перемещаетвя в предыдущую позицию, в противном случае окно не перемещается:

Код

template<class Т> Т RandomizedSearchTree<T>::remove (T val)
{
  Т v = find (val);
  if (v) {
    remove();
    return v;
  }
  return NULL;
}



Ожидаемые характеристики

В дереве случайного поиска размера n средняя глубина узла равна O(log n), Это справедливо независимо от изменений в порядке ввода элементов или положения в дереве, куда эти элементы вводятся или из которого удаляются. Поскольку выполнение каждой из операций ввода и удаления insert, remove и removeMin, а также операций поиска find и findMin занимает время, пропорциональное глубине обрабатываемого элемента, то в среднем затраты времени равны 0(log n).

Почему же средняя длина поиска равна O(log n) ? Чтобы ответить на этот вопрос, найдем ожидаемую глубину элемента в дереве случайного поиска Т. Переименуем элементы в дереве поиска Т по увеличивающемуся приоритету как x1, x2,..., xn. Для определения ожидаемой глубины элемента зд предположим, что дерево Т строилось путем занесения элементов в указанном порядке в первоначально пустое дерево случайного поиска Т'. По мере ввода каждого элемента xi определим вероятность того, что оно лежит на пути поиска элемента хk в дереве Т.

Прежде, чем продолжать дальше, обсудим три момента. Во-первых, процесс имеет место в дереве Т, поскольку дерево случайного поиска полностью определяется его элементами и их приоритетами (если даже некоторые значения приоритетов встречаются более одного раза, то элементы все равно могут быть упорядочены таким образом, что дерево Т существует). Во-вторых, вследствие принятого порядка включения элементов не требуется никаких операций ротаций. В-третьих, наш анализ требует, чтобы были внеcены только элементы х1,..., xk1, поскольку элемент хk всегда обязательно содится в конце своего пути поиска и внесение элементов хk+1,..., xn не может увеличить глубину элемента xk, поскольку ни один из этих элементов не может быть предшественником элемента xk.

Начнем с пустого двоичного дерева Т', представленного единственным аешним узлом. Для внесения элемента х1 в Т' заменим внешний узел на 1. Поскольку элемент x1 находится в корне дерева Т', то он будет предшественником любого элемента xk, так что вероятность того, что элемент x1 лежит на пути поиска элемента xk равна единице. Внесем теперь в дерево элемент x2. Очевидно, что элемент x2 может заменить любой из двух внешних узлов, которые являются последователями элемента х1, так что только одна из этих двух позиций приведет к тому, что элемент x2 будет лежать на пути поиска элемента xk. Поэтому вероятность того, что элемент x2 будет лежать на этом пути поиска, равна 1/2. В общем случае, при вводе в дерево Т' элемента xi, где i изменяется от 1 до k, элемент xi с равной вероятностью замещает один из i внешних узлов. Поскольку только одна из этих позиций приводит к тому, что элемент хi будет лежать на пути поиска цемента хk, то вероятность того, что элемент xi лежит на пути поиска эле-ента xk будет равна 1/i. Из этого следует, что ожидаемая глубина элемента равна 1 + СУММА(1/i), i=1..k-1, что соответствует O(log n) для k <= n.






Просмотров: 2617

 

 

Новые статьи:


Популярные:
  1. Как сделать цикличным проигрывание MIDI-файла?
  2. Создание AVI файла из рисунков
  3. Как устройство "отключить в данной конфигурации"?
  4. Kто в данный момент присоединен через Сеть?
  5. Как узнать количество доступной памяти?
  6. Как реализовать в RichEdit разноцветный текст?
  7. Как скрыть свое приложение от ProcessViewer
  8. Как программно нажать/скрыть/показ кнопку "Start"?
  9. Модуль работы с ресурсами в PE файлах
10. Функции вызова диалоговых окон выбора
11. Проверка граматики средствами Word'а из Delphi.
12. Модуль для упрощенного вызова сообщений
13. Функции для записи и чтение своих данных в, ЕХЕ- файле
14. Рекурсивный просмотр директорий
15. Network Traffic Monitor
16. Разные модули
17. Универсальная функция для обращения к любым экспортируем функциям DLL
18. Библиотека от VladS
19. Протектор для UPX'а
20. Еще об ICQ, сообщения по контакт листу?
21. Использование открытых интерфейсов
22. Теория и практика использования RTTI
23. Работа с TApplication
24. Примеры использования Drag and Drop для различных визуальных компонентов
25. Что такое порт? Правила для работы с портами
26. Симфония на клавиатуре
27. Загрузка DLL
28. Исправление автоинкремента
29. Взаимодействие с чужими окнами
30. Проверить дубляжи в столбце


 

 

 
 
На главную