Изменения

Перейти к: навигация, поиск

Дерево ван Эмде Боаса

419 байт добавлено, 01:58, 8 апреля 2012
remove
== remove ==
Удаление из дерева T также делится на несколько подзадач:*Если T.<tex> min </tex> = T.<tex> max </tex> = <tex> x</tex>, значит в дереве один элемент, мы удалим его удалим и как-нибудь пометимотметим, что дерево пусто(на будущее).*Если <tex> x = T.min</tex>,то мы должны найти следующий второй минимум минимальный элемент в этом дереве, присвоить <tex>min</tex> значение второго минимального элемента и удалить его из того места , где он находится и поставить в Tхранится.min Второй минимум {{--- }} это либо T.<tex> max</tex>, либо T.<tex> children[T.aux.min].min.Аналогично </tex> (для случая <tex> x = T.max</tex> действуем аналогично)*Если же <tex> x = T.\neq min </tex> и <tex> x = T.\neq max</tex>, то мы должны удалить <tex>low(x )</tex> из поддерева i отвечающего <tex>children[high(x)]</tex>. Важно, что Delete реализован рекурсивно от дерева в котором идет удаления.Так же нельзя Нельзя забывать, что если мы удаляем последнее вхождение <tex>x</tex>, то мы должны удалить i <tex>high(x)</tex> из вспомогательного дерева.
<pre>
Deleteremove(T, x) if (T.min == x and T.max == x) // случай, когда в дереве один элемент T.min = Mnone; return; if T.max min == -1x if empty(T.aux) T.min = T.max; return; if ( x =T.children[T.aux.min].min; T.min = x; if T.min)max == x if empty(T.aux is empty) T.min max = T.maxmin; 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 empty(T.aux is empty) // случай, когда элемента x нет в дереве return; i = floor(x/sqrt(M)) Deleteremove(T.children[ihigh(x)], low(x%sqrt(M)); if empty(T.children[ihigh(x)] is empty) // если мы удалили из поддерева последний элемент Deleteremove(T.aux, ihigh(x))wikipedia.org; // то удаляем информацию, что это поддерево не пусто
</pre>
 
== next и prev ==
403
правки

Навигация