ПК 2102. ПК(2102). П. Г. Колинько пользовательские контейнеры
 Скачать 0.78 Mb.
|
3.2. Деревья двоичного поискаДерево двоичного поиска (ДДП) — это способ хранения множества в форме расширяемого упорядоченного списка с сохранением упорядоченности при вставке новых элементов без перемещения уже имеющихся. ДДП — это дерево с нагруженными узлами, вес в любом узле которого больше любого веса в левом его поддереве и не больше любого веса в правом поддереве. Количество шагов алгоритма поиска элемента множества в таком дереве не превышает его высоты, т. е. оценивается как O(log n). Такую же сложность имеют операции вставки нового элемента в дерево и удаления элемента. ДДП можно получить из упорядоченной последовательности ключей, если двоичное дерево соответствующей мощности разметить внутренним (симметричным) способом, а затем заменить номера узлов соответствующими элементами последовательности. Если последовательность хранится в массиве, то построить ДДП можно методом деления пополам: поместить в корень дерева средний по порядку элемент, затем рекурсивно создать левое поддерево из первой половины последовательности, а правое — из второй. Node * Build(int a, int b, vector //Сборка ДДП из отрезка [a, b] упорядоченного вектора ключей data { if (b <= a) return nullptr; int c = (a + b) /2; Node * s = new Node (data[ c ]); s->left = Build(a, c, data); s->right = Build(c+1, b, data); return s; }  а) BST (n= 15) ------------------------------------>..17................................................... .........................8.................................................................21.................. .............4.......................15........................................20......................44...... .......2...........6...........10..........16............................18..........21..........34..........55 ............................................................................................................... б) BST (n= 7) —------------------------------------>..55................................................... .........................44.................................................................................... .............34................................................................................................ .......21...................................................................................................... ....21......................................................................................................... ...20.......................................................................................................... ...18.......................................................................................................... .............................................................................................................. Рис. 3.2. Деревья двоичного поиска: а – сбалансированное, б – вырожденное Недостаток ДДП в том, что оно хорошо работает только в том случае, если сбалансировано, т. е. длины путей из корня в любой лист примерно одинаковы. Однако при поэлементной вставке в дерево упорядоченной последовательности дерево вырождается, превращаясь в линейный список. Поиск, вставка и удаление в таком дереве будут выполняться не за логарифмическое, а за линейное время. Вероятность вырождения весьма велика. Так, из 7 узлов можно образовать только одно полностью сбалансированное дерево, а полностью вырожденных — 64 (рис. 3.2). Поэтому алгоритмы работы с ДДП часто дополняют автобалансировкой после вставки и удаления. Наиболее употребительны следующие схемы.  AVL-Tree(h=5 n=17) --------->...........40............................................ ...................35.....................o......................80..................... ........20..........-...........38....................60..........-...........90........ ..10....+.....31..........37....-...............50....-.....70................+.....100. ..o........30.o..32.......o..................44.o..55.......o.......................o... ...........o.....o...........................o.....o.................................... ........................................................................................ Рис. 3.3. АВЛ-дерево: –, о, + — значения баланса в узлах 1. АВЛ-деревья. Разность высот поддеревьев любого узла дерева не превышает 1. Информация о разности высот хранится в узле и используется для его перестройки после вставки и удаления узла (рис. 3.3).  BSTh (n= 11) ------------------------------------>..16............................................. .....................8.................................3...............................18............. .........4...........2...........10........................................17..........2...........21. ...2.....1.....6.................1.....15..................................0.................20....1.. ...0...........0.......................0.....................................................0........ ...................................................................................................... Рис. 3.4. ДДП с хранимой высотой (под каждым узлом — высота его поддерева) 2. Деревья с хранимой высотой. Если разместить в каждом узле ДДП поле со значением высоты поддерева, корнем которого является узел, возможна автоматическая поддержка балансировки способом, подобным АВЛ-дереву: балансы вычисляются на ходу сравнением высот поддеревьев в каждом проходимом узле (рис. 3.4).  BSTp (n= 11) ------------------------------------>..16............................................. .....................8.................................11..............................18............. .........4...........6...........10........................................17..........4...........21. ...2.....3.....6.................2.....15..................................1.................20....2.. ...1..........1.........................1.....................................................1........ ...................................................................................................... Рис. 3.5. ДДП с хранимой мощностью (под каждым узлом — мощность поддерева) 3. Деревья с хранимой мощностью. Если в каждом узле имеется дополнительное поле, хранящее мощность поддерева, можно организовать вставку нового узла в корень или в случайное место, поддерживая тем самым относительную сбалансированность ДДП (рис. 3.5). RB-Tree ---> 35 ..................................... ..................23......................................52.................. ........17*.................31..................43..................57........ ...3.........18........29*.......33*.......41*.......46*.......54*.......61*.. .0*..11*...................................................................... .............................................................................. Рис. 3.6. Красно-черное дерево (красные узлы помечены *) 4. Красно-черные деревья. Узлы красятся в один из двух цветов — черный или красный. Если узел красный, его сыновья — обязательно черные. Вставляемый узел всегда красный. При появлении цепочки из двух красных узлов дерево перестраивается (рис. 3.6).  2-3-Tree (h=3) --------------------->..10................................ .........................................50............................... ..........................................100............................. .......................................................................... ...........10...........................50...........................100.. ............40...........................70...........................103. ..............@ ..........................@ ..........................@ .......................................................................... .10........40...............50..........70...............100.........103.. ..20........44...............55..........80...............101.........104. ...30.........@ .............60..........90...............102.........105 Рис. 3.7. 2–3-дерево (тройки из управляющих узлов; отсутствующие узлы помечены @) 5. 2–3-деревья. Данные хранятся в листьях, над которыми делается надстройка из управляющих узлов, каждый из которых может иметь 2 или 3 сына и содержит наибольшие значения ключей в левом и в среднем поддеревьях, что необходимо для операции поиска. Если в результате вставки или удаления у управляющего узла оказывается 1 или 4 сына, дерево перестраивается (рис. 3.7). 6. 1–2-деревья. Узлы такого дерева объединяются в «горизонтальные группы» по два. При добавлении в группу третьего узла она разбивается на две подгруппы, выделяя корень, который передается вверх по иерархии, поддерживая тем самым общую сбалансированность дерева (рис. 3.8). Подробнее о ДДП и деревьях с автобалансировкой — в [13, с. 457–468], [9, с. 341–344].  1-2_Tree (h=3) ---------->......40.......................................... ............................................................................ ............20....................................60........................ ...................................................80....................... .....10............24....................50.......70.........90............. ......12............30........................................100........... ............................................................................ Рис. 3.8. 1–2-дерево (при подсчете высоты дерева двойные узлы считаются за один) Двуместные операции над множествами в ДДП можно выполнять, используя примитивы проверка–вставка–удаление. Очевидно, что временная сложность двуместной операции при этом будет в среднем O(n log n). В худшем случае, при вырожденных деревьях, двуместная операция потребует O(n2) времени. Более того, если алгоритм порождает упорядоченную последовательность ключей, ДДП, полученное в результате последовательности вставок, всегда будет вырожденным. Однако можно использовать тот факт, что из ДДП легко получить упорядоченную последовательность ключей внутренним обходом. Применив такой обход к двум ДДП одновременно, можно обработать последовательности алгоритмом слияния, модифицировав его для нужной операции над множествами. Результат в виде упорядоченной последовательности записывается в массив (вектор), из которого затем описанным ранее методом деления пополам строится новое ДДП. Этот способ обеспечивает получение результата за время O(n) независимо от формы исходных ДДП, а результат всегда получается сбалансированным. Его недостаток — необходимость в буферной памяти. Без нее можно обойтись, если использовать деревья специального вида (с автобалансировкой и т. п.). ДДП сами по себе мало пригодны для хранения множеств с повторениями, поскольку дубликаты ключей искажают форму дерева, образуя в нем мертвые зоны: группы указателей, которые никогда не используются. Если дубликаты редки, проблемой можно пренебречь. Если же их может быть много, нужны специальные способы, применимость которых зависит от задачи. Так, вместо дубликатов ключей можно хранить в каждом узле дерева значение кратности (1 или больше). Если же дубликаты должны быть представлены явно, их можно хранить в узлах как цепочки переполнения, по аналогии с хеш-таблицей. 3.2.1. Контрольные вопросы1. Каким способом следует разметить дерево, чтобы в нем был возможен двоичный поиск? Как его следует нагрузить? 2. Почему для операций с двоичным деревом дают две оценки сложности — «в худшем случае» и «в среднем»? Почему не рассматривается «лучший» случай? 3. Отчего деревья двоичного поиска вырождаются? 4. Можно ли воспрепятствовать вырождению ДДП? 5. Каков оптимальный алгоритм двуместной операции над множествами, представленными деревьями двоичного поиска? 6. Какова временная сложность такой операции и как сказывается на ней возможное вырождение деревьев? 7. Может ли при двуместной операции над множествами в ДДП получиться вырожденное дерево-результат? 8. Можно ли хранить в дереве двоичного поиска множество с повторениями? 9. Какая структура данных требует больше памяти для хранения множества: хеш-таблица или дерево двоичного поиска? 10. Какая из них быстрее работает? 11. Как сделать не вырождающееся ДДП? Зачем оно может понадобиться? 12. Какая структура данных является оптимальной для хранения дерева двоичного поиска? |