Случаи, когда высота правого поддерева узла превосходит допустимое значение, аналогичны рассмотренным.
|
2 |
|
8 |
|
5 |
|
Рис.13а |
|
6 |
|
10 |
|
16 |
|
2 |
|
8 |
|
5 |
|
Рис.13б |
|
6 |
|
10 |
|
16 |
|
1 |
Также следует заметить, что балансировка Н. Вирта работает только тогда, когда баланс любого узла дерева выходит за пределы допустимого диапазона не далее чем на единицу, то есть такая логика применима лишь для последовательной вставки/удаления узлов. Но сбалансированные деревья изначально были созданы для организации баз данных, где может встать задача об удалении узла и всех его потомков, или ее можно сформулировать как удаление узлов, ключи которых лежат в заданном диапазоне. Последовательное удаление узлов из дерева не только требовательно к времени (так как возможны невостребованные повороты), но и, скорее всего, потребует создания списка удаляемых узлов, так как после удаления одного узла потомок узла может стать его предком, что делает невозможным дальнейшее удаление без предварительно составленного списка. Таким образом, данная логика еще и требовательна к памяти. Предлагаемая же логика легко оптимизируется под задачи такого типа путем простого зацикливания процедуры балансировки, то есть необходимо выполнять балансировку до восстановления допустимого баланса узла.
Похожие статьи
- бестарифная система оплаты труда
- коэффициент роста производительности труда
- структурная схема работы лексического анализатора
- rsl режимы программы
- седло и узел на фазовой плоскости