Создание древовидной структуры

@JIupToH · Регистрация: 20.05.2022

Author24 — интернет-сервис помощи студентам

Есть функция, которая на вход получает массив, состоящий из 2^n блоков, длиной по 32 байта каждый. Необходимо построить дерево хэширования, причем каждый узел надо пронумеровать. Не прошу писать код, прошу помощи разобраться в этой теме. А именно как строить такое дерево. Структура узла будет выглядеть следующим образом:

C++

struct node{
uint8_t *right;
uint8_t *left;
uint8_t *out;
uint64_t id;

@SmallEvil · 29.08.2024, 16:55

Дерево хешей (дерево Меркла)

Построение

@JIupToH · 30.08.2024, 00:09 **[ТС]**

SmallEvil, да это я читал, но я не могу понять как это применить к построению дерева хэшей...

@Royal_X · 30.08.2024, 00:16

Open source реализация от Майкрософт https://github.com/microsoft/merklecpp
А вот доку https://microsoft.github.io/merklecpp/main/

JIupToH, а вот простой пример https://www.geeksforgeeks.org/... rkle-tree/

@SmallEvil · 30.08.2024, 07:02

Сообщение от JIupToH

как это применить к построению дерева

там же написано, нужно построить дерево, и заполнить листья хешами из данных
навскидку, это можно сделать во время создания дерева, передав в функцию N, (уровень дерева - внутренние данные) и итератор на данные
при построении связей, хеши будут создаваться по данным из итераторов
потом уже пройтись по дереву и посчитать суммы хешей
ну елки палки, никогда бинарные деревья не строили ? обычный обход дерева

Добавлено через 13 минут

Сообщение от Royal_X

а вот простой пример https://www.geeksforgeeks.org/... rkle-tree/

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

@SmallEvil 3718 / 2647 / 761 Регистрация: 29.06.2020 Сообщений: 9,800
	29.08.2024, 16:55	2
	Дерево хешей (дерево Меркла) Построение 0

@JIupToH 34 / 22 / 13 Регистрация: 20.05.2022 Сообщений: 414
	30.08.2024, 00:09 [ТС]	3
	SmallEvil, да это я читал, но я не могу понять как это применить к построению дерева хэшей... 0

@Royal_X 4183 / 2034 / 961 Регистрация: 01.06.2021 Сообщений: 7,136 Записей в блоге: 7
	30.08.2024, 00:16	4
	Open source реализация от Майкрософт https://github.com/microsoft/merklecpp А вот доку https://microsoft.github.io/merklecpp/main/ JIupToH, а вот простой пример https://www.geeksforgeeks.org/... rkle-tree/ 0

@SmallEvil 3718 / 2647 / 761 Регистрация: 29.06.2020 Сообщений: 9,800
	30.08.2024, 07:02	5
	Сообщение от JIupToH как это применить к построению дерева там же написано, нужно построить дерево, и заполнить листья хешами из данных навскидку, это можно сделать во время создания дерева, передав в функцию N, (уровень дерева - внутренние данные) и итератор на данные при построении связей, хеши будут создаваться по данным из итераторов потом уже пройтись по дереву и посчитать суммы хешей ну елки палки, никогда бинарные деревья не строили ? обычный обход дерева Добавлено через 13 минут Сообщение от Royal_X а вот простой пример https://www.geeksforgeeks.org/... rkle-tree/ Чой то там у них за паранойя со struct я такое только у отбитых видел 0