Range Sum of BST

Q: Какова временная сложность Range Sum of BST?

Обход, который использует порядок дерева поиска для отсечения ветвей, посещает k узлов в диапазоне, а также узлы не более чем на двух путях от корня; для дерева глубины h это занимает время O(h + k) . В худшем случае, когда каждое значение входит в диапазон, это O(n) . Дополнительная память составляет O(h) для стека или рекурсии.

Q: Почему можно пропускать поддеревья в Range Sum of BST?

В бинарном дереве поиска каждое значение слева от узла меньше его значения, а каждое значение справа — больше. Если значение узла не превышает low , ничто слева от него не может попасть в диапазон, а если оно не меньше high , ничто справа от него не может попасть в диапазон. Пропуская эти стороны, вы не пропустите ни одного значения из диапазона.

Q: Можно ли решить задачу Range Sum of BST с помощью симметричного обхода?

Да. Симметричный обход двоичного дерева поиска перечисляет значения в возрастающем порядке, поэтому можно складывать значения, как только они достигают low , и остановиться, как только значение превысит high . Результат будет тем же, а ранняя остановка позволяет сэкономить работу в правой части дерева, тогда как отсечение ветвей также экономит работу в левой части.

Q: Следует ли использовать рекурсию или стек для вычисления суммы в диапазоне BST?

Оба варианта работают. Рекурсивный вариант короче, а здесь глубина составляет не более 14, поэтому стек вызовов остаётся небольшим. Явный стек полностью позволяет избежать ограничения рекурсии, что важно для высокого дерева с тысячами уровней; именно его используют решения на этой странице.

ЛегкоДвоичное дерево поиска Обход деревьев

+10

Дано бинарное дерево поиска, хранящееся в массиве tree в порядке уровней, и два числа low и high. Корень находится по индексу 0, дочерние узлы узла с индексом i находятся по индексам 2*i+1 (левый) и 2*i+2 (правый), -1 обозначает пустое место, а в конце массива могут быть дополнительные элементы -1. В бинарном дереве поиска каждое значение в левом поддереве узла меньше значения этого узла, а каждое значение в его правом поддереве больше.

Напишите функцию с именем rangeSumBST, которая возвращает сумму значений всех узлов v, для которых low ≤ v ≤ high, или 0, если в этом диапазоне нет значений.

Функция

rangeSumBST(tree: integer-array, low: integer, high: integer) → integer

treeinteger-array: двоичное дерево поиска в порядке по уровням, где -1 обозначает пустое место
lowinteger: наименьшее значение для подсчёта
highinteger: наибольшее значение для подсчёта
Возвращаетinteger: сумма значений узлов от low до high включительно

Ограничения

1 ≤ tree.length ≤ 32767
Каждый tree[i] равен -1 или является значением, для которого 0 ≤ tree[i] ≤ 10⁵.
tree[0] никогда не равно -1, поэтому в дереве есть как минимум один узел.
После последнего узла в массиве могут быть дополнительные элементы -1.
Оба потомка пустого места тоже пусты, а глубина не превышает 14.
Дерево является корректным двоичным деревом поиска, поэтому все его значения различны.
0 ≤ low ≤ high ≤ 10⁵
Ответ помещается в 32-разрядное целое число со знаком.

Примеры

Ввод: tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]low = 9high = 31
Вывод: 88
Пояснение: Значения от 9 до 31 — это 10, 12, 15, 20 и 31, в сумме дающие 88. 3, 8 и 40 находятся за пределами диапазона.

Ввод: tree = [50, 25, 75, -1, -1, -1, -1]low = 60high = 70
Вывод: 0
Пояснение: В дереве хранятся 25, 50 и 75, и ни одно из этих значений не находится между 60 и 70, поэтому сумма равна 0. Четыре значения -1 обозначают пустые места для потомков у 25 и 75.

Ввод: tree = [6, 2, 9, 1, 4, 7]low = 4high = 4
Вывод: 4
Пояснение: Когда и low, и high равны 4, учитывается только узел со значением 4. 4 с индексом 4 — правый потомок 2, поэтому ответ — 4.

+14 скрытых тестов при отправке

Дополнительный вопрос

Если бы тебе нужно было отвечать на тысячи разных запросов (low, high) для одного и того же дерева, как бы ты мог отвечать на каждый из них за время O(log n)?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Сложение всех значений в диапазоне — это простой обход: посетите каждый узел и оставьте те, которые подходят. Порядок узлов в дереве поиска позволяет сделать это эффективнее. Значение узла подсказывает, с какой стороны находятся меньшие и большие значения, поэтому целые поддеревья можно пропустить, не заглядывая ни в один узел внутри них.

Посетите каждый узел

Идея

Сначала — как перемещаться по массиву. Узел с индексом i имеет левого потомка с индексом 2*i+1, а правого — с индексом 2*i+2. Потомок считается существующим, только если его индекс находится в пределах массива и значение по этому индексу не равно -1. В массиве [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15] у корня 20 есть потомки 8 и 31 с индексами 1 и 2; у узла 12 с индексом 4 есть потомки 10 и 15 с индексами 9 и 10, а у узла 31 левое место пусто — индекс 5.

Теперь перейдём к идее. Каждое значение из диапазона находится в каком-то узле, поэтому обход, который достигает каждого узла и складывает значения, удовлетворяющие условию low ≤ v ≤ high, даст нужную сумму. Используйте стек индексов узлов. Начните с корня, извлеките индекс, прибавьте значение, если оно входит в диапазон, и добавьте в стек каждого существующего потомка.

При этом свойство дерева поиска полностью игнорируется: этот способ работает с любым бинарным деревом. Он затрагивает все n узлов, время выполнения — O(n), а в стеке хранятся ожидающие обработки потомки вдоль одного пути, поэтому для дерева глубины h требуется O(h) памяти. Если диапазон охватывает несколько значений в дереве из тысяч узлов, большая часть этой работы выполняется впустую.

Алгоритм

Поместите индекс корня 0 в стек и задайте total = 0.
Извлеките индекс i. Если low ≤ tree[i] ≤ high, добавьте tree[i] к total.
Добавьте 2*i+1 и 2*i+2 в стек, если они находятся в пределах массива и не равны -1.
Когда стек опустеет, верните total.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        if left < n and tree[left] != -1:
            stack.append(left)
        if right < n and tree[right] != -1:
            stack.append(right)
    return total

Обрезка с учетом порядка в дереве поиска

Идея

Сохрани тот же обход с помощью стека, но используй порядок значений. Допустим, узел содержит v. Его левое поддерево содержит только значения меньше v. Если v ≤ low, все они меньше low, поэтому левое поддерево ничего не может добавить: пропусти его. Аналогично, если v ≥ high, правое поддерево содержит только значения больше high: пропусти его. Поэтому добавляй левого потомка в стек только тогда, когда v > low, а правого — только тогда, когда v < high.

В первом примере с диапазоном [9, 31] значение 31 равно high, поэтому его правый потомок 40 никогда не добавляется в стек. Значение 8 меньше low, поэтому его левый потомок 3 пропускается, а правый потомок 12 всё ещё посещается, поскольку значения между 8 и 20 могут входить в диапазон.

Посещённые узлы — это k значений в диапазоне и не более двух путей от корня к листу вдоль его границ, поэтому временная сложность составляет O(h + k). Если диапазон охватывает всё дерево, сложность всё ещё составляет O(n), но узкий диапазон в большом дереве затрагивает всего несколько десятков узлов. Стеку требуется O(h) памяти.

Алгоритм

Поместите индекс корня 0 в стек и задайте total = 0.
Извлеките индекс i и прочитайте v = tree[i]. Если low ≤ v ≤ high, добавьте v к total.
Если v > low, поместите левого потомка 2*i+1 в стек, если он существует.
Если v < high, поместите правого потомка 2*i+2 в стек, если он существует.
Когда стек опустеет, верните total.

def rangeSumBST(tree, low, high):
    n = len(tree)
    total = 0
    stack = [0]  # node indexes still to visit; the root is never empty
    while stack:
        i = stack.pop()
        value = tree[i]
        if low <= value <= high:
            total += value
        left, right = 2 * i + 1, 2 * i + 2
        # Smaller values sit on the left, larger on the right: skip a side the range cannot reach.
        if value > low and left < n and tree[left] != -1:
            stack.append(left)
        if value < high and right < n and tree[right] != -1:
            stack.append(right)
    return total

Ловушки и крайние случаи

Большинство неправильных ответов связано с границами диапазона или массива.

Использование строгих сравнений. Включены обе границы, поэтому узел, равный low или high, учитывается.
Слишком ранняя обрезка. Когда v равно low, левое поддерево можно пропустить, но когда v равно low + 1, этого делать нельзя: в нём может находиться само значение low.
Остановка на узле вне диапазона. У узла меньше low всё ещё может быть правое поддерево, полное значений из диапазона, поэтому пропускайте только ту сторону, которую исключают правила порядка.
Чтение индекса дочернего узла за пределами массива. Перед чтением значения проверьте 2*i+1 < tree.length, а -1 считайте отсутствием дочернего узла.
Путаница со смещением в Lua и R, где массивы начинаются с 1. Оставляйте индексы узлов 0-индексированными для вычислений с 2*i+1 и считывайте tree[i + 1].

Частые вопросы4

Какова временная сложность Range Sum of BST?

Обход, который использует порядок дерева поиска для отсечения ветвей, посещает k узлов в диапазоне, а также узлы не более чем на двух путях от корня; для дерева глубины h это занимает время O(h + k). В худшем случае, когда каждое значение входит в диапазон, это O(n). Дополнительная память составляет O(h) для стека или рекурсии.

Почему можно пропускать поддеревья в Range Sum of BST?

В бинарном дереве поиска каждое значение слева от узла меньше его значения, а каждое значение справа — больше. Если значение узла не превышает low, ничто слева от него не может попасть в диапазон, а если оно не меньше high, ничто справа от него не может попасть в диапазон. Пропуская эти стороны, вы не пропустите ни одного значения из диапазона.

Можно ли решить задачу Range Sum of BST с помощью симметричного обхода?

Да. Симметричный обход двоичного дерева поиска перечисляет значения в возрастающем порядке, поэтому можно складывать значения, как только они достигают low, и остановиться, как только значение превысит high. Результат будет тем же, а ранняя остановка позволяет сэкономить работу в правой части дерева, тогда как отсечение ветвей также экономит работу в левой части.

Следует ли использовать рекурсию или стек для вычисления суммы в диапазоне BST?

Оба варианта работают. Рекурсивный вариант короче, а здесь глубина составляет не более 14, поэтому стек вызовов остаётся небольшим. Явный стек полностью позволяет избежать ограничения рекурсии, что важно для высокого дерева с тысячами уровней; именно его используют решения на этой странице.

Python

def rangeSumBST(tree, low, high):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

tree = [20, 8, 31, 3, 12, -1, 40, -1, -1, 10, 15]
low = 9
high = 31

Ожидается