Я хочу рассчитать коэффициент баланса узла в дереве avl без использования какой-либо рекурсивной процедуры. Как я могу это сделать? Пожалуйста, скажите мне метод или предоставите фрагмент кода на C++.Расчет коэффициента баланса узла в дереве avl
Вы можете сохранить коэффициент баланса как часть информации, которую сохраняет каждый узел. В частности, вы можете сохранить высоту левого и правого поддеревьев и обновить значения с каждой вставкой/удалением по пути вставки/удаления.
Пример:
class Node {
public:
// stuff...
int GetBF() { return lHeight - rHeight; }
private:
int data;
Node* right;
Node* left;
Node* parent; // optional...
int rHeight; // Height of the right subtree
int lHeight; // Height of the left subtree
};
Без рекурсии может быть немного сложнее, но вы можете сохранить высоту узла в каждом узле. Тогда вы можете получить сбалансированный коэффициент в постоянное время (разница между левым и правым высотами ребенка, если ребенок равен NULL, тогда высота равна 0).
Будет сложно обновить это число. Когда вы вставляете узел, вы должны обновлять все высоты на пути, но не каждый. Высота всегда равна max (высота левого ребенка, высота ребенка) + 1. Эта вставка является рекурсивной, и я не знаю, является ли это проблемой для вас. Также во время балансировки вы должны обновлять высоты и, возможно, снова с рекурсией.
Я надеюсь, что это вам поможет. Если нет, укажите проблему с рекурсией - время, память, ... и мы можем попытаться найти лучшее решение.
Точка для вас, вы быстрее. Я писал свое решение слишком долго, но у нас есть такая же идея. Но я думаю, что в этом решении потребуется рекурсивное обновление во время вставки, и это может быть проблемой, потому что в требованиях «без рекурсии» – Gaim
@Gaim. В любом случае, вставка в дерево AVL должна проходить все узлы в путь вставки. Неважно, если вы пишете рекурсивную или итеративную функцию для этого (рекурсивный вариант будет проще реализовать). Эти узлы являются единственными, чей коэффициент баланса изменяется, поэтому тогда будут обновляться rHight и lHeight. Если у вас есть определенный узел - вычисление коэффициента баланса выполняется в O (1). – Anna