Обсуждение статьи "От начального до среднего уровня: Очереди, списки и деревья (VIII)"

Новый комментарий
 

Опубликована статья От начального до среднего уровня: Очереди, списки и деревья (VIII):

В этой статье мы рассмотрим, как реализовать алгоритм балансировки дерева. Здесь я представлю свой вариант реализации этого алгоритма. Существует множество других алгоритмов с той же целью. Тем не менее, у каждого из них есть свои преимущества и недостатки. Вам, мой дорогой читатель, предстоит изучить их и найти тот, который лучше всего соответствует вашим потребностям.

В предыдущей статье «От базового к среднему уровню: очереди, списки и деревья (VII)» мы объяснили один из многих возможных способов удаления узла из дерева. Эту операцию нужно очень хорошо понимать, чтобы работать с деревьями, предназначенными для разных целей. Как мы уже упоминали в предыдущей статье, существуют и другие способы реализовать удаление. Однако, на мой взгляд, показанный там вариант — один из самых простых среди тех, которые не используют рекурсию. При удалении узлов следует избегать рекурсии, поскольку, если потребуется удалить несколько данных, хранящихся в очень глубоких узлах, придётся поместить в стек множество вызовов, чтобы добраться до каждого узла, а затем снять их со стека. Такой рекурсивный обход требует значительных вычислительных затрат и увеличивает время, необходимое для выполнения операций построения и обслуживания дерева.

Итак, нужно понять всё изложенное. Аналогичным образом операцию поиска нужно проектировать очень тщательно, чтобы не допустить ненужного увеличения времени её выполнения. Однако здесь возникает дополнительная сложность: необходимо поддерживать балансировку дерева. Понимание этого вопроса не менее важно, а возможно, даже важнее, чем понимание алгоритмов вставки, удаления и поиска, уже реализованных или ещё только подлежащих реализации.

Итак, в этой статье мы рассмотрим, что означает балансировать дерево и почему это так важно. Кроме того, мы начнём понимать, почему иногда мы не можем или не должны выполнять ребалансировку дерева — вопрос, практическое применение которого будет рассмотрено в другой статье, — хотя в структуре и сохраняется разница в высоте между некоторыми поддеревьями. Этот структурный дисбаланс может удлинить некоторые обходы, но сам по себе не является мерой времени выполнения. Поиск, вставка или удаление будут выполняться быстрее или медленнее в зависимости от пути, по которому проходит операция, и количества узлов, которые нужно посетить. В любом случае перейдём к основной теме этой статьи.


Автор: CODE X

Новый комментарий