251
правка
Изменения
Форматирован псевдокод
=== empty ===
Чтобы определить, пусто ли дерево, будем изначально инициализировать поле <tex>min</tex> числом, которое не лежит в интервале <tex>[0;2^k)</tex>. Назовем это число <tex>none</tex>. Например, это может быть <tex>-1</tex>, если мы храним в числа в знаковом целочисленном типе, или <tex>2^k</tex>, если в беззнаковом. Тогда проверка на пустоту дерева будет заключаться лишь в сравнении поля <tex>min</tex> с этим числом.
<precode> '''boolean''' empty(Tt: '''Tree''') '''if T''' t.min == none '''return ''' true; '''else''' '''return ''' false;</precode>
=== min и max ===
*иначе ищем число <tex>\mathtt{low(x)}</tex> в поддереве <tex>children[\mathtt{high(x)}]</tex>.
<precode> '''boolean''' find(Tt: '''Tree''', x: '''int''') '''if ''' empty(Tt) '''return ''' false; '''if T''' t.min == x '''or T''' t.max == x '''return ''' true; '''return ''' find(Tt.children[high(x)], low(x));</precode>
Заметим, что выполняя операцию <tex>\mathtt{find}</tex>, мы либо спускаемся по дереву на один уровень ниже, либо, если нашли нужный нам элемент, выходим из нее. В худшем случае мы спустимся от корня до какого-нибудь 1-дерева, то есть выполним операцию <tex>\mathtt{find}</tex> столько раз, какова высота нашего дерева. На каждом уровне мы совершаем <tex>O(1)</tex> операций. Следовательно время работы <tex>O(\log k)</tex>.
**вставим число <tex>\mathtt{low(x)}</tex> в поддерево <tex>children[\mathtt{high(x)}]</tex>, за исключением ситуации, когда текущее дерево {{---}} это 1-дерево, и дальнейшая вставка не требуется.
<precode> '''function''' insert(Tt: '''Tree''', x: '''int''') '''if ''' empty(Tt) // проверка на пустоту текущего дерева Tt.min = x; Tt.max = x; '''else''' '''if T''' t.min == Tt.max // проверка, что в дереве один элемент '''if ''' T.min < x Tt.max = x; '''else''' Tt.min = x; '''else''' '''if T''' t.min > x swap(Tt.min, x); // релаксация минимума '''if T''' t.max < x swap(Tt.max, x); // релаксация максимума '''if T''' t.k != 1 '''if ''' empty(Tt.children[high(x)]) insert(Tt.aux, high(x)); // вставка high(x) во вспомогательно дерево aux insert(Tt.children[high(x)], low(x)); // вставка low(x) в поддерево children[high(x)]</precode>
Нетрудно увидеть, что данная операция работает за время <tex>O(\log k)</tex>. На каждом уровне дерева мы выполняем <tex>O(1)</tex> операций. После этого возможны 2 случая: поддерево <tex>children[\mathtt{high(x)}]</tex> пусто, и мы будем производить дальнейшую вставку и в него, и во вспомогательное дерево <tex>aux</tex>, или же поддерево не пусто, и мы просто спустимся на уровень ниже. Но если поддерево <tex>children[\mathtt{high(x)}]</tex> пусто, то вставка в него будет выполнена за <tex>O(1)</tex>, так как мы всего лишь обновим поля <tex>min</tex> и <tex>max</tex>. Все остальные операции будут выполнятся уже со вспомогательным деревом <tex>aux</tex>, высота которого на 1 уровень меньше, чем высота текущего. Если же поддерево <tex>children[\mathtt{high(x)}]</tex> не пусто, то мы просто перейдем к вставке элемента в это поддерево, высота которого так же на 1 меньше, чем у текущего. В итоге, каждый раз, выполнив <tex>O(1)</tex> операций, мы переходим к дереву, высота которого на 1 меньше, чем у текущего. Следовательно, количество операций пропорционально высоте дерева, которая, как уже было показано, <tex>O(\log k)</tex>. То есть операция вставки займет <tex>O(\log k)</tex> времени.
Так как в поддеревьях хранятся не все биты исходных элементов, а только часть их, то для восстановления исходного числа, по имеющимся старшим и младшим битам, будем использовать функцию <tex> merge </tex>. Также нельзя забывать, что если мы удаляем последнее вхождение <tex>x</tex>, то мы должны удалить <tex>\mathtt{high(x)}</tex> из вспомогательного дерева.
<precode> '''function''' remove(Tt: '''Tree''', x: '''int''') '''if T''' t.min == x '''and T''' t.max == x // случай, когда в дереве один элемент Tt.min = none; '''return'''; '''if T''' t.min == x '''if ''' empty(Tt.aux) Tt.min = Tt.max; '''return'''; x = merge(Tt.aux.min, Tt.children[Tt.aux.min].min); T t.min = x; '''if T''' t.max == x '''if ''' empty(Tt.aux) Tt.max = Tt.min; '''return'''; '''else''' x = merge(Tt.aux.max, Tt.children[Tt.aux.max].max); Tt.max = x; '''if ''' empty(Tt.aux) // случай, когда элемента x нет в дереве '''return'''; remove(Tt.children[high(x)], low(x)); '''if ''' empty(Tt.children[high(x)]) // если мы удалили из поддерева последний элемент remove(Tt.aux, high(x)); // то удаляем информацию, что это поддерево не пусто</precode>
Оценка времени работы операции <tex>\mathtt{remove}</tex> такая же, как и у операции <tex>\mathtt{insert}</tex>. На каждом уровне дерева мы совершаем <tex>O(1)</tex> операций и переходим к удалению элементов максимум в двух деревьях(в одном поддереве и во вспомогательном дереве), чьи высоты на один меньше текущей. Но если мы производим операцию удаления из вспомогательного дерева, значит удаление из поддерева потребовало <tex>O(1)</tex> операций, так как оно содержало всего один элемент. В итоге, количество операций пропорционально высоте дерева, то есть <tex>O(\log k)</tex>.
**иначе искомым элементом является либо минимум следующего непустого поддерева, если такое есть, либо максимум текущего дерева в противном случае.
<precode> '''int''' next(Tt: '''Tree''', x: '''int''') '''if ''' empty(Tt) '''or T''' t.max <= x '''return none''' -1; // следующего элемента нет '''if T''' t.min > x '''return T''' t.min; '''if ''' empty(Tt.aux) '''return T''' t.max; // в дереве не более двух элементов '''else''' '''if ''' '''not ''' empty(Tt.children[high(x)]) '''and T'''t.childen[high(x)].max > low(x) '''return ''' merge(high(x), next(Tt.children[high(x)], low(x))); // случай, когда следующее число начинается с high(x) '''else ''' // иначе найдем следующее непустое поддерево '''int''' nextHigh = next(Tt.aux, high(x)); '''if ''' nextHigh == null-1 '''return T''' t.max; // если такого нет, вернем максимум '''else''' '''return ''' merge(nextHigh, Tt.children[nextHigh].min); // если есть, вернем минимум найденного поддерева</precode>
Время работы, как и всех предыдущих функций, оценивается так же, и равно <tex>O(\log k)</tex>. Функция <tex>\mathtt{prev} </tex> реализуется аналогично.
