РБ дерево с суммой
У меня есть несколько вопросов об увеличении структур данных:
Пусть S = {k1, . , , , kn} будет набором чисел. Разработайте эффективную структуру данных для S, которая поддерживает следующие две операции:
Вставка (S, k), которая вставляет число k в S (можно предположить, что k еще не содержится в S), и TotalGreater(S, a), который возвращает сумму всех ключей ki ∈ S, которые больше, чем a, то есть P ki∈S, ki> a ki.
Аргументируйте время выполнения обеих операций и приведите псевдокод для TotalGreater(S, a) (не указывайте псевдокод для Insert (S, k)).
Я не понимаю, как это сделать, я думал о добавлении дополнительного поля к RB-дереву, называемому sum, но тогда это не работает, потому что иногда мне нужна только сумма левых узлов, а иногда мне нужна сумма правых узлов тоже.
Поэтому я думал о добавлении 2 полей с именами leftSum и rightSum, и если текущий узел> GivenValue, то добавьте кешированное значение суммы подузлов к текущему значению суммы.
Может кто-нибудь помочь мне с этим?
2 ответа
Вы можете просто добавить переменную size к каждому узлу, который является числом узлов в поддереве с корнем в этом узле. При поиске узла с наименьшим значением, превышающим значение aна пути к этому узлу могут произойти две вещи: вы можете пойти налево или направо. Каждый раз, когда вы идете налево, вы добавляете размер правого ребенка + 1 к промежуточной сумме. Каждый раз, когда вы идете прямо, вы ничего не делаете.
Есть два условия для прекращения. 1) находим узел, содержащий точное значение a, в этом случае мы добавляем размер его правильного дочернего элемента к общему количеству. 2) мы достигаем листа, и в этом случае мы добавляем 1, если он больше, чем aили ничего, если оно меньше.
Как описывает Джорди: Ключевое слово может быть дополнено красно-черным деревом.