Поиск суммы всех элементов дерева

13.3. Алгоритмы работы с деревьями

А1. Вычисление суммы значений информационных полей элементов

Алгоритм реализован в виде функции, возвращающей значение суммы информационных полей всех элементов. Тривиальным считается случай, когда очередной узел – пустой, и, следовательно, не имеет информационного поля.

function Sum(Root : PNode) : integer;

if Root=Nil then

Sum := Root^.Data + Sum(Root^.left)

Для нетривиального случая результат вычисляется как значение информационного элемента в корне (Root^.Data) плюс суммы информационных полей левого и правого поддеревьев.

А выражение Sum(Root^.left)представляет собой рекурсивный вызов левого поддерева для данного корня Root.

А2. Подсчет количества узлов в бинарном дереве

function NumElem(Tree:PNode):integer;

if Tree = Nil then

А3. Подсчет количества листьев бинарного дерева

function Number(Tree:PNode):integer;

if Tree = Nil then

else if (Tree^.left=Nil) and (Tree^.right=Nil) then

Number := Number(Tree^.left) + Number(Tree^.right);

Анализ приведенных алгоритмов показывает, что для получения ответа в них производится просмотр всех узлов дерева. Ниже будут приведены алгоритмы, в которых порядок обхода узлов дерева отличается. И в зависимости от порядка обхода узлов бинарного упорядоченного дерева, можно получить различные результаты, не меняя их размещения.

Примечание: Просмотр используется не сам по себе, а для обработки элементов дерева, а просмотр сам по себе обеспечивает только некоторый порядок выбора элементов дерева для обработки. В приводимых ниже примерах обработка не определяется; показывается только место, в котором предлагается выполнить обработку текущего

А4. Алгоритмы просмотра дерева

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

а. Просмотр дерева слева – направо

procedure ViewLR(Root:PNode); Left – Right >

if Root<>Nil then

вывод на печать, в файл и др.>

Источник

Как найти суммы последовательных узлов в бинарном дереве?

Дано: бинарное дерево (алгоритм дерева написан вручную). Число S. Нужно найти последовательность узлов (только с вверху вниз или наоборот) в бинарном дереве, сумма которых равна S. Например: есть бинарное дерево, а число S = 9. Решение: 3+6, 4+5, 9. п.с. желательно, что бы это был отдельный класс, который имел доступ к классу binTree

#pragma once class binTree < protected: struct Node < int Value; Node * pLeft; Node * pRight; Node * pParent; Node(int x) :Value(x), pLeft(NULL), pRight(NULL), pParent(NULL) <>>; Node * m_pRoot; void InoderTreeWalk(Node * x); Node * TreeSuccessor(Node *x); Node * TreeMin(Node * x); public: binTree(); ~binTree(); virtual void TreeInsert(int k); Node * TreeSearch(Node * X, int k); void ShowTree(); int Root(); >; 

2 ответа 2

Задача тянет на олимпиадную, пишу идею.

Решение будет сделано с помощью динамики по дереву.

Для каждого узла в дереве заведём список значений. Инициализация — в листах . Пересчёт снизу вверху. Значение для узла пересчитывается примерно так (текущая вершина U):

for (auto left : U->left->list) U->list.add(left + U->Value); for (auto right: U->left->right) U->list.add(right+ U->Value); U->add(U->Value); U->list->unique(); 

Я специально пишу псевдокодом, т.к. там может быть любая структура от специфики задачи (list vector set bitset) и т.д.

Для каждой вершины, где в списке есть S будет последовательность ответ, которая заканчивается в ней. Её можно восстановить примерно так. Последовательность однозначно задаётся начальным и конченым элементом. Я верну только начальные.

list fun(Tree *U, int S)< S -= U->Value; list tmp; if (S == 0) tmp.add(U); if (U->left->list.contains(S)) tmp.add(fun(U->left,S); if (U->rigth->list.contains(S)) tmp.add(fun(U->rigth,S); return tmp; > 

Сложно что-то порядка O(N^2 log N). Оптимизировать можно, но если выводить все последовательности то их может быть примерно столько же. Дальнейшие реализации/оптимизации вам виднее.

Источник

Поиск суммы всех элементов дерева

Обратите внимание, что у каждого элемента есть своё отдельное место, и никакая пара элементов не пересекается, поэтому все элементы мы можем записать в массив: рассматриваемая вершина имеет индекс v , а его потомки – индексы 2*v + 1 и 2*v + 2 для левого и правого потомка соответственно.

Расход памяти дерева отрезков будет составлять 4n (доказательство).

Пусть у нас есть массив tree[4*n] и есть вершина tree[v] , которая должна хранить сумму диапазона [L..R] . Если L == R , то очевидно, что tree[v] = a[L] . В противном случае мы не можем сразу сказать, чему равна сумма. Для этого нам нужно передать запрос суммы потомкам, а затем записать в tree[v] результат сложения сумм потомков. Пусть M = середина диапазона [L..R] , тогда левый потомок t[2*v + 1] соответствует диапазону [L..M] , а правый t[2*v + 2] – [M..R] .

Напишем рекурсивную функцию построения дерева отрезков для вычисления суммы:

#include using namespace std; const int SIZE = (1 return; // Присвоили, возвращаемся > int M = (L + R) / 2; // Выбираем середину отрезка [L..R] build_sum_tree(2 * v + 1, L, M); // Запускаем сумму для левого потомка build_sum_tree(2 * v + 2, M, R); // И для правого tree[v] = tree[2 * v + 1] + tree[2 * v + 2]; // Обновляем текущую вершину > // Usage: // build_sum_tree(0, 0, SIZE); Строим дерево от нулевой вершины с границей от 0 до SIZE (можно n) 

Для вычисления max/min/gcd построение аналогично, только tree[v] надо присваивать max(л.п., п.п.)/min(л.п., п.п.)/gcd(л.п., п.п.) соответственно.

Подсчёт суммы на отрезке

Пусть дан массив a , q запросов с данными l , r . Необходимо для каждого запроса найти сумму на отрезке [l..r] . Поскольку в данной реализации мы всё индексируем с нуля, l мы рассматриваем включительно (предварительно уменьшив l на единицу), а r – не включительно.

Утверждается, что в рекурсивной функции подсчёта суммы может быть обработано три ситуации.

1. [l..r] не пересекается с [L..R] → возвращаем нейтральное значение для суммы;
2. [L..R] ∈ [l..r] → возвращаем значение текущей вершины;
3. Третий случай, когда ни один из предыдущих не работает. Нужно получить суммы от потомков текущей вершины. Запрос аналогичен с запросом в функции build_sum_tree . Мы должны получить два слагаемых от двух потомков соответственно и вернуть их сумму. При этом стоит заметить, что рекурсия не будет разрастаться: каждый запрос будет обрабатываться за 2*logN , что асимптотически верно O(logN) , поскольку одна из двух вызываемых рекурсий всегда будет возвращать либо 0, либо tree[v] . В этом несложно убедиться, если попробовать пройтись алгоритмом по дереву самостоятельно.

int64_t get_summary(int v, int L, int R, int l, int r) // L, R - обрабатываемые функцией границы, l, r - границы запроса < if (r // Usage: // build_sum_tree(0, 0, SIZE); // int l, r; cin >> l >> r; --l; // int sum = (get_summary(0, 0, SIZE, l, r)); 

Изменение элемента

Смысл алгоритма донельзя прост: нужно рекурсивно спуститься до нужного нам элемента, затем пересчитать его предков. Выход из рекурсии – если L == R . Тут важно не забыть поменять не только значение элемента в дереве, но ещё и значение в самом массиве. Пусть у нас дан индекс i элемента, который мы хотим заменить, и новое значение x . Если выход из рекурсии не выполняется, то, как всегда, ищем медиану. Если данный индекс меньше медианы, то выполняем запрос изменения элемента к левому потомку, иначе – к правому. Затем пересчитываем tree[v] .

void set_in_sum_tree(int v, int L, int R, int i, int x) < if (L == R - 1) < tree[v] = x; a[i] = x; return; >int M = (L + R) / 2; if (i < M) set_in_sum_tree(2 * v + 1, L, M, i, x); else set_in_sum_tree(2 * v + 2, M, R, i, x); tree[v] = tree[2 * v + 1] + tree[2 * v + 2]; >// Usage: // build_sum_tree(0, 0, SIZE); // int i, x; cin >> i >> x; --i; // set_in_sum_tree(0, 0, SIZE, i, x); 

Изменения на отрезке

Имеем всё тот же массив a, q запросов, дерево суммы tree . Необходимо создать изменение элементов (прибавить x) на запрашиваемом отрезке [l..r] .

Создадим вспомогательный массив tree_add[2 * SIZE] . Если в tree[v] хранилось значение суммы на отрезке [L..R] , то в tree_add[v] будет хранится значение, добавляемое всем элементам на отрезке [L..R] . Тогда нам придётся переписать некоторые методы, поскольку сумма на отрезке будет вычисляться по другой формуле, а именно:

Но есть ещё одна проблема: когда запрос на изменение отрезка приходит в определённый отрезок [L..R] , он может не дойти ниже (см. иллюстрацию в начале статьи). Представьте, что дан запрос на изменение отрезка [3..5] . Тогда, исходя из нашей логики, отрезок [3..5] может быть «проинформирован» о том, что его сумма поменялась, а отрезки [3..4] , [5..5] и прочие – нет.

Эта проблема решается «ленивым проталкиванием изменений» (lazy propogation). Вкратце опишем алгоритм:

1. Если tree_add[v] != 0, то пересчитываем tree[v] ;
2. Передаём tree_add[v] потомкам, если таковые имеются;
3. Меняем значение tree_add[v] на нейтральное. В случае суммы это ноль.

void push(int v, int L, int R) < if (L != R - 1) // Условие проталкивания < tree_add[2 * v + 1] = tree_add[v]; tree_add[2 * v + 2] = tree_add[v]; >tree[v] += tree_add[v] * (R - L); // Пересчёт tree_add[v] = 0; > 

И функцию изменения на отрезке:

 void set_range(int v, int L, int R, int l, int r, int x) < push(v, L, R); if (r int M = (L + R) / 2; set_range(2 * v + 1, L, M, l, r, x); set_range(2 * v + 2, M, R, l, r, x); tree[v] = tree[2 * v + 1] + tree[2 * v + 2]; > // Usage: // build_sum_tree(0, 0, SIZE); // int l, r, x; cin >> l >> r >> x; --l; // set_range(0, 0, SIZE, l, r, x); 

Как и было сказано ранее, необходимо изменить функцию get_summary , добавив push . Ещё один важный момент: используя изменения на диапазоне, мы не поддерживаем изменения самих элементов массива.

Итак, вот наш код получившегося дерева отрезков:

#include using namespace std; const int SIZE = (1 tree[v] += tree_add[v] * (R - L); // Пересчёт tree_add[v] = 0; > void build_sum_tree(int v, int L, int R) < if (L == R - 1) // Условие выхода < if (L < n) // Поскольку мы объявляем большую размерность, необходимо следить за границей < tree[v] = a[L]; >return; // Присвоили, возвращаемся > int M = (L + R) / 2; // Выбираем серидину отрезка [L..R] build_sum_tree(2 * v + 1, L, M); // Запускаем сумму для левого потомка build_sum_tree(2 * v + 2, M, R); // И для правого tree[v] = tree[2 * v + 1] + tree[2 * v + 2]; // Обновляем текущую вершину > // Usage: // build_sum_tree(0, 0, SIZE); Строим дерево от нулевой вершины с границей от 0 до SIZE (можно n) int64_t get_summary(int v, int L, int R, int l, int r) // L, R - обрабатываемые функцией границы, l, r - границы запроса < push(v, L, R); if (r // Usage: // build_sum_tree(0, 0, SIZE); // int l, r; cin >> l >> r; --l; // int sum = (get_summary(0, 0, SIZE, l, r)); void set_in_sum_tree(int v, int L, int R, int i, int x) < if (L == R - 1) < tree[v] = x; a[i] = x; return; >int M = (L + R) / 2; if (i < M) set_in_sum_tree(2 * v + 1, L, M, i, x); else set_in_sum_tree(2 * v + 2, M, R, i, x); tree[v] = tree[2 * v + 1] + tree[2 * v + 2]; >// Usage: // build_sum_tree(0, 0, SIZE); // int i, x; cin >> i >> x; --i; // set_in_sum_tree(0, 0, SIZE, i, x); void set_range(int v, int L, int R, int l, int r, int x) < push(v, L, R); if (r int M = (L + R) / 2; set_range(2 * v + 1, L, M, l, r, x); set_range(2 * v + 2, M, R, l, r, x); tree[v] = tree[2 * v + 1] + tree[2 * v + 2]; > // Usage: // build_sum_tree(0, 0, SIZE); // int l, r, x; cin >> l >> r >> x; --l; // set_range(0, 0, SIZE, l, r, x); int main() < cin >> n; for (int i = 0; i < n; ++i) cin >> a[i]; build_sum_tree(0, 0, SIZE); int q; cin >> q; for (int req = 0; req < q; ++req) < string type; cin >> type; if (type == "1") < int l, r, x; cin >> l >> r >> x; --l; set_range(0, 0, SIZE, l, r, x); > else if (type == "2") < int i, x; cin >> i >> x; --i; set_in_sum_tree(0, 0, SIZE, i, x); > else if (type == "3") < int l, r; cin >> l >> r; --l; cout else if (type == "4") < for (int i = 0; i < n; ++i) cout > return 0; > 

Сможете решить несколько задач по теме? Вот ресурсы для практики: первый, второй и третий.

Источник