Изменения

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

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

Нет изменений в размере, 00:47, 10 апреля 2012
remove
== remove ==
Удаление из дерева также делится на несколько подзадач:
*Если если <tex> min </tex> = <tex> max </tex> = <tex> x </tex>, значит в дереве один элемент, удалим его и отметим, что дерево пусто*Если если <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>x</tex>, то мы должны удалить <tex>high(x)</tex> из вспомогательного дерева.
403
правки

Навигация