Junior
Какво е двоично дърво?
sobes.tech AI
Отговор от AI
Бинарно дърво е структура от данни във форма на дърво, при която всеки възел има най-много двама наследници: левия и десния.
Основни свойства:
- Корен (Root): Най-горният възел на дървото.
- Възел (Node): Елемент на дървото, който съдържа данни и връзки към наследниците си.
- Дете (Child): Възел, който се намира директно под друг възел (родител).
- Родител (Parent): Възел, който има един или повече наследници директно под себе си.
- Лист (Leaf): Възел без наследници.
- Клон (Branch): Път от корена до листа.
- Поддърво (Subtree): Дърво, състоящо се от възел и всички негови наследници.
Различни видове бинарни дървета:
- Пълно бинарно дърво (Full Binary Tree): Всеки възел има или 0, или 2 наследници.
- Перфектно бинарно дърво (Perfect Binary Tree): Всички нива, освен последното, са напълно запълнени, а на последното ниво всички възли са разположени колкото е възможно по-наляво.
- Балансено бинарно дърво (Balanced Binary Tree): Височината на левите и десните поддървета на всеки възел се различава не повече от 1. Пример: AVL дърво, червено-черно дърво.
- Дегенерирано (разтегнато) бинарно дърво (Degenerate Binary Tree): Всеки възел има най-много един наследник. По същество, това е свързан списък.
Използва се в различни алгоритми и структури от данни, като бинарни дървета за търсене, купчини, синтактични дървета.