Редактирование: Взвешенное дерево
Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.
Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия | Ваш текст | ||
Строка 188: | Строка 188: | ||
Удаляется элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей). | Удаляется элемент из дерева обычным удалением вершины бинарного дерева поиска (поиск элемента, удаление, возможное переподвешивание детей). | ||
Далее следует проверка выполнения условия: | Далее следует проверка выполнения условия: | ||
− | :<tex> | + | :<tex>weight[T] < \alpha \cdot \mathtt {maxweight[T]}</tex>; |
Если оно выполняется — дерево могло потерять <tex>\alpha</tex>-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить: | Если оно выполняется — дерево могло потерять <tex>\alpha</tex>-балансировку по весу, а значит нужно выполнить полную перебалансировку дерева (начиная с корня) и присвоить: | ||
− | :<tex>\mathtt {maxweight[T]} = | + | :<tex>\mathtt {maxweight[T]} = weight[T]</tex>; |
====Псевдокод==== | ====Псевдокод==== |