Page 96 - 4656

Алгоритми і структури даних. Лабораторний практикум.

Бінарне дерево є рекурсивної структурою, оскільки кожне
його піддерево є бінарним деревом і, отже, кожен його вузол в
свою чергу є коренем дерева.
Вузол дерева, що не має нащадків, називається листом.
Схематичне зображення бінарного дерева, рис. 12.1:

Рисунок 12.1 - Схематичне зображення бінарного дерева.

Бінарне дерево може представляти собою порожній
безліч.
Бінарне дерево може виродитися в список, рис. 12.2:

Рисунок 12.2 - Схематичне зображення бінарного дерева.

Організація даних за допомогою бінарних дерев часто
дозволяє значно скоротити час пошуку потрібного
елементу. Пошук елемента в лінійних структурах даних зазвичай
здійснюється шляхом послідовного перебору усіх елементів,
присутніх у даній структурі. Пошук по дереву не вимагає
перебору всіх елементів, тому займає значно менше часу.
Максимальне число кроків при пошуку по дереву дорівнює
висоті даного дерева, тобто кількості рівнів в ієрархічній
структурі дерева.
94