Изменения

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

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

371 байт добавлено, 22:14, 25 мая 2012
remove
*если <tex> x = min </tex>, то мы должны найти следующий минимальный элемент в этом дереве, присвоить <tex>min</tex> значение второго минимального элемента и удалить его из того места, где он хранится. Второй минимум {{---}} это либо <tex> max </tex>, либо <tex> children[aux.min].min </tex> (для случая <tex> x = max </tex> действуем аналогично).
*если же <tex> x \neq min </tex> и <tex> x \neq max </tex>, то мы должны удалить <tex>low(x)</tex> из поддерева <tex>children[high(x)]</tex>.
Нельзя Так как в поддеревьях хранятся не все биты исходных элементов, а только часть их, то для восстановления исходного числа, по имеющимся старшим и младшим битам, будем использовать функцию <tex> merge </tex>. Также нельзя забывать, что если мы удаляем последнее вхождение <tex>x</tex>, то мы должны удалить <tex>high(x)</tex> из вспомогательного дерева.
<pre>
403
правки

Навигация