Дерева
Це сукупність компонентів, що називаються вузлами, в якому є головний (один) компонент у вигляді кореня, а всі інші розбиті на безліч роз’єднаних елементів. Кожна множина є деревом, а корінь кожного дерева – нащадком кореня дерева. Іншими словами, всі компоненти з’єднані між собою відносинами предок–нащадок. Як результат можна спостерігати ієрархічну структуру вузлів. Якщо вузли не мають нащадка, то вони називаються листям. Над деревом визначені такі операції: додавання компонента і його видалення, обхід, пошук компонента. Особливу роль в інформатиці грають бінарні дерева. Що це таке? Це приватний випадок дерева, де кожен вузол може мати не більше пари нащадків, що є корінням лівого і правого піддерева. Якщо додатково для вузлів дерева виконується ще умову, що всі значення компонентів лівого піддерева менше значень кореня, а значення компонентів правого піддерева більше кореня, то таке дерево називається деревом бінарного пошуку, і воно призначається для швидкого знаходження елементів. Як же працює алгоритм пошуку в такому випадку? Шукане значення порівнюється зі значенням кореня, і в залежності від результату пошук або завершується, або триває, але виключно в лівому або правому поддереве. Загальна кількість операцій порівняння не стане перевершувати висоту дерева (це найбільше число компонентів на шляху від кореня до одного з листя).
