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

- корневой - имеет два ребра: правое и левое;

- внутренний - имеет три ребра: одно соединяет с вышележащим узлом, а два других - правое и левое;

- листья - соединяются только с вышележащим узлом.

Рис. 2.7. Бинарное дерево
Корневой узел порождает либо внутренние узлы, либо листья, называемые детьми. Они, в свою очередь, порождают другие узлы, и тогда сами называются родителями.

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

1. Обозначим каждое из t общедоступных значений как листья.

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

3. Если левое и правое ребро внутреннего узла обозначены как ht и h2, то ребро, соединяющее с вышележащим узлом, обозначим как

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