Чтение структуры хэш-дерева с 3 кандидатами

Question

Я пытаюсь выяснить, как правильно перемещаться по структуре хеш-дерева с учетом определенной транзакции. У меня уже есть ответ на вопрос, но я не совсем уверен, как они к нему пришли.

Вот ссылка на структуру хеш-дерева

Вопрос: Учитывая транзакцию, которая содержит элементы {1,3,4,5,8}, какой из листовых узлов дерева хеша будет посещен при поиске кандидатов на транзакцию?

Ответ: L1, L3, L5, L9 и L11

Я понимаю, что это какая-то форма Apriori, поэтому мой первоначальный мыслительный процесс состоит в том, чтобы взглянуть на первый уровень узла {1, 4, 7}, {2, 5, 8} и {3, 6, 9} и, если есть, из этих трех наборов-кандидатов содержат по крайней мере 1 номер в транзакции, затем переходите к следующему уровню узла, где вы проверяете, были ли по крайней мере 2 номера в транзакции, но это не работает вообще. Если бы кто-нибудь мог помочь объяснить, как перемещаться по этому типу хеш-дерева с помощью транзакции, это было бы чрезвычайно полезно.

Answer 1

1,4,7 это не набор предметов.

Каждая ветка представляет собой список чисел по модулю 3. Если x mod 3==1 вы берете первую ветку, если x mod 3==2 второй и x mod 3==0 последняя ветка.

НИКАКИХ гарантий {145}

• 1 mod 3 = 1Таким образом, первая ветвь на верхнем уровне
• 4 mod 3 = 1Таким образом, первая ветвь на втором уровне
• 5 mod 3 = 2Таким образом, вторая ветвь на третьем уровне (если она существует).