Какво е бинарно дърво?

Бинарното дърво е структура от данни във форма на дърво, при която всеки възел има най-много две деца: ляво и дясно.

Ключови характеристики:

• Всеки възел има указател към стойността си (данни) и указатели към левия и десния си наследник (могат да са празни).
• Съществува коренов възел — горният възел на дървото, без предшественик.
• Листата са възли без наследници.
• Поддърветата са всяко от двоичните дървета, които образуват поддървото на корена.

Основни типове бинарни дървета:

• Пълно бинарно дърво: на всеки ниво, освен може би последното, всички възли имат по две деца, а на последното ниво всички възли са изместени наляво.
• Перфектно бинарно дърво: всички нива са напълно запълнени, и всеки възел (освен листата) има по две деца.
• Балансирано бинарно дърво: височините на левите и десните поддървета на всеки възел се различават най-много с 1.

Приложения в QA:

• Иерархия на тестовете: организиране на тестови сценарии или набори от тестове в дървовидна структура за по-добра четливост и навигация.
• Търсене и сортиране на данни: бинарните дървета за търсене се използват за бързо търсене, вмъкване и изтриване на елементи (например при тестове за производителност на операции с данни).
• Структуриране на данни: представяне и организиране на тестови данни или резултати от изпълнение.

Пример за представяне на възел в Python:

class Node:
    def __init__(self, value):
        self.value = value  # Стойност на възела
        self.left = None    # Ляв наследник
        self.right = None   # Десен наследник