Sisäsolmut

Sisäsolmu tarkoittaa solmua puussa tai grafissa, jolla on ainakin yksi lapsi. Tämä määritelmä erottaa sisäsolmut lehtisolmuista, jotka eivät omista lapsia. Puussa voidaan lisäksi erottaa juurisolmu, sisäsolmut ja lehtisolmut. Näiden luokittelun avulla puun rakenne ja ominaisuudet voidaan ymmärtää.

Juurisolmu on puun alkuperäinen solmu. Se voi olla sisäsolmu, jos sillä on lapsia. Jos puu koostuu vain yhdestä solmusta, kyseessä on sekä juurisolmu että lehtisolmu, eikä sitä yleensä pidetä sisäsolmuna.

Ominaisuudet: Jos puussa on n solmua, ja i sisäsolmua sekä l lehtisolmua, niin n = i + l. Jokaisella sisäsolmulla on vähintään yksi lapsi, ja kytkettyjen solmujen kokonaismäärä on n − 1. Näin ollen sisäsolmujen määrä vaikuttaa puun tiheyteen ja sen tasojen määrään.

Erikoistapaukset: Täysbinäärisessä puussa jokaisella sisäsolmulla on täsmälleen kaksi lasta, jolloin l = i + 1. Yleisesti binääripuussa sisäsolmulla voi olla yksi tai kaksi lasta.

Esimerkki: Puussa A on juurisolmu, jolla on kaksi lasta B ja C; B:llä on lapsi D; D on lehtisolmu. Tällöin sisäsolmut ovat A ja B, ja lehtisolmut ovat C ja D.

Käyttö: Sisäsolmujen määrä ja sijainti vaikuttavat puun operaatioiden kustannuksiin ja tehokkuuteen. Eri algoritmeissa ja tietorakenteissa sisäsolmut ovat keskeisiä, esimerkiksi läpikäynneissä, hakumenetelmissä ja rakenteiden analyysissä.