Junior
Mis on binaarne puu?
sobes.tech AI
Vastus AI-lt
Kaksipuuline puu on andmestruktuur, mis sarnaneb puuga, kus iga sõlm võib omada kuni kaks järglast: vasak ja parem.
Peamised omadused:
- Juure (Root): Puuga kõrgem sõlm.
- Sõlm (Node): Puus olev element, mis sisaldab andmeid ja viiteid selle järglastele.
- Laps (Child): Sõlm, mis asub otse teise sõlme (ema) all.
- Ema (Parent): Sõlm, kellel on otse all üks või mitu järglast.
- Leht (Leaf): Sõlm, millel ei ole järglasi.
- Haru (Branch): Tee juurest leheni.
- Alampuu (Subtree): Puu, mis koosneb ühest sõlmest ja kõigist selle järglastest.
Erinevad kaksipuuliste puude tüübid:
- Täielik kaksipuuline puu (Full Binary Tree): Iga sõlm omab kas 0 või 2 järglast.
- Täiuslik kaksipuuline puu (Perfect Binary Tree): Kõik tasemed, välja arvatud viimane, on täielikult täidetud ning viimase taseme kõik sõlmed paiknevad võimalikult vasakul.
- Tasakaalustatud kaksipuuline puu (Balanced Binary Tree): Iga sõlme vasaku ja parema alampuu kõrguste erinevus ei ületa 1. Näide: AVL-puu, punane-must puu.
- Degeneratiivne (laienev) kaksipuuline puu (Degenerate Binary Tree): Iga sõlm omab kuni ühte järglast. Põhimõtteliselt on see ühendatud nimekiri.
Kasutatakse erinevates algoritmides ja andmestruktuurides, näiteks kaheotsingupuu, virnade, süntaktiliste puude puhul.