Алгоритм подсчета количества узлов в дереве AVL

Question

Примите следующие обозначения / операции над деревьями AVL.Пустое дерево AVL обозначено E. Непустое дерево AVL T имеет три атрибута:

• Ключ T.key является ключом корневого узла.

• Левый дочерний элемент T.leftявляется левым поддеревом T, которое является деревом AVL (возможно, E).

• Правым дочерним T.right является правое поддерево T, которое является деревом AVL (возможно, E).

Я пытаюсь написать алгоритм (псевдокод будет делать) Count (T, lo, hi), который считает и возвращает количество узлов в дереве AVL с корнем T, где значение ключа находится в диапазоне lo ≤ keyHi привет.Я хочу, чтобы он имел временную сложность O (n), где n - это количество узлов в дереве AVL T. У меня была одна идея - рекурсия, но, похоже, она не имела необходимой сложности.Есть идеи?

Answer 1

Вы можете добавить глобальную переменную, например, счетчик, выполнить итерацию дерева с помощью Предварительный заказ , стоимость (n + e) ​​и добавить 1 для каждого узла.

Вы можететакже добавьте счетчик, и когда добавляете новый узел внутри структуры данных, вы можете добавить 1, а если вы удалите узел, вы можете вычесть 1