Mis on binaarne puu?

Binaarne puu on puustruktuur, kus iga sõlm omab mitte rohkem kui kahte järglast: vasakut ja paremat.

Peamised omadused:

• Iga sõlm omab viidet väärtusele (andmed) ning viiteid vasakule ja paremale järglasele (võivad olla tühjad).
• On olemas juursõlm — puu ülemine sõlm, millel pole eelkäijat.
• Lehed on sõlmed, millel pole järglasi.
• Alampuud on iga binaarse puu juure all olev puu, mis on samuti binaarne puu.

Peamised binaarpuu tüübid:

• Täielik binaarne puu: igal tasemel, välja arvatud võib-olla viimasel, on kõik sõlmed kaht järglast omavad ning viimasel tasemel on kõik sõlmed vasakule nihutatud.
• Täiuslik binaarne puu: kõik tasemed on täielikult täidetud ning iga sõlm (välja arvatud lehed) omab kahte järglast.
• Tasakaalustatud binaarne puu: iga sõlme vasaku ja parema alampuu kõrguste erinevus ei ületa 1.

Kasutus QA-s:

• Testhierarhia: teststsenaariumite või testide kogumi organiseerimine puustruktuuris parema loetavuse ja navigeerimise jaoks.
• Andmete otsimine ja sorteerimine: binaarsed otsingupuud kasutatakse kiireks otsimiseks, sisestamiseks ja elementide eemaldamiseks (näiteks andmetega toimingute jõudluse testimisel).
• Andmete struktureerimine: testide või täitmise tulemuste andmete esitamine ja organiseerimine.

Näide sõlme esitamisest Pythonis:

class Node:
    def __init__(self, value):
        self.value = value  # Sõlme väärtus
        self.left = None    # Vasak järglane
        self.right = None   # Parempoolne järglane