Як приклад наведемо бінарне дерево, що складається з вузлів і ребер (рис. 2.7). Вузли бувають трьох типів:

- Кореневої - має два ребра: праве і ліве;

- Внутрішній - має три ребра: одне з'єднує з вищерозміщених вузлом, а два інших - праве і ліве;

- Листя - з'єднуються тільки з верхніх вузлом.

Рис. 2.7. Бінарне дерево
Кореневий вузол породжує або внутрішні вузли, або листя, що називаються дітьми. Вони, в свою чергу, породжують інші вузли, і тоді самі називаються батьками.

Наведемо приклад побудови дерева аутентифікації на основі бінарного дерева. Нехай в системі є вільна від колізій хеш-функція h і t загальнодоступних значень (наприклад, відкриті ключі) Yt ... Yt. Тоді побудова дерева аутентифікації буде відбуватися таким чином:

1. Позначимо кожне з t загальнодоступних значень як листя.

2. Ребро, що виходить з листа, позначимо як h (Yj).

3. Якщо ліве і праве ребро внутрішнього вузла позначені як ht і h2, то ребро, що з'єднує з вищерозміщених вузлом, позначимо як

4. Якщо ребра, що підходять до кореневого вузла, позначені як uj і u2, то кореневий вузол позначимо як h (uj u2).