В этом упражнении студенту предлагается удалить узел из дерева AVL. В данном случае это требует некоторой балансировки, так как разница между самой большой и самой мелкой глубиной> 1. Но должна ли балансировка происходить до или после удаления? Или все равно?
сбалансировать дерево AVL до или после удаления узла?
Ответы (1)
По сути, вы хотите удалить, как в BST. Затем вычислите свой коэффициент глубины (какова длина каждого пути в дереве) и выполните повороты, как обычно, со вставками, в зависимости от того, какие пути не сбалансированы. Итак, чтобы ответить на ваш вопрос, вы делаете ротацию после удаления.
person
Jay
schedule
11.11.2016