Що таке щільність дерева?

Щільність дерева - це характеристика, яка показує, наскільки дерево "заповнене" вузлами відносно можливого максимуму для його висоти.

---

#Формально

Якщо висота дерева = h, то максимальна кількість вузлів (в ідеальному повному дереві) дорівнює: [ N_{max} = 2^{h+1} - 1 ]

Щільність (D) визначається як: [ D = \frac{N_{actual}}{N_{max}} ] де

• ( N_{actual} ) - реальна кількість вузлів у дереві,
• ( N_{max} ) - максимально можлива за цієї висоти.

---

#Приклад

Дерево має висоту 3 і містить 10 вузлів. Максимум при h = 3 → ( 2^{4} - 1 = 15 ). [ D = 10 / 15 = 0.67 ] Тобто дерево заповнене на 67%.

---

#Інтерпретація

• Чим вища щільність, тим краще збалансоване дерево і ближче до повного.
• Низька щільність указує на розрідженість: багато "порожнього простору", довгі гілки, меншу ефективність.

---

#Підсумок

Щільність дерева показує, наскільки ефективно воно заповнене вузлами за своєї висоти. Це міра "компактності" структури: чим ближче до 1, тим дерево більш збалансоване й ефективне.