Ответ 1
Причина каскадного сокращения заключается в том, чтобы D (n) был низким. Оказывается, что если вы разрешаете любое количество узлов быть отрезанным от дерева, то D (n) может расти линейным, что делает удаление и удаление-min линейным.
Интуитивно, вы хотите, чтобы число узлов в дереве порядка k было экспоненциальным по k. Таким образом, вы можете иметь логарифмически много деревьев в консолидированной куче. Если вы можете вырезать произвольное количество узлов из дерева, вы потеряете эту гарантию. В частности, вы могли бы взять дерево порядка k, а затем разрезать всех своих внуков. Это оставляет дерево с k детьми, каждый из которых - листья. Следовательно, вы можете создавать деревья порядка k с помощью всего k + 1 тотальных узлов в них. Это означает, что в худшем случае вам понадобится дерево порядка n - 1 для хранения всех узлов, поэтому D (n) станет n - 1, а не O (log n).
Надеюсь, это поможет!