Я хочу увеличить двоичное дерево поиска, чтобы поиск, вставка и удаление сохранялись в O (h), а затем Я хочу реализовать алгоритм для нахождения суммы всех значений узлов в заданном диапазоне.Найдите сумму узлов в двоичном дереве поиска, значение которого находится в определенном диапазоне, дополняя BST
Если вы добавите дополнительную структуру данных в свой класс BST, в частности, Hashmap или Hashtable. Ваши keys будут разными номерами вашего BST и вашим values количеством вхождений для каждого. BST search(...) не будет влиять, однако insert(...) и delete(...) потребуют незначительных изменений кода.
Вставка
При добавлении узлов к проверке BST, чтобы увидеть, что если значение существует в Hashmap в качестве ключа. Если существует приращение счетчика вхождений на 1. Если он не существует добавить его в Hashmap с начальным значением 1.
Удалить
При удалении уменьшает количество вхождений в Hashmap (предполагается, что ваш не говорят, чтобы удалить узел, который не существует)
Sum
Теперь для суммы F соборование
sum(int start, int end)
Вы можете итеративно проверить HashMap, чтобы увидеть, какие существуют числа из диапазона в вашей карте и их количество вхождений. Используя это, вы можете построить свою сумму, суммируя все значения на карте, которые находятся в диапазоне, умноженном на их количество вхождений.
Сложности
пространство: О (п) Время метода Сумма: O (размер диапазона).
На все остальные временные сложности не влияет.
Вы не упомянули о смене места, поэтому, надеюсь, все в порядке. Мне очень интересно узнать, можете ли вы каким-то образом использовать свойства BST для решения этого более эффективно, для меня ничего не приходит в голову.
Звучит великолепно. Что вы пробовали? С какой частью у вас проблемы. Существует уже много документации о бинарных деревьях, на которые вы можете ссылаться. – miltonb
Ну, я огляделся, и единственное, что было близко к этой проблеме, я нашел, используя дерево сегментов, которое не является дополнением. Я также нашел решение, которое в основном использовало дерево AVL. Но я хочу увеличить BST, а затем найти сумму узлов в узком диапазоне. Я попытался добавить кумулятивную сумму к каждому узлу снизу вверх, но после этого я застрял. На самом деле я понятия не имею. –