Junior
Kas yra dvejetainis medis?
sobes.tech AI
Atsakymas iš AI
Dvigubas medis yra duomenų struktūra, panaši į medį, kur kiekvienas mazgas turi ne daugiau kaip du palikuonis: kairį ir dešinį.
Pagrindinės savybės:
- Šaknis (Root): Aukščiausias medžio mazgas.
- Mazgas (Node): Medžio elementas, kuris turi duomenis ir nuorodas į savo palikuonis.
- Vaikas (Child): Mazgas, kuris yra tiesiogiai po kitu mazgu (tėvu).
- Tėvas (Parent): Mazgas, kuris turi vieną ar daugiau tiesioginių palikuonių.
- Lapelis (Leaf): Mazgas be palikuonių.
- Šaka (Branch): Kelias nuo šaknies iki lapo.
- Potmedis (Subtree): Medis, sudarytas iš vieno mazgo ir visų jo palikuonių.
Skirtingi dvigubų medžių tipai:
- Pilnas dvigubas medis (Full Binary Tree): Kiekvienas mazgas turi arba 0, arba 2 palikuonis.
- Tobulas dvigubas medis (Perfect Binary Tree): Visuose lygiuose, išskyrus paskutinį, yra pilnai užpildyti, o paskutinio lygio visi mazgai yra kuo arčiau kairės.
- Subalansuotas dvigubas medis (Balanced Binary Tree): Kiekvieno mazgo kairiojo ir dešiniojo potmedžio aukščiai skiriasi ne daugiau kaip 1. Pavyzdys: AVL medis, raudona-juoda medis.
- Degeneruotas (išsiplėtęs) dvigubas medis (Degenerate Binary Tree): Kiekvienas mazgas turi ne daugiau kaip vieną palikuonį. Iš esmės, tai yra susietas sąrašas.
Naudojamas įvairiuose algoritmuose ir duomenų struktūrose, pavyzdžiui, dviejų paieškos medžiuose, kalnuose, sintaksės medžiuose.