Вычисление коэффициента баланса узла в дереве avl

Я хочу вычислить коэффициент баланса узла в дереве avl без использования какой-либо рекурсивной процедуры. Как я могу это сделать? Пожалуйста, сообщите мне метод или предоставьте фрагмент кода C++.

Источник

2 ответа

Решение

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

Пример:

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. Эта вставка является рекурсивной, и я не знаю, является ли это проблемой для вас. Также во время балансировки вы должны обновить высоты и, возможно, снова с рекурсией.

Я надеюсь, что это поможет вам. Если нет, укажите проблему с рекурсией - время, память,... и мы можем попытаться найти лучшее решение

Источник
Другие вопросы по тегам