Kas yra dvejetainis medis?

Dvigubas medis yra duomenų struktūra, panaši į medį, kur kiekvienas mazgas gali turėti ne daugiau kaip du vaikus: kairįjį ir dešinįjį.

Pagrindinės savybės:

• Kiekvienas mazgas turi nuorodą į savo reikšmę (duomenis) ir nuorodas į kairįjį ir dešinįjį vaiką (gali būti tušti).
• Yra šakninis mazgas — aukščiausias medis, neturintis protėvio.
• Lapai — mazgai be vaikų.
• Pošakiai — kiekvienas iš dviejų medžių, sudarančių šaknies medį.

Pagrindiniai tipai:

• Pilnas dviejų vaikų medis: kiekviename lygyje, išskyrus galbūt paskutinį, visi mazgai turi du vaikus, o paskutinio lygio visi mazgai yra paslinkti į kairę.
• Tobulas dviejų vaikų medis: visi lygiai yra pilnai užpildyti, ir kiekvienas mazgas (išskyrus lapus) turi du vaikus.
• Subalansuotas dviejų vaikų medis: kiekvieno mazgo kairiojo ir dešiniojo pošakio aukščiai skiriasi ne daugiau kaip 1.

Taikymas QA:

• Testų hierarchija: testavimo scenarijų arba testų rinkinių organizavimas medžio struktūroje geresniam skaitomumui ir navigacijai.
• Duomenų paieška ir rūšiavimas: dviejų vaikų paieškos medžiai naudojami greitam paieškai, įterpimui ir šalinimui (pavyzdžiui, našumo testavimui).
• Duomenų struktūrizavimas: testų duomenų arba vykdymo rezultatų pateikimas ir organizavimas.

Python pavyzdys, kaip atvaizduoti mazgą:

class Node:
    def __init__(self, value):
        self.value = value  # Mazgo reikšmė
        self.left = None    # Kairysis vaikas
        self.right = None   # Dešinysis vaikas