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

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


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

Поиск:
При вводе элемента в дерево случайного поиска этому элементу приcваивается приоритет — некоторое вещественное число с равномерным распределением в диапазоне [0, 1] (вероятность выбора любого числа в заданном диапазоне одинакова). Приоритеты элементов в дереве случайного поиска определяют их положение в дереве в соответствии с правилом: приоритет каждого элемента в дереве не должен быть более приоритета любого из его последователей. Правило двоичного дерева поиска также остается справедливым: для каждого элемента х элементы в левом поддереве х будут меньше, чем х, а в правом поддереве — больше, чем х. На рис. 1 приведен пример такого дерева случайного поиска.
user posted image
Рис. 1: Дерево случайного поиска. Приоритеты каждого элемента указаны в виде нижнего индекса

Как же осуществить ввод некоторого элемента х в дерево случайного поиска? Он выполняется в два этапа. На первом этапе будем учитывать приоритет и введем элемент х уже известным нам способом: проследуем по пути поиска элемента я от корня вниз до внешнего узла, которому принадлежит х, и затем заменим внешний узел новым внутренним узлом, содержащим х. На втором этапе мы изменим форму дерева в соответствии с приоритетами элементов. Сначала случайным образом зададим приоритет для х. В простейшем случае, приоритет х может быть больше и равен приоритету предка, тогда задача оказывается решенной. В противном случае, если приоритет х оказывается меньше приоритета его предка у, то правило приоритета для у оказывается нарушенным. Предположим, что элемент х оказался левым наследником для у. В этом случае применим правую ротацию для элемента у, переместив элемент х в дереве на один уровень выше (рис. 2). Теперь правило приоритета может оказаться нарушенным для нового предка элемента х. Если это так, то применим ротацию для предка — правую ротацию, если х является левым потомком, или левую ротацию, если х является правым потомком, переместив таким образом элемент х еще на один уровень вверх. Такой подъем элемента х будем осуществлять до тех пор, пока он не станет либо корневым, либо его приоритет будет не меньше, чем у его предка.
user posted image
Рис. 2: Ротация
user posted image
Рис. 3: Внесение элемента 6 в дерево случайного поиска: (а) и (б)—левая ротация элемента 5; (б) и (в) — правая ротация элемента 7; (в) и (г) - левая ротация элемента 4


На рис. 3 показан процесс внесения элемента. На этой схеме показано, как элемент 6 заменяет соответствующий внешний узел, а затем поднимается вверх в соответствии с его приоритетом (.10) и приоритетами его текущих предков.

Определим теперь соответствующие классы. Несколько позже рассмотрим, как удалить элемент из дерева случайного поиска. Реализация использует классы из описания связанного дерева поиска.

Класс RandomizedNode


    

Узлы в дереве случайного поиска являются объектами шаблона класса RandomizedNode:

Код

template<class T>
class RandomizedNode : public BraidedNode<T> {
protected :
  RandomizedNode *_parent;
  double _priority;
  void rotateRight (void);
  void rotateLeft (void);
  void bubbleUp (void);
  void bubbleDown (void);
public :
  RandomizedNode ( Т v, int seed = -1);
  RandomizedNode *lchild (void);
  RandomizedNode *rchild(void);
  RandomizedNode *next (void);
  RandomizedNode *prev{ void);
  RandomizedNode *parent (void);
  double priority (void);
  friend class RandomizedSearchTree<T>;
};


Класс RandomizedNode наследует пять элементов данных из его базового класса: val, _lchild, _rchild, _prev и _next. В класс включены два дополнительных элемента данных: _parent, который указывает на узел-предок текущего узла, и _priority, приоритет текущего узла.

Конструктор присваивает новому узлу RandomizedNode случайное значение приоритета, используя стандартную функцию языка C++ rand, которая генерирует случайное число в пределах от 0 до RAND_MAX :

Код

template<class T>
RandomizedNode<T>::RandomizedNode(T v, int seed) :
  BraidedNode<T>(v)
{
  if (seed != -1) srand(seed);
  priority = (rand() % 32767) / 32767.0;
  _parent = NULL;
}


Наибольший интерес представляют компонентные функции класса RandomizedNode, объявленные как private (собственные). Первые две выполняют два вида ротации — правую и левую. Правая ротация является локальной операцией, которая изменяет форму дерева поиска, оставляя неизменным порядок следования элементов — до и после выполнения операции предшественник и последователь для каждого узла остаются без изменения. Правая ротация для узла у приводит к повороту поддерева с корнем в узле у вокруг связи от узла у к его левому потомку х (рис. 2). Операция выполняется путем изменения небольшого числа связей: связь с левым потомком узла у заменяется на связь с поддеревом T2, связь с правым потомком узла х заменяется на связь с узлом у, а связь с узлом у (от его предка) заменяется на связь с узлом х.

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

Код

template<class T> void RandomizedNode<T>::rotateRight(void)
{
  RandomizedNode<T> *y = this;
  RandomizedNode<T> *x = y->lchild();
  RandomizedNode<T> *p = y->parent();
  y->_lchild = x->rchild();
  if (y->lchild() != NULL)
    y->lchild()->_parent = y;
  if (p->rchild() == y)
    p->_rchild = x;
  else
    p->_lchild = x; 
  x->_parent = p;
  x->_rchild = y;
  y->_parent = x;
}


Действие компонентной функции rotateLeft для левой ротации также показано на рис. 2 и она определяется симметрично:

Код

template<class T> void RandomizedNode<T>::rotateLeft(void)
{
  RandomizedNode<T> *х = this;
  RandomizedNode<T> *y = x->rchild();
  RandomizedNode<T> *p = x->parent();
  x->_rchild = y->lchild();
  if (x->rchild() != NULL)
    x->_rchild()->_parent = x;
  if (p->lchild() == x)
    p->_lchild = y;
  else
    p->_rchild = y;
  y->_parent = p;
  y->_lchild = x;
  x->_parent = y;
}


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

Код

template<class T> void RandomizedNode<T>::bubbleUp(void)
{
  RandomizedNode<T> *p = parent();
  if (priority() < p->priority() ) {
    if (p->lchild() == this)
      p->rotateRight();
     else
       p->rotateLeft();
     bubbleUp();
  }
}


Компонентная функция bubbleDown переносит текущий узел вниз по направлению к внешним узлам дерева путем многократных ротаций до тех пор, пока приоритет текущего узла не станет меньше или равным приоритетам обоих его потомков. Для ротации ее направление (вправо или влево) зависит от того, какой из потомков текущего узла имеет меньший приоритет. Если, например, приоритет левого потомка меньше, то правая ротация переносит левый потомок вверх на один уровень, а текущий узел перемещается на один уровень вниз. Каждому внешнему узлу приписывается приоритет 2.0, достаточно большой, чтобы ошибочно не переместить его вверх. Функция bubbleDown применяется в тех случаях, когда элемент в дереве случайного поиска располагается выше, чем это следует в соответствии со значением его приоритета. Эта функция будет использована впоследствии для удаления элемента из дерева поиска.

Код

template<class T> void RandomizedNode<T>::bubbleDown(void)
{
  float lcPriority = lchild() ? lchild()->priority () : 2.0;
  float rcPriority = rchild() ? rchild()->priority () : 2.0;
  float minPriority = (lcPriority < rcPriority) ? lcPriority : rcPriority;
  if (priority () <= minPriority)
    return;
  if (lcPriority < rcPriority)
    rotateRight();
  else
    rotateLeft();
  bubbleDown();
}


Общедоступные компонентные функции rchild, Ichild, next, prev и parent определяют связи текущего узла с его правым и левым потомками, с последующим и предшествующим узлами и с предком соответственно:

Код

template<class T>
RandomizedNode<T> *RandoraizedNode<T>::rchild(void)
{
  return (RandomizedNode<T>*) _rchild;
}

template<class T>
RandomizedNode<T> *RandomizedNode<T>::lchild(void)
{
  return (RandomizedNode<T>*) _lchild;
}

template<class T>
RandomizedNode<T> *RandomizedNode<T>::next(void)
{
  return ( RandomizedNode<T>*) next;
}

template<class T>
RandomizadNode<T> *RandomizedNode<T>::prev(void)
{
  return (RandomizedNode<T>*)_prev;
}

template-Cclass T>
RandomizedNode<T> * RandomizedNode<T>::parent(void)
{
  return (RandcaaizedNode<T>* ) _parent ;
}


Компонентная функция priority возвращает приоритет текущего узла:

Код

template<class T>
double RandomizedNode<T>::priority(void)
{
  return _priority;
}




 Класс RandomizedSearchTree

Деревья случайного поиска представляются в виде объектов класса RandomizedSearchTree. Во многих отношениях шаблон класса напоминает класс BraidedSearchTree: элемент данных root указывает на головной узел, win представляет окно, а элемент cmp указывает на функцию сравнения деревьев.

Код

template<class T> class RandomizedsearchTree {
private :
  RandomizedNode<T> *root;       // головной узел
  RandomizedNode<T> *win;        // окно
  int (*cmp) (T,T);                 // функция сравнения
  void _remove(RandomizedNode<T>*);
public :
  RandomizedsearchTree (int (*) (T,T) , int = -1);
  ~RandomizedsearchTree (void);
  Т next (void);
  Т prev(void);
  void inorder (void (*) (T) );
  Т val (void);
  bool isFirst (void);
  bool isLast (void);
  bool isHead(void);
  bool isEmpty (void);
  Т find (T);
  Т findMin (void);
  T locate (T);
  T insert (T);
  void remove (void);
  T remove (T);
  T removeMin (void);
};



ЧАСТЬ 2 >>





Файлы:
rtree1.gif
rtree2.gif
rtree3.gif

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

 

 

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


Популярные:
  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. Проверить дубляжи в столбце


 

 

 
 
На главную