Що таке двійкове дерево?

Двійкове дерево (binary tree) - це структура даних, у якій кожен вузол може мати не більше двох нащадків:

• лівого (left child)
• правого (right child)

#Структура

Тут:

• A - корінь,
• B і C - нащадки A,
• у B два нащадки (D і E),
• C - лист (немає нащадків).

#Особливості

• Кожен вузол має до 2 ребер (на відміну від загального дерева, де їх може бути більше).
• Спрощує реалізацію пошуку, сортування та обходів.

#Основні різновиди

1. Повне (complete) - усі рівні заповнені, крім, можливо, останнього, і елементи на ньому вибудувані зліва направо.
2. Досконале (perfect) - усі рівні повністю заповнені.
3. Збалансоване (balanced) - висота лівого і правого піддерев відрізняється не більше ніж на 1.
4. Двійкове дерево пошуку (BST) - ліве піддерево містить елементи менші за батька, праве - більші.

#Підсумок

Двійкове дерево - це ієрархічна структура, де кожен вузол пов'язаний максимум із двома нащадками, що робить її базою для багатьох алгоритмів пошуку, сортування та зберігання даних.