Дерево ван Эмде Боаса — различия между версиями
(Новая страница: «дерево размер мин макс вершина - дерево для корня из n элементов лист массив от 1 до sqrt(n) из…») |
|||
Строка 1: | Строка 1: | ||
− | дерево | + | ==Структура== |
+ | Пусть есть множество <tex>m[0 .. M-1]</tex> мы хотим записать эти данный в дерево. | ||
+ | В корне будут храниться: массив детей размером sqrt(M), значение текущего минимума и максимума в дерево, а также | ||
+ | вспомогательный массив. | ||
+ | Элемент массива из детей с индексом <tex>i=\lfloor x/M^{1/2}\rfloor</tex> является также деревом для элементов <tex>[i*M^1/2 .. (i+1)M^1/2 - 1]</tex> | ||
+ | В вспомогательном дереве хранится информация о том какие клетки уже заняты. То есть значение о хранится в вспомогательном дереве только если занят элемент с индексом j в массиве детей. | ||
− | |||
− | |||
− | |||
− | |||
+ | Рассмотрим две опeрации | ||
+ | Insert(x) | ||
+ | Delete(x) | ||
+ | ==Insert== | ||
+ | операция добавления(insert)пусть добавляем мы элемент <tex>x</tex> | ||
+ | Если дерево пусто, то меняем значения минимума и максимума на x; | ||
+ | Если x<T.min тогда мы кладем T.min в поддерево i соответствующее T.min и ставим T.min = x. Если поддерево[i] до этого было пусто то мы также добавляем i в вспомогательное дерево. | ||
+ | Аналогично если x>T.max. | ||
+ | Если T.min< x < T.max тогда кладем x в поддерево i соответствующее x и меняем вспомогательное дерево. | ||
+ | <pre> | ||
+ | Insert(T, x) | ||
+ | if (T.min > T.max) // T is empty | ||
+ | T.min = T.max = x; | ||
+ | return | ||
+ | if (T.min = T.max) | ||
+ | if (x < T.min) | ||
+ | T.min = x; | ||
+ | if (x > T.max) | ||
+ | T.max = x; | ||
+ | return | ||
+ | if (x < T.min) | ||
+ | swap(x, T.min) | ||
+ | if (x > T.max) | ||
+ | swap(x, T.max) | ||
+ | i = x/sqrt(M) | ||
+ | Insert(T.children[i], x % sqrt(M)) | ||
+ | if (T.children[i].min = T.children[i].max) | ||
+ | Insert(T.aux, i) | ||
+ | </pre> | ||
+ | ==Delete== | ||
+ | Если T.min = T.max = x, значит в дереве один элемент, мы его удалим и как-нибудь пометим, что дерево пусто(на будущее). | ||
+ | Если x = T.min,то мы должны найти следующий второй минимум удалить его из того места где он находится и поставить в T.min Второй минимум - это либо T.max, либо T.children[T.aux.min].min. | ||
+ | Аналогично для случая x = T.max | ||
+ | Если же x = T.min и x = T.max, то мы должны удалить x из поддерева i отвечающего x. | ||
+ | Важно, что Delete реализован рекурсивно от дерева в котором идет удаления. | ||
+ | Так же нельзя забывать, что если мы удаляем последнее вхождение x, то мы должны удалить i из вспомогательного дерева. | ||
− | + | <pre> | |
− | + | Delete(T, x) | |
+ | if (T.min == T.max == x) | ||
+ | T.min = M | ||
+ | T.max = -1 | ||
+ | return | ||
+ | if (x == T.min) | ||
+ | if (T.aux is empty) | ||
+ | T.min = T.max | ||
+ | return | ||
+ | else | ||
+ | x = T.children[T.aux.min].min | ||
+ | T.min = x | ||
+ | if (x == T.max) | ||
+ | if (T.aux is empty) | ||
+ | T.max = T.min | ||
+ | return | ||
+ | else | ||
+ | x = T.children[T.aux.max].max | ||
+ | T.max = x | ||
+ | if (T.aux is empty) | ||
+ | return | ||
+ | i = floor(x/sqrt(M)) | ||
+ | Delete(T.children[i], x%sqrt(M)) | ||
+ | if (T.children[i] is empty) | ||
+ | Delete(T.aux, i) | ||
+ | </pre> |
Версия 20:54, 15 июня 2011
Структура
Пусть есть множество
мы хотим записать эти данный в дерево. В корне будут храниться: массив детей размером sqrt(M), значение текущего минимума и максимума в дерево, а также вспомогательный массив. Элемент массива из детей с индексом является также деревом для элементов В вспомогательном дереве хранится информация о том какие клетки уже заняты. То есть значение о хранится в вспомогательном дереве только если занят элемент с индексом j в массиве детей.
Рассмотрим две опeрации
Insert(x)
Delete(x)
Insert
операция добавления(insert)пусть добавляем мы элемент
Если дерево пусто, то меняем значения минимума и максимума на x; Если x<T.min тогда мы кладем T.min в поддерево i соответствующее T.min и ставим T.min = x. Если поддерево[i] до этого было пусто то мы также добавляем i в вспомогательное дерево. Аналогично если x>T.max. Если T.min< x < T.max тогда кладем x в поддерево i соответствующее x и меняем вспомогательное дерево.Insert(T, x) if (T.min > T.max) // T is empty T.min = T.max = x; return if (T.min = T.max) if (x < T.min) T.min = x; if (x > T.max) T.max = x; return if (x < T.min) swap(x, T.min) if (x > T.max) swap(x, T.max) i = x/sqrt(M) Insert(T.children[i], x % sqrt(M)) if (T.children[i].min = T.children[i].max) Insert(T.aux, i)
Delete
Если T.min = T.max = x, значит в дереве один элемент, мы его удалим и как-нибудь пометим, что дерево пусто(на будущее). Если x = T.min,то мы должны найти следующий второй минимум удалить его из того места где он находится и поставить в T.min Второй минимум - это либо T.max, либо T.children[T.aux.min].min. Аналогично для случая x = T.max Если же x = T.min и x = T.max, то мы должны удалить x из поддерева i отвечающего x. Важно, что Delete реализован рекурсивно от дерева в котором идет удаления. Так же нельзя забывать, что если мы удаляем последнее вхождение x, то мы должны удалить i из вспомогательного дерева.
Delete(T, x) if (T.min == T.max == x) T.min = M T.max = -1 return if (x == T.min) if (T.aux is empty) T.min = T.max return else x = T.children[T.aux.min].min T.min = x if (x == T.max) if (T.aux is empty) T.max = T.min return else x = T.children[T.aux.max].max T.max = x if (T.aux is empty) return i = floor(x/sqrt(M)) Delete(T.children[i], x%sqrt(M)) if (T.children[i] is empty) Delete(T.aux, i)