Powered By Blogger

Thursday, September 27, 2012

Абстрактные типы данных - Бинарные деревья поиска 2


Дерамиды (декартовы деревья)
Вставка в декартово дерево
Удаление из декартова дерева
Заключение
Из предыдущей статьи "Абстрактные типы данных - Бинарные деревья поиска" Вы узнали, что бинарные деревья поиска являются мощной структурой данных для поиска и выборки данных. Бинарные деревья поиска могут быть довольно простыми, как и операции на них. Над бинарными деревьями возможны и более сложные операции. Однако, реализация более сложных операций не всегда так проста. В особенности, когда речь идёт о вращениях и прочих структурных преобразованиях дерева. Я также указывал уже на то, что в некоторых определённых случаях базовые алгоритмы на бинарных деревьях могут быть крайне неэфективны. Можно выделить три наихудших случая: данные, поступающие на вход, упорядочены по возрастанию:
bst2_0
Добавляемые данные отсортированы в убывающем порядке:
bst2_1
Или, наконец, чередующийся порядок, задом наперёд:
bst2_2
Ни в одном из этих случаев эффективность поиска на бинарном дереве не будет высокой, потому что структурно дерево, содержащее эти данные, эквивалентно связному списку. Эффективность поиска O(log N) вырождается в O(N). Учитывая то, что наибольший выигрыш от использования бинарных деревьев поиска достигается при работе с большими объёмами данных, результатом будет серьёзное падение производительности. К сожалению, классические методы поддержания дерева в оптимальном состоянии дико сложны. Простое решение - изучить усреднённый показатель эффективности на неком бинарном дереве поиска.
В среднем эффективность базового бинарного дерева поиска составляет O(log N). Здесь "в среднем" означает, что данные, поступающие на вход, достаточно случайны, чтобы создать то, что называется "рандомизированным бинарным деревом" (ну или случайным, уж простите за вольность), в котором каждый новый элемент данных с вероятностью 1/N будет помещён в корень произвольного поддерева:
Наиболее очевидный способ создания рандомизированного бинарного дерева - случайная перетасовка входящих данных. Но в большинстве случаев мы не имеем сразу доступа ко всем данным, которые должны храниться в дереве в данный момент времени. На самом деле, чаще всего мы будем добавлять по одному элементу данных из потока. Это крайне усложняет задачу перемешивания данных ещё до их добавления в дерево.
Случайное бинарное дерево может быть создано, если каждый элемент набора данных имеет одинаковые шансы стать вершиной поддерева. Мы можем прибегнуть к упомянутым в предыдущей статье функциям вставки в вершину. При каждой вставке мы можем случайным образом использовать вставку в вершину или обычную вставку. Таким образом мы получим случайное бинарное дерево. Алгоритм выглядит неплохо и на удивление прост для реализации. В реализации нашего алгоритма будем использовать структуры struct node и struct tree, описанные в предыдущей статье:

1 struct node {
2         struct node* link[2];
3         int data;
4 };
5
6 struct tree {
7         struct node* root;
8         size_t size;
9 };

Возьмём простую рекурсивную вставку на основе функций из предыдущей статьи "Абстрактные типы данных - Бинарные деревья поиска":

 1 struct node* insert_r (struct node* root, struct node* item, int key)
 2 {
 3         if (root == NULL)
 4                 root = item;
 5         else {
 6                 int dir = root->data < key;
 7                 root->link[dir] = insert_r (root->link[dir], item, key);
 8         }
 9
10         return root;
11 }
12
13 void insert (struct tree* tree, struct node* item, int key)
14 {
15         tree->root = insert_r (tree->root, item, key);
16         ++tree->size;
17 }

Предполагая сортированные данные на входе, используя этот алгоритм мы получим вырожденное дерево. Однако, два простых изменения помогут сократить вероятность вырождения дерева до пренебрежительно малого значения. Первая модификация: добавим аргумент sz в прототипе insert_r(). Начальное значение этого аргумента будет задаваться с помощью tree->size в insert(). При каждом рекурсивном вызове insert_r() будет передаваться половина данного значения, которое является грубой оценкой числа элементов в поддереве.
Вторая модификация: вставка в вершину; текущее поддерево будет вершиной в которую производится вставка. Вставка в вершину будет сделана с вероятностью 1/sz. В общем и в целом, подразумевая, что у нас есть функция root_insert(), изменения, сделанные нами в изначальном коде insert_r() и insert() будут выглядеть следующим образом:

 1 struct node* insert_r (struct node* root, struct node* item, int key, int sz)
 2 {
 3         if (root == NULL)
 4                 root = item;
 5         else if (rand () % (sz + 1) == sz)        /* Вероятность 1/sz */
 6                 root = root_insert (root, item, key);
 7         else {
 8                 int dir = root->data < key;
 9                 root->link [dir] = insert_r (root->link [dir], item, key, sz / 2);
10         }
11
12         return root;
13 }
14
15 void insert (struct tree* tree, struct node* item, int key)
16 {
17         tree->root = insert_r (tree->root, item, key, tree->size);
18         ++tree->size;
19 }

Здесь мы используем вероятно не лучший источник случайных чисел, однако, на данный момент так будет проще. По поводу достоинств разных источников энтропии и их использования см. Random Numbers tutorial (eternallyconfuzzled.com). Пока же мы ограничимся функцией стандартной библиотеки.
Предположения о существовании root_insert() было достаточно на этапе "проектирования", но в реальном коде нам будет полезна конкретная реализация. Не вдаваясь в детали, возьмём такую примерную реализацию:

 1 struct node* root_insert (struct node* root, struct node* item, int key)
 2 {
 3         if (root == NULL)
 4                 root = item;
 5         else {
 6                 struct node* save;
 7                 int dir = root->data < key;
 8
 9                 root->link [dir] = root_insert (root->link [dir], item, key);
10
11                 /* Поворот относительно вершины */
12                 save = root->link [dir];
13                 root->link [dir] = save->link [!dir];
14                 save->link [!dir] = root;
15                 root = save;
16         }
17
18         return root;
19 }

В этих функциях нет ничего нового, так что у любого, кто читал "Абстрактные типы данных - Бинарные деревья поиска", проблем с ними возникнуть не должно.
Альтернативой обычной вставке с поднятием нового элемета данных в выбранную с некоторой вероятностью вершину является вероятностное объединение поддеревьев. Этот метод используется в "официальных" реализациях случайных бинарных деревьев поиска, как описано у Martinez и Roura. Алгоритмы вставки на верхнем уровне не особо изменились и в целом уже знакомы нам:

 1 struct node* insert_r (struct node* root, struct node* item, int key)
 2 {
 3         int n = (root == NULL) ? 0 : root->size;
 4
 5         if (rand () % (n + 1) == n)
 6                 return root_insert (root, item);
 7         else {
 8                 int dir = root->data < key;
 9                 root->link [dir] = insert_r (root->link [dir], item, key);
10                 ++root->size;
11         }
12
13         return root;
14 }
15 
16 void insert (struct tree* tree, struct node* item, int key)
17 {
18         tree->root = insert_r (tree->root, item, key);
19 }

Вместо поиска вершины root со значением NULL единственным фактором при решении о месте вставки становится оценка вероятности. Заметьте, что вершина - это терминальный узел, n будет равно 0 и оценка вероятности будет такой, как нам и надо. Таким образом симулируется обычная вставка листового узла. Условия для предельного случая вставки на терминальном узле гарантированно соблюдаются.
Операция объединения будет выполняться функцией root_insert() с помощью split(). root_insert() не производит поиск; вместо этого она просто резервирует место для нового элемента и объединяет с деревом на выбранной вершине. Такая операция может быть непростой, ведь небходимо гарантировать что дерево останется правильно построенным бинарным деревом. Поэтому split() должна быть рекурсивной функцией, чтобы выполнять очистку на поддереве, присоединённом к данной вершине. Естественно функция split() не обязана быть рекурсивной, но в данном случае рекурсия - это то, что делает жизнь легче:

 1 void split (struct node* root, struct node* item, struct node** s, struct node** g)
 2 {
 3         if (root == NULL)
 4                 *s = *g = NULL;
 5         else if (item->data < root->data) {
 6                 *g = root;
 7                 split (root->link [0], item, s, &((*g)->link [0]));
 8         } else {
 9                 *s = root;
10                 split (root->link [1], item, &((*s)->link [1]), g);
11         }
12 }
13 
14 struct node* root_insert (struct node* root, struct node* item)
15 {
16         struct node *s, *g;
17
18         split (root, item, &s, &g);
19
20         root = item;
21         root->link [0] = s;
22         root->link [1] = g;
23         root->size = 1;
24
25         root->size += s == NULL ? 0 : s->size;
26         root->size += g == NULL ? 0 : g->size;
27
28         return root;
29 }

Такая реализация функции root_insert() крайне проста. Большую часть работы она передаёт split(). root_insert() просто берёт результат выполнения split() и присоединяет полученный элемент к вершине root, попутно убеждаясь, что размеры изменены корректно и соответствуют структурным изменениям в поддереве. split() несколько сложнее. В частности то, как она рекурсивно обеспечивает правильную структуру дерева. Рассмотрим следующий пример:
bst2_3
Скажем, мы хотим добавить в дерево узел c. split() нужно зарезервировать место для c, не нарушая структуру инвариантность бинарного дерева. Это достигается разделением двух поддеревьев нового узла без потери инвариантности. Здесь приведён пример разбиения поддеревьев для добавления узла с. Важным для для понимания алгоритма является момент, что каждый рекурсивный вызов оперирует на дочерних узлах s или g. (! обозначает текущий узел, ? - неопределённый указатель, ~ - NULL-указатель):
bst2_4


bst2_5


bst2_6


bst2_7


bst2_8
После того, как split() разбила дерево, отдельные части выглядят приблизительно как на следующей диаграмме. Теперь всё, что осталось root_insert(), использовать s и g для реструктуризации дерева. Попробуйте пройтись по коду самостоятельно и проверьте правильность результата:
bst2_9
Все эти трюки служат одной цели - сохранить инвариантность дерева, т.е., гарантию того, что каждый элемент по-прежнему имеет больший ключ, чем вершина его левого поддерева и меньший, чем его вершина его правого поддерева. Без этого нам бы пришлось использовать вставку у листа и вращения, чтобы избежать сложных проблем, связанных с коррекцией объединения.
Заметьте: такая реализация insert() допускает повторение ключей. Есть несколько способов избавиться от дубликатов, начиная с самых простых, но не очень эффективных, до довольно сложных, но очень быстрых. При объединении самое простое решение - вызов find() перед каждой операцией вставки:

1 int insert (struct tree* tree, struct node* item, int key)
2 {
3         if (find (tree, key))
4                 return 0;
5
6         tree->root = insert_r (tree->root, item, key);
7
8         return 1;
9 }

Удаление из такого рандомизированного бинарного дерева - это "просто" операция, обратная разбиению, метко названная объединением. Код функции remove на данный момент будет выглядеть так:

 1 struct node* remove_r (struct node* root, struct node** old_item, int key)
 2 {
 3         struct node* save;
 4
 5         if (root != NULL) {
 6                 if (key == root->data) {
 7                         save = join (root->link [0], root->link [1]);
 8                         *old_item = root;
 9                         root = save;
10                 } else {
11                         int dir = root->data < key;
12                         root->link [dir] = remove_r (root->link [dir], old_item, key);
13                         --root->size;
14                 }
15         }
16
17         return root;
18 }
19
20 int remove (struct tree* tree, struct node** old_item, int key)
21 {
22         if (!find (tree, key))
23                 return 0;
24
25         tree->root = remove_r (tree->root, old_item, key);
26
27         return 1;
28 }

join() удаляет вершину root и заново соединяет структуры с помощью ссылок, сохраняя правильное построение рандомизированного бинарного дерева поиска, так что мы и дальше можем пользоваться оценкой вероятности. Код лаконичен, но возможно не совсем ясен:

 1 struct node* join (struct node* left, struct node* right)
 2 {
 3         int ln = left == NULL ? 0 : left->size;
 4         int rn = right == NULL ? 0 : right->size;
 5
 6         if (ln + rn == 0)
 7                 return NULL;
 8         else if (rand () % (ln + rn) < ln) {
 9                 left->link [1] = join (left->link [1], right);
10                 left->size += rn;
11                 return left;
12         } else {
13                 right->link [0] = join (left, right->link [0]);
14                 right->size += ln;
15                 return right;
16         }
17 }

Чтобы на примере рассмотреть работу функции join(), возьмём такое же дерево, как для примера со split(). Однако на сей раз мы будем удалять узел e вместо добавления c к e:
bst2_10
Принимая в качестве аргументов ссылки узла g (d и h), join() сначала проверяет, был ли узел g терминальным. С этой целью функция вычисляет сумму размеров поддеревьев узла. Если g был терминальным узлом, мы может просто заменить его указателем на NULL. Однако, в нашем случае у g есть два дочерних узла, так что придётся проделать чуть больше работы. Используя вероятность так же, как при вставке (1/sz), join() рекурсивно вызывает сама себя в поисках подходящей замены, основываясь на значении вероятности. Допустим, выбрано правое направление, тогда наше дерево примет такой вид:
bst2_11
Если бы был выбран левый путь, окончательная структура дерева выглядела бы так:
bst2_12
Так как трассировка выполнения этого алгоритма тривиальна, а трассировка рекурсивного алгоритма к тому же хорошая практика, я оставляю вам выяснение того, как алгоритм создаёт окончательную структуру представленных деревьев.

Дерамиды (декартовы деревья) [наверх]

Вычурно названные дерамиды являются структурой данных, совмещающих в себе свойства бинарной кучи и бинарного дерева поиска (вообще, этот АТД наверно более известен под названием "декартово дерево"). Если генерируемый для кучи приоритет - случайное число, то результат такой гибрилизации - на удивление хорошо сбалансированное рандомизированное бинарное дерево поиска. Дерамида (далее всё-таки буду придерживаться более распространённого названия в русскоязычной среде - "декартово дерево") должна подчиняться двум жёстким правилам:
Как бинарное дерево (для u с левым дочерним узлом v и правым - w):

1 v->data < u->data < w->data

Как куча:

1 w->priority < v->priority < u->priority

При присвоении приоритетам случайных значений или хэшировании данных с одной стороны и соблюдении условий для бинарной кучи и дерева мы получаем прекрасную возможность построить хорошо сбалансированное дерево. В худшем случае его эффективность всё же будет линейно зависеть от числа элементов O(n), как и в случае прочих разновидностей рандомизированного бинарного дерева. Однако вероятность вырождения дерева не так велика. Там, где гарантия лучшего случая не является необязательной, декартово дерево демонстрирует приемлемую эффективность и его легко реализовать.

Вставка в декартово дерево [наверх]

Вставка в декартово дерево - простая операция. Имея на входе новый элемент данных и случайный приоритет, просто осуществляем вставку в бинарное дерево поиска, а затем идём по дереву обратно, вращая поддеревья, пока не будет удовлетворено условие бинарной кучи. Это один из относительно простых вариантов вставки элемента данных в дерево не у листа. Вращая поддеревья, мы можем гарантировать, что свойства бинарного дерева сохраняются. Однако, в оригинальную структуру struct node надо внести небольшие изменения:

 1 struct node {
 2         struct node* link [2];
 3         int priority;
 4         int data;
 5 };
 6
 7 struct node NullItem = { &NullItem, &NullItem, RAND_MAX, 0 };
 8 struct node *Null = &NullItem;
 9
10 struct tree {
11         struct node *root;
12 };

Мы добавили поле приоритета. Кроме того, я определил две глобальные переменные типа struct node, проинициализированные предельными значениями, и указателями на себя. Наше декартово дерево будет использовать Null вместо NULL для обозначения терминального листа. Это выглядит, как необязательная модификация, но это изменение сильно упрощает алгоритм удаления.
Рекурсивный алгоритм вставки, реализованный в insert для декартова дерева - сама простота:

 1 struct node* insert_r (struct node* root, struct node* item, int key)
 2 {
 3         if (root == Null)
 4                 root = item;
 5         else {
 6                 int dir = root->data < key;
 7
 8                 root->link[dir] = insert_r (root->link [dir], item, key);
 9
10                 if (root->priority < root->link [dir]->priority) {
11                         struct node* save = root->link [dir];
12                         root->link [dir] = save->link [!dir];
13                         save->link [!dir] = root;
14                         root = save;
15                 }
16         }
17
18         return root;
19 }
20 
21 void insert (struct tree* tree, struct node* item, int key)
22 {
23         tree->root = insert_r (tree->root, item, key);
24 }

Эта функция невероятно проста. Возможно, единственный момент, который может показаться неясным, использование переменной dir для определения направления поворота. Однако, понимание этой идиомы позволит Вам использовать более короткий и простой код. Этой сложности можно избежать при явной обработке двух случаев отдельными ветками условия, если угодно:

 1 if (key < root->data) {
 2         root->link [0] = insert_r (root->link [0], item, key);
 3
 4         if (root->priority < root->link [0]->priority) {
 5                 struct node* save = root->link [0];
 6                 root->link [0] = save->link [1];
 7                 save->link [1] = root;
 8                 root = save;
 9         }
10 } else {
11         root->link [1] = insert_r (root->link [1], item, key);
12
13         if (root->priority < root->link [1]->priority) {
14                 struct node* save = root->link [1];
15                 root->link [1] = save->link [0];
16                 save->link [0] = root;
17                 root = save;
18         }
19 }

Конечно, это делает ненужным применение массива ссылок в struct node, но вполне соответствует традиционному дизайну бинарных деревьев поиска, принятому в книгах и обучении.
Те, кто внимательно читал "Абстрактные типы данных - Бинарные деревья поиска", могут обнаружить, что вставка в декартово дерево очень похожа на вставку в базовое бинарное дерево поиска у вершины. Таким образом, мы можем без труда преобразовать алгоритм в не рекурсивный:

 1 int insert (struct tree* tree, struct node* item, int key)
 2 {
 3         struct node* walk;
 4         struct node* up [50];
 5         int dir;
 6         int top = 0;
 7
 8         /* Дерево пустое */
 9         if (tree->root == Null) {
10                 tree->root = item;
11                 return 1;
12         }
13
14         /* Поиск пустой ссылки */
15         walk = tree->root;
16
17         for ( ; ; ) {
18                 if (walk->data == key)
19                         return 0;
20
21                 dir = walk->data < key;
22
23                 if (walk->link[dir] == Null)
24                         break;
25
26                 up [top++] = walk;
27                 walk = walk->link [dir];
28         }
29
30         /* Вставка нового элемента */
31         walk->link [dir] = item;
32
33         /* Проход в обратном направлении и вращение */
34         while (item != tree->root) {
35                 if (walk->priority > item->priority)
36                         break;
37
38                 dir = item == walk->link [1];
39                 walk->link [dir] = item->link [!dir];
40                 item->link [!dir] = walk;
41
42                 /* Применяем изменения к остальным частям дерева */
43                 if (top > 0 && up [top - 1] != Null) {
44                         dir = (walk == up [top - 1]->link [1]);
45                         up [top - 1]->link [dir] = item;
46                 }
47
48                 /* Сброс вершины, если надо */
49                 if (tree->root == walk)
50                         tree->root = item;
51
52                 /* Двигаемся вверх и начинаем новый проход */
53                 walk = up [--top];
54         }
55 
56         return 1;
57 }

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

Удаление из декартова дерева [наверх]

Удаление узла - не такая важная операция, как вставка и часто её обходят без упоминания. Хотя я согласен с таким подходом, но всё же приведу небольшой кусочек кода, если он может оказаться полезным. Это чувство у меня появилось во времена тщетных попыток вывести полезный код удаления из примеров, когда я сам изучал структуры данных. Алгоритм удаления из декартова дерева в точности противоположен вставке, удивительно, но факт. Нам нужно нати элемент данных и произвести поворот (нисходя далее по дереву от нашего элемента), пока не достигнут лист, а затем наш элемент просто удаляется. Операция обычно называется "проталкиванием вниз" (продавливанием?), что лишь в очередной раз подтверждает наличие отсутствие особой фантазии у учёных, работающих в области теории вычислительных машин и систем. Алгоритм краток:

 1 struct node* remove_r (struct node* root, struct node** old_item, int key)
 2 {
 3         if (root != Null) {
 4                 struct node* save;
 5
 6                 if (key == root->data) {
 7                         int dir = root->link [0]->priority > root->link [1]->priority;
 8
 9                         save = root->link [dir];
10                         root->link [dir] = save->link [!dir];
11                         save->link [!dir] = root;
12                         root = save;
13
14                         if (root != Null)
15                                 root = remove_r (root, old_item, key);
16                         else {
17                                 *old_item = root->link [1];
18                                 root->link [1] = Null;
19                         }
20                 }
21                 else {
22                         int dir = root->data < key;
23                         root->link [dir] = remove_r (root->link [dir], old_item, key);
24                 }
25         }
26 
27         return root;
28 }
29 
30 void remove (struct tree* tree, struct node** old_item, int key)
31 {
32         tree->root = remove_r (tree->root, old_item, key);
33 }

Поиск прост: если корень root не является терминальным узлом, двигаемся влево или право, соответственно. Иначе, совершаем поворот в соответствующем направлении и рекурсивно идём дальше, пока root не станет терминальным узлом. Если root является терминальным узлом, то простая его замена на Null достаточна для удаления узла из дерева. После удаления алгоритм должен пройти в обратном направлении вверх и исправить испорченные ссылки.
Изучив этот код, Вы увидите, почему я предпочитаю специальные метки вместо простого указателя на NULL чтобы отметить терминальный узел. Если бы я использовал NULL-указатели, следующий кусок кода наверняка спровоцировал бы ошибку, т.к. при разыменовании root содержит неверный указатель.

1 if (root != Null)
2         root = remove_r (root, old_item, key);
3 else {
4         *old_item = root->link [1];
5         root->link [1] = Null;
6 }

Заключение [наверх]

Бинарные деревья поиска хороши для начала, но при этом имеющие место худшие случаи для них действительно худшие и что немаловажно, они отнюдь не редки. Используя рандомизацию при добавлении данных в дерево мы можем избегать худших случаев большу часть времени. Хотя я затронул лишь три вариации рандомизированных деревьев, на самом деле их больше. Не должно пройти незамеченным и сходство с алгоритмом быстрой сортировки. Базовый алгоритм быстрой сортировки похож на алгоритмы на базовых бинарных деревьях поиска: быстрый, но с такими же худшими случаями, коотрые очень сильно бьют по эффективности. Использование рандомизации в алгоритмах быстрой сортировки, и алгоритмах на бинарных деревьях поиска помогает минимизировать вероятность возникновения ситуаций, развивающихся по наихудшему сценарию. Таким образом эти алгоритмы становятся более полезными для среднестатистического программиста, причём особых усилий такое усовершенствование не требует.
Оригинал этой статьи вы можете найти здесь: eternallyconfuzzled.com.
mind_fuck

ПОСЕТИТЕЛИ

free counters