sisäsolmu

Sisäsolmu on käsite, jota käytetään puu- ja graf-teorioissa. Se tarkoittaa solmua, jolla on ainakin yksi lapsi. Lehtisolmu (leaf) puolestaan on solmu, jolla lapsia ei ole. Puussa sisäsolmujen ja lehtisolmujen määrä sekä niiden suhteet kuvaavat rakenteen rakennetta. Suuntaamattomissa puissa termiä käytetään yleensä puun mukaan, mutta käytännössä sisäsolmulla tarkoitetaan solmua, jolla on ainakin yksi naapuriin liittyvä alihakemisto.

Juurisolmu tarkoittaa puun ylintä solmua. Jos puu koostuu vain yhdestä solmusta, kyseinen solmu on sekä juuri että lehti. Rootiksi määritellään puun alkuperä, josta muut solmut haarautuvat. Juurisolmu voi olla sisäsolmu silloin, kun puussa on vähintään toinen solmu.

Ominaisuudet ja laskentasäännöt: jos puussa on N solmua, L on lehtisolmujen määrä ja I on sisäsolmujen määrä, niin N = L + I. Tämä pätee sekä yksinkertaisiin että monimutkaisiin puuryhmiin, kun solmut jaetaan sisäsolmuihin ja lehtisolmuihin. Eräissä erityistapauksissa, kuten täydellisessä binääri puussa, jokaisella sisäsolmulla on täsmälleen kaksi lasta ja lehtisolmujen määrä toteuttaa L = I + 1.

Käyttökohteet: sisäsolmuja käytetään laajalti tietorakenteissa ja algoritmeissa, joissa puita tarkastellaan tai muokataan, kuten hakupuissa ja päätöspuissa. Biologiassa sisäsolmut voivat edustaa hypoteettisia esi-isiä evoluutiofuussa, kun lehdet kuvaavat havaittuja lajeja. Yleisesti sisäsolmut ovat keskeisiä solmujen järjestämisessä ja reittien sekä kierrosten kulun analysoinnissa puissa.