1.3 Понятие транзакций и проблема их кластеризации
Термин “транзакция” относится к подмножеству предметов из общей совокупности с переменным числом предметов (мощностью подмножества). Транзакциями являются записи в таблице, содержащие категориальные атрибуты и имеющие различную длину, в отличие от категориальных БД, где длина всех записей одинакова. В связи с этим транзакционные БД считаются менее упорядоченными, по сравнению с категориальными БД, что усложняет их кластеризацию. Похожие транзакции должны иметь общие предметы при определенном уровне поддержки частоты их встречаемости, не ниже заданного, называемого минимальной поддержкой. Этого трудно добиться на разреженных транзакционных данных с низкой встречаемостью одинаковых наборов предметов. Примером таких транзакций являются множества терминов в статьях или документах, когда близкие по смыслу текстовые источники содержат мало точно совпадающих терминов (ключевых слов), т.е. трудно выделить общую тему. Классическими примерами транзакций являются корзина покупок в магазине, профиль интересов клиента, множество симптомов пациента, множество характеристик образа и тому подобное.
Транзакционная или операционная база данных (Transaction database) представляет собой двумерную таблицу, которая состоит из номера транзакции (TID) и перечня покупок, приобретенных во время этой транзакции.
TID - уникальный идентификатор, определяющий каждую сделку или транзакцию.
Пример транзакционной базы данных, состоящей из покупательских транзакций, приведен ниже в таблице. В таблице первая колонка (TID) определяет номер транзакции, во второй колонке таблицы приведены товары, приобретенные во время определенной транзакции.
|
TID
|
Приобретенные покупки
|
100
|
Хлеб, молоко, печенье
|
200
|
Молоко, сметана
|
300
|
Молоко, хлеб, сметана, печенье
|
400
|
Колбаса, сметана
|
500
|
Хлеб, молоко, печенье, сметана
|
Благодаря последним разработкам в области поиска информации, Web технологий и Data Mining, кластеризация транзакций играет важную роль и привлекает внимание во многих приложениях и областях, в которых ускоряет поиск ближайшего соседа. Например, кластеризация используется как важнейший метод во многих web приложениях; транзакционная кластеризация применяется в целевом маркетинге/рекламе, при обнаружении причин заболеваний, при поиске информации, основанном на содержании образа, при получении рекомендаций соединений для web пользователей, организации папок и закладок, создании информационных иерархий подобных Yahoo! и Infoseek и т.д.
Для кластеризации транзакций оказываются не эффективными подходы, основанные на парной похожести транзакций (k-means, k-modes) и используемых при этом локальных критериях оценки похожести. Проблема заключается в том, что транзакционные данные являются разреженными, каждая транзакция содержит небольшое количество предметов из общей совокупности и малое число общих предметов с другими транзакциями.
В современных исследованиях доказывается, что для транзакций, составленных их разреженно распределенных предметов, парная похожесть не является ни необходимым, ни достаточным критерием для группирования транзакций в кластере.
Пример 1. Рассмотрим кластер из пяти транзакций
t1 = {a,e,h,k}, t2 = {a,c,f}, t3 = {a,b,c}, t4 = {b,c,i,j}, t5 = {b,e,g}.
Каждая транзакция представляет собой множество любимых боевиков пяти личностей. Из всех возможных 10 пар транзакций только две пары (t2, t3) и (t3, t4) имеют два общих боевика. Все другие пары имеют не более чем 1 общий боевик. Следовательно, парное подобие в этом кластере слабое. Однако можно заметить, что a,b,c являются типичными боевиками, так как два из них присутствуют в 3-х из пяти транзакций, т.е. вероятность любителей боевиков составляет 60%. Следовательно, эти типичные боевики можно использовать, чтобы характеризовать интересы этого кластера людей, в противоположность кластеру людей, интересующихся мелодрамами. Дело в том, что для большого числа боевиков и большого кластера людей, которые любят боевики, маловероятно, что каждый человек предпочитает те же боевики, что и другой человек в этом кластере. В связи с низкой парной похожестью внутри кластера необходимы другие критерии оценки похожести предметов в кластере, способные сгруппировать любителей боевиков и мелодрам в разные кластеры.
1.4 Кластеризация транзакций с использованием концепции часто встречающихся (“больших”) предметов
1.4.1 Подход, основанный на “больших” предметах и функциональный критерий кластеризации
Поддержка предмета в кластере Ci есть относительное число транзакций в этом кластере, которые содержат этот предмет. Примем, что |S| означает число элементов в множестве S. Для определяемой пользователем минимальной поддержки θ (0 < θ ≤ 1) предмет является “большим” в кластере Ci, если его поддержка в кластере не меньше чем θ*|Ci|; в противном случае предмет является “малым” в кластере Ci. Понятно, что большие предметы являются популярными предметами в кластере, которые вносят похожесть в кластер, в то время как малые предметы вносят непохожесть в кластер. Примем, что Largei означает множество больших предметов в Ci, и Smalli означает множество малых предметов в этом кластере. Рассмотрим кластеризацию C = {C1,…Ck}. Чтобы минимизировать стоимость С, имеются два компонента: внутри кластерная и между кластерная стоимости.
1.4.2 Внутри кластерная стоимость (непохожесть)
На этот компонент возлагается ответственность за внутри кластерную непохожесть, измеряемую общим числом “малых” предметов, которое будет возрастать при увеличении кластера, так как при этом уменьшается число общих больших предметов и соответственно растет число малых:
Intra(C) = | ki=1 Smalli| (1)
Этот компонент будет штрафовать большие кластеры, которые имеют слишком много различных малых предметов. Отметим, что если использовать
 , (1*)
то будет неоправданно ограничено создание кластеров с различными малыми предметами в связи с тем, что сумма (1*) больше объединения (1), исключающего дублирование предметов. Эксперименты показывают, что использование суммы ведет к тому, что все транзакции будут помещены в один или небольшое число кластеров, даже если они не похожи.
1.4.3 Между кластерная стоимость (похожесть)
На этот компонент возлагается ответственность за похожесть между кластерами. Поскольку именно большие предметы вносят похожесть в кластер, каждый кластер должен иметь минимально возможное перекрытие по большим предметам с другими кластерами. Это перекрытие определяется выражением:
Функция штрафует (Inter (C) ) кластеры с одинаковыми или перекрывающимися большими предметами за счет увеличения первой суммы и уменьшения объединения, исключающего дублирование. Функция Inter(C) ограничивает дублирование больших предметов в различных кластерах и создание похожих кластеров. Если сложить два компонента вместе, то можно ввести вес w их относительной важности. Тогда функциональный критерий, штрафующий за неправильную кластеризацию, примет вид:
Вес w > 1 увеличивает долю штрафа за внутри кластерную непохожесть, а вес w < 1 делает акцент на штрафе за похожесть кластеров между собой. По умолчанию w = 1.
1.4.4 Цель кластеризации
Для заданной коллекции транзакций и при заданном уровне минимальной поддержки найти такую кластеризацию С, которая отвечает минимуму ее стоимости Cost(C) (минимальному штрафу).
Нахождение точного решения не реально, вследствие большого числа способов разделения транзакций. В практических приложениях достаточно найти приблизительное решение. Данное определение не требует задания числа кластеров, как входного параметра, и стоимость минимизируется для всех членов кластеров. Полезной вариацией является задание некоторого максимального числа кластеров. Кроме того, не используются жесткие пороговые значения, чтобы остановить группирование непохожих транзакций. Вместо этого налагается штраф за неправильные решения. Эти характеристики являются ключевыми для динамической кластеризации, где число кластеров и похожесть в кластере могут изменяться при добавлении новой транзакции. Наконец, понятие больших предметов не является иным представлением центроида кластера. В действительности не оценивается “близость” транзакций в кластере, подобно алгоритму k-средних. Вместо этого используются большие предметы, чтобы оценивать качество кластеризации в целом.
Пример. Рассмотрим 6 транзакций:
t1={a,b,c}, t2={a,b,c,d}, t3={a,b,c,e}, t4={a,b,f} t5={d,g,h}, t6={d,g,i}
Рассмотрим кластеризацию С с одним кластером С1 = {t1,t2,t3,t4,t5,t6}. Предположим, что пользователь установил минимальную поддержку 60%. Большие предметы должны содержаться, по меньшей мере, в 4 транзакциях (6*60%). В четырех транзакциях содержатся только {a,b}, поэтому |Large1| = 2. Остальные предметы являются малыми Small1 ={c,d,e,f,g,h,i}, и по формуле (32) Intra(C1) = 7. Между кластерная похожесть Inter(C1) = 2 – 2 = 0 по формуле из пункта 1.4.3. Таким образом при w = 1, получаем Cost(C1) = 7. Как видно, штраф накладывается за большое число малых предметов, что является неизбежным следствием уменьшения числа больших предметов при чрезмерном укрупнении кластера. Одного кластера мало.
Рассмотрим второй вариант кластеризации C2 с двумя кластерами {C1 = {t1,t2,t3,t4}, C2 = {t5,t6}}. Для кластера С1 большие предметы должны содержаться по меньшей мере в 4*60% 3-х транзакциях. Такими предметами для транзакций в С1 являются {a,b,c}, т.е. |Large1| = 3. Small1 = {d,e,f} и |Small1| = 3. Подобно этому, Large2 = {d,g}, |Large2| = 2, Small2 = {h,i}, |Small2| = 2. Поскольку все малые предметы в кластерах С1 и С2 различные, их объединение приводит к простому суммированию малых предметов Intra (C2) = 3 + 2 = 5). Inter(C2) = (3 + 2) – (3 + 2) = 0. Cost(C2) = 5 + 0 = 5. Кластеризация С2 лучше, чем С1 за счет уменьшения штрафа за сумму малых предметов при нулевом штрафе за одинаковые большие предметы, поскольку таковых нет.
Рассмотрим кластеризацию C3 = {C1 = {t1,t2}, C2 = {t3,t4}, C3 = {t5,t6}}. Общими большими предметами в кластере С1 являются {a,b,c}, т.е. Large1 = {a,b,c}, |Large1| = 3. Small1 = {d}, Large2 = {a,b}, Small2 = {c,e,f}, Large3 = {d,g}, Small3 = {h,i}. Intra(C3) = 1 +3 + 2 = 6 (суммируются малые предметы по трем кластерам, поскольку нет повторов). Inter(C3) = 7 – 5 = 2. Здесь 7 = 3 + 2 + 2 – это простая сумма больших предметов в 3-х кластерах с повтором предметов {a,b}; 5 - это объединение больших предметов по трем кластерам, исключающее повторы предметов а и b, что дает {a,b,c,d,g} с числом элементов 5; Стоимость Cost(C3) = 6 + 2 = 8. В сравнении с С2 расщепление {t1,t2,t3,t4} на два кластера С1 и С2 увеличивает стоимость, поскольку приводит к их большей внутри кластерной непохожести (6 против 5) и между кластерной похожести (2 против 0), за что и налагается штраф.
При выборе минимальной поддержки пользователь должен учитывать, насколько часто предметы могут встречаться в транзакциях, чтобы они могли характеризовать кластер. Вначале обычно используют малую поддержку, чтобы образовать малое число крупных кластеров, где только очень непохожие транзакции попадают в различные кластеры. Затем используется большее значение минимальной поддержки, чтобы добиться лучшей кластеризации. Это повторяется рекурсивно до тех пор, пока стоимость кластеризации невозможно будет уменьшить.
Значение Cost(C) отражает правильность выбора пользователем минимальной поддержки. Однако этот критерий не рекомендуется использовать для выбора минимальной поддержки. Действительно, при минимальной поддержке 1/n, где n – число транзакций, группирование всех транзакций в один кластер даст Cost(C) = 0 (оба слагаемых равны 0). Очевидно, это нельзя интерпретировать как лучшее решение.
1.4.5 Обобщенный алгоритм кластеризации
Коллекция транзакций хранится в файле на диске. Алгоритм читает каждую транзакцию t последовательно и присоединяет t к существующему кластеру, или создает t как новый кластер, тот который минимизирует стоимость для текущей кластеризации. Идентификатор кластера каждой транзакции записывается обратно в файл. Это называется фазой размещения. В фазе усовершенствования алгоритм читает каждую транзакцию t (в том же порядке как в фазе размещения), перемещает t в существующий не одиночный кластер (возможно, оставляет там, где она есть), чтобы минимизировать Cost(C). После каждого перемещения идентификатор кластера у транзакции обновляется, и любой пустой кластер немедленно уничтожается. Если ни одна транзакция не перемещается при проходе по всем транзакциям, фаза усовершенствования оканчивается. В противном случае начинается новый проход. Существенно, что при добавлении каждой транзакции минимизируется глобальный критерий стоимости Cost(C). Ключевым шагом является нахождение адреса кластера для размещения или перемещения транзакции. Этот вопрос обсуждается ниже.
Парадигма следования фазы усовершенствования за фазой размещения заимствована из алгоритмов k-средних и k-мод. Однако в предлагаемом алгоритме имеются важные отличия. Во-первых, не требуется предварительно определять число k кластеров. Вместо этого кластеры создаются и уничтожаются динамически на основе критерия стоимости. Во-вторых, адрес кластера транзакции определяется не по расстоянию до ближайшего кластера или до его моды/центроида, а путем расчета стоимости Cost(C), являющейся не локальным, а глобальным критерием качества.
/* Фаза размещения транзакций */
while not end of the file do
read the next transaction < t, -- >;
allocation t to an existing or new cluster Ci to minimize Cost(C);
write i >;
/* Фаза улучшения кластеризации */
repeat
not_moved = true;
while not end of the file do
read the next transaction < t, Ci > ;
move t to an existing non-singleton cluster Cj to minimize Cost(C);
if Ci ≠ Cj then
write < t, Cj >;
not_moved = false;
eliminate any empty cluster;
until not_moved;
Рис. 5 Обобщенный алгоритм кластеризации
1.4.6 Обновление значения функционального критерия
Допустим, что MinSupi = θ * |Ci|. Поддержка данного предмета в Ci характеризует число транзакций в этом кластере, которые содержат этот предмет. Поэтому предмет является большим в кластере Ci, если и только если его поддержка в этом кластере больше или равна MinSupi. Для каждого кластера Ci необходимо сохранять две структуры данных в памяти: хэш-таблицу Hashi и бинарное дерево Btreei. Эти структуры являются стандартными методами индексации для больших БД.
Hashi: Хэш-таблица для Ci с предметами в виде их индексных ключей. Для каждого предмета e в Ci имеется вход в форме < e, tree_addr > в Hashi, где tree_addr есть адрес соответствующего листового входа для e в Btreei (см. ниже). Hashi обеспечивает доступ к пути, чтобы вставлять, удалять или обновлять поддержку данного предмета.
Btreei: Это бинарное дерево B-tree с поддержкой предметов в Ci в виде индексных ключей. Для каждого предмета e в Ci имеется листовой вход в форме < sup, Hash_addr > в Btreei, где sup есть поддержка e в Ci, а hash_addr есть адрес соответствующего входа для e в Hashi. Btreei обеспечивает доступ к пути для нахождения всех предметов, имеющих данную поддержку.
Минимальная поддержка MinSupi разделяет листовые входы Btreei на входы для больших предметов Largei (в правом поддереве) и входы для малых предметов Smalli (в левом поддереве). Особый интерес вызывают предметы, находящиеся вблизи границы раздела: малые предметы, имеющие поддержку (MinSupi – 1), и большие предметы, имеющие поддержку MinSupi. Когда транзакция помещается в кластер или перемещается в другой кластер, поддержка некоторых предметов будет увеличиваться или уменьшаться на 1. Следовательно, эти предметы могут пересекать границу. Эффективное сохранение следа таких изменений является главной задачей сопровождения. Во-первых, мы определяем две операции.
Мы определяем Inc(Ci, e) как операцию, которая увеличивает поддержку данного предмета e в Ci на 1.
Некоторые шаги включают в себя следующее содержание:
Отыскать Hashi для входа < e, tree_addr >. Допустим, что < sup, hash_addr > является листовым входом в Btreei, на который указывает tree_addr.
Увеличить поддержку sup на 1 в < sup, hash_addr >.
Переместить < sup, hash_addr > направо, чтобы пройти все листовые входы
< sup’, hash_addr’ > при условии sup’ < sup.
Для каждого входа < sup’, hash_addr’ >, перемещенного в (с), обновить адреса в дереве, содержащем соответствующие входы в Hashi.
Обновить предыдущие входные индексы в < sup, hash_addr > чтобы отразить изменение поддержки, если необходимо.
Когда транзакция t присоединяется к кластеру Ci, MinSupi, поддержка каждого предмета, содержащегося в транзакции, увеличивается на 1. Допустим, что OldMinSupi и MinSupi обозначают минимальную поддержку для Ci перед и после присоединения транзакции к кластеру.
1.4.7 Обновление числа “больших” предметов
Алгоритм для обновления дан на рис.6. Для каждого предмета е в t отыскивается Hashi. Если е найдено хэше кластера, то увеличиваем на 1 его sup в Btreei. Если е не найдено, то вставляем е с sup = 1 в Hashi и Btreei. Это показано в строках (4) – (9).
|Ci| ++; /* размер кластера увеличивается на 1*/
OldMinSupi = MinSupi;
MinSupi = θ * |Ci|;
/* обновление поддержки предметов в t */
foreach item e in t do /* для каждого предмета е в транзакции t выполнить */;
look up Hashi for e /* отыскать Hashi для предмета е */;
if e is found then /* если е найден, то */;
Inc(Ci, e) /* */
else
insert e into Hashi and Btreei with sup = 1
/* малые предметы становятся большими */
if MinSupi = = OldMinSupi then
search Btreei for the items e with sup = MinSupi;
foreach returned item e do /*для каждого возвращенного предмета е выполнить*/
if e is in t then |Largei| ++; /* если е находится в t, то увеличить число больших предметов в кластере Ci на 1*/;
/* большие предметы становятся малыми */
if MinSupi = = OldMinSupi + 1 then
search Btreei for the items e with sup = OldMinSupi;
foreach item e returned do /* для каждого возвращенного предмета е выполнить */
if e is not in t then |Largei| - -; /*если е нет в t, то уменьшить число больших предметов в кластере на 1 */;
Рис. 6 Обновление числа больших предметов при добавлении транзакции в кластер
Малые предметы становятся большими: малый предмет е становится большим, если (а) MinSupi = OldMinSupi, (b) е находится в t, и (с) sup = MinSupi. Этот случай отслеживается в строках (10) – (13).
Большие предметы становятся малыми: большой предмет становится малым, если (а) MinSupi = OldMinSupi + 1, (b) е не находится в t, и (с) sup = OldMinSupi. Этот случай отслеживается в строках (14) – (17).
Для обновления числа элементов в множествах |ki=1Smalli| и |ki=1Largei|
используются две хэш-таблицы LargeHash и SmallHash, чтобы сохранять число кластеров с большими и малыми предметами. Когда малый предмет е становится большим в кластере, его число в SmallHash уменьшается на 1, а его число в LargeHash увеличивается на 1, т.е. эти числа изменяются согласованно. Как только это число достигает 0 в хэш-таблице, соответствующая ячейка удаляется из этой таблицы. Как только новый предмет е добавляется в кластер, новая ячейка с начальным значением 1 вставляется в LargeHash или SmallHash, в зависимости от того, является ли е большим или малым предметом в этом кластере. Когда транзакция t присоединяется к кластеру, изменение числа |ki=1Smalli| (или |ki=1Largei| соответственно) заключается в числе новых вставляемых ячеек минус число ячеек, удаляемых в SmallHash (или LargeHash, соответственно).
В действительной реализации обновление структур данных выполняется только после того, как протестированы все возможные варианты адресации кластеров.
Подобные рассуждения применимы к случаю удаления транзакции из кластера.
2. ПОСТАНОВКА ЗАДАЧИ
2.1 Цель и задачи работы
Цель работы – предложить усовершенствованный метод реализации классического алгоритма LargeItem в части удобства и быстроты поиска кластерных наборов в транзакционных БД большого объема (порядка 100000 транзакций и более). Использовать для этого рекурсивные структуры данных в виде сбалансированного бинарного дерева В+.
Исходя из предложенной цели работы, можно сформулировать следующие задачи дипломной работы:
1) Изучить принцип работы алгоритма LargeItem в первоначальном варианте.
2) Модернизировать алгоритм кластеризации с учетом применения B+ деревьев в его работе.
3) Разработать и протестировать генератор баз данных, используя за основу существующий генератор из работы Кызылов А. В. «Разработка программного обеспечения для реализации и тестирования алгоритма нахождения частых множеств в транзакционных данных вертикального формата» за 2009 год.
4) Реализовать разработанный модернизированный алгоритм на языке Java с применение библиотек для работы со сбалансированными двоичными деревьями поиска.
5) Оценить эффективность предложенного решения на тестовых примерах.
Первоначально произведем разбор таких понятий как двоичное дерево поиска, а также сбалансированное дерево поиска.
2.2 Двоичное дерево поиска
Рис. 7 Пример двоичного дерева поиска
Двоичное дерево поиска ( binary search tree, BST) — это двоичное дерево, для которого выполняются следующие дополнительные условия (свойства дерева поиска):
Оба поддерева — левое и правое, являются двоичными деревьями поиска.
У всех узлов левого поддерева произвольного узла X значения ключей данных меньше, нежели значение ключа данных самого узла X.
В то время, как у всех узлов правого поддерева того же узла X значения ключей данных не меньше, нежели значение ключа данных узла X.
Очевидно, данные в каждом узле должны обладать ключами, на которых определена операция сравнения меньше.
Как правило, информация, представляющая каждый узел, является записью, а не единственным полем данных. Однако, это касается реализации, а не природы двоичного дерева поиска.
Для целей реализации двоичное дерево поиска можно определить так:
Двоичное дерево состоит из узлов (вершин) — записей вида (data, left, right), где data — некоторые данные, привязанные к узлу, left и right — ссылки на узлы, являющиеся детьми данного узла - левый и правый сыновья соответственно. Для оптимизации алгоритмов конкретные реализации предполагают также определения поля parent в каждом узле (кроме корневого) - ссылки на родительский элемент.
Данные (data) обладают ключом (key), на котором определена операция сравнения "меньше". В конкретных реализациях это может быть пара (key, value) - (ключ и значение), или ссылка на такую пару, или простое определение операции сравнения на необходимой структуре данных или ссылке на неё.
Для любого узла X выполняются свойства дерева поиска: key[left[X]] < key[X] ≤ key[right[X]], т. е. ключи данных родительского узла больше ключей данных левого сына и нестрого меньше ключей данных правого.
Двоичное дерево поиска не следует путать с двоичной кучей, построенной по другим правилам.
Основным преимуществом двоичного дерева поиска перед другими структурами данных является возможная высокая эффективность реализации основанных на нём алгоритмов поиска и сортировки.
Двоичное дерево поиска применяется для построения более абстрактных структур, таких как множества, мультимножества, ассоциативные массивы.
2.2.1 Основные операции в двоичном дереве поиска
Базовый интерфейс двоичного дерева поиска состоит из трех операций:
FIND(K) — поиск узла, в котором хранится пара (key, value) с key = K.
INSERT(K,V) — добавление в дерево пары (key, value) = (K, V).
REMOVE(K) — удаление узла, в котором хранится пара (key, value) с key = K.
По сути, двоичное дерево поиска — это структура данных, способная хранить таблицу пар (key, value) и поддерживающая три операции: FIND, INSERT, REMOVE.
Кроме того, интерфейс двоичного дерева включает ещё три дополнительных операции обхода узлов дерева: INFIX_TRAVERSE, PREFIX_TRAVERSE и POSTFIX_TRAVERSE. Первая из них позволяет обойти узлы дерева в порядке неубывания ключей.
Поиск элемента (FIND)
Дано: дерево Т и ключ K.
Задача: проверить, есть ли узел с ключом K в дереве Т, и если да, то вернуть ссылку на этот узел.
Алгоритм:
(1)Если дерево пусто, сообщить, что узел не найден, и остановиться.
(2)Иначе сравнить K со значением ключа корневого узла X.
(3)Если K=X, выдать ссылку на этот узел и остановиться.
(4)Если K>X, рекурсивно искать ключ K в правом поддереве Т.
(5)Если K
Добавление элемента (INSERT)
Дано: дерево Т и пара (K,V).
Задача: добавить пару (K, V) в дерево Т.
Алгоритм:
(1)Если дерево пусто, заменить его на дерево с одним корневым узлом ((K,V), null, null) и остановиться.
(2)Иначе сравнить K с ключом корневого узла X.
(3)Если K>=X, рекурсивно добавить (K,V) в правое поддерево Т.
(4)Если K
Удаление узла (REMOVE)
Дано: дерево Т с корнем n и ключом K.
Задача: удалить из дерева Т узел с ключом K (если такой есть).
Алгоритм:
(1)Если дерево T пусто, остановиться;
(2)Иначе сравнить K с ключом X корневого узла n.
(3)Если K>X, рекурсивно удалить K из правого поддерева Т;
(4)Если K
(5)Если K=X, то необходимо рассмотреть три случая.
(6)Если обоих детей нет, то удаляем текущий узел и обнуляем ссылку на него у родительского узла;
(7)Если одного из детей нет, то значения полей ребёнка m ставим вместо соответствующих значений корневого узла, затирая его старые значения, и освобождаем память, занимаемую узлом m;
(8)Если оба ребёнка присутствуют, то
(9)найдём узел m, являющийся самым левым узлом правого поддерева с корневым узлом Right(n);
(10)скопируем данные (кроме ссылок на дочерние элементы) из m в n;
(11)рекурсивно удалим узел m.
Обход дерева (TRAVERSE)
Есть три операции обхода узлов дерева, отличающиеся порядком обхода узлов.
Первая операция — INFIX_TRAVERSE — позволяет обойти все узлы дерева в порядке возрастания ключей и применить к каждому узлу заданную пользователем функцию обратного вызова f. Эта функция обычно работает только с парой (K,V), хранящейся в узле. Операция INFIX_TRAVERSE реализуется рекурсивным образом: сначала она запускает себя для левого поддерева, потом запускает данную функцию для корня, потом запускает себя для правого поддерева.
INFIX_TRAVERSE ( f ) — обойти всё дерево, следуя порядку (левое поддерево, вершина, правое поддерево).
PREFIX_TRAVERSE ( f ) — обойти всё дерево, следуя порядку (вершина, левое поддерево, правое поддерево).
POSTFIX_TRAVERSE ( f ) — обойти всё дерево, следуя порядку (левое поддерево, правое поддерево, вершина).
INFIX_TRAVERSE:
Дано: дерево Т и функция f
Задача: применить f ко всем узлам дерева Т в порядке возрастания ключей
Алгоритм:
(1)Если дерево пусто, остановиться.
(2)Иначе
(3)Рекурсивно обойти левое поддерево Т.
(4)Применить функцию f к корневому узлу.
(5)Рекурсивно обойти правое поддерево Т.
В простейшем случае, функция f может выводить значение пары (K,V). При использовании операции INFIX_TRAVERSE будут выведены все пары в порядке возрастания ключей. Если же использовать PREFIX_TRAVERSE, то пары будут выведены в порядке, соответствующим описанию дерева, приведённого в начале статьи.
Разбиение дерева по ключу
Операция «разбиение дерева по ключу» позволяет разбить одно дерево поиска на два: с ключами
Балансировка дерева
Всегда желательно, чтобы все пути в дереве от корня до листьев имели примерно одинаковую длину, т.е. чтобы глубина и левого, и правого поддеревьев была примерно одинакова в любом узле. В противном случае теряется производительность.
В вырожденном случае может оказаться, что все левое дерево пусто на каждом уровне, есть только правые деревья, и в таком случае дерево вырождается в список (идущий вправо). Поиск (а значит, и удаление и добавление) в таком дереве по скорости равен поиску в списке и намного медленнее поиска в сбалансированном дереве.
Для балансировки дерева применяется операция "поворот дерева". Поворот направо выглядит так:
Рис. 8
было Left(A) = L, Right(A) = B, Left(B) = C, Right(B) = R
поворот меняет местами A и B, получая Left(A) = L, Right(A) = C, Left(B) = A, Right(B) = R
также меняется в узле Parent(A) ссылка, ранее указывавшая на A, после поворота она указывает на B.
Поворот направо выглядит так же, достаточно заменить в вышеприведенном примере все Left на Right и обратно.
Достаточно очевидно, что поворот не нарушает упорядоченность дерева, и оказывает предсказуемое (+1 или -1) влияние на глубины всех затронутых поддеревьев.
Для принятия решения о том, какие именно повороты нужно совершать после добавления или удаления, используются такие алгоритмы, как «красно-чёрное дерево» и АВЛ.
Оба они требуют дополнительной информации в узлах – 1 бит у красно-черного или знаковое число у АВЛ.
Красно-черное дерево требует <= 2 поворотов после добавления и <= 3 после удаления, но при этом худший дисбаланс может оказаться до 2 раз (самый длинный путь в 2 раза длиннее самого короткого).
АВЛ-дерево требует <= 2 поворотов после добавления и до глубины дерева после удаления, но при этом идеально сбалансировано (дисбаланс не более, чем на 1).
2 .3 B+ дерево
Рис. 9
Пример B+ дерева, связывающего ключи 1-7 с данными d1-d7. Связи (выделены красным) позволяют быстро обходить дерево в порядке возрастания ключей.
B+ дерево — структура данных, представляет собой сбалансированное дерево поиска. Является модификацией B-дерева, истинные значения ключей которого содержатся только в листьях, а во внутренних узлах — ключи-разделители, содержащие диапазон изменения ключей для поддеревьев.
2.3.1 Построение
При построении B+ дерева, его временами приходится перестраивать. Это связано с тем, что количество ключей в каждом узле (кроме корня) должно быть от k до 2k, где k — степень дерева. При попытке вставить в узел (2k+1)-й ключ возникает необходимость разделить этот узел. В качестве ключа-разделителя сформированных ветвей выступает (k+1)-й ключ, который помещается на соседний ярус дерева. Особым же случаем является разделение корня, так как в этом случае увеличивается число ярусов дерева. Особенностью разделения листа B+ дерева является то, что он делится на неравные части. При разделении внутреннего узла или корня возникают узлы с равным числом ключей k. Разделение листа может вызвать «цепную реакцию» деления узлов, заканчивающуюся в корне.
2.3.2 Свойства:
В B+ дереве легко реализуется независимость программы от структуры информационной записи.
Поиск обязательно заканчивается в листе.
Удаление ключа имеет преимущество — удаление всегда происходит из листа.
Другие операции выполняются аналогично B-деревьям.
B+ деревья требуют больше памяти для представления чем B-деревья.
B+ деревья имеют возможность последовательного доступа к ключам.
|
