Medis (duomenų struktūra): Skirtumas tarp puslapio versijų
Ištrintas turinys Pridėtas turinys
S robot Adding:da Modifying:pt |
SNėra keitimo santraukos |
||
Eilutė 1:
Medžiai yra hierarchinės [[:Category:Duomenų struktūros|duomenų struktūros]], juose tarp medžio elementų egzistuoja "tėvų-vaikų" santykiai. Kiekvienas elementas yra susietas su vienu ar daugiau elementų. Medžio elementai yra vadinami medžio viršūnėmis. Kitaip nei gamtoje, ši duomenų struktūra dažniausiai vaizduojama iš viršaus į apačią, kai aukščiau esanti viršunė vadinama tėvu. Elementas, kuris neturi tėvo, vadinamas '''šaknimi''' ar šakniniu elementu. Elementai neturintys vaikų vadinami ''lapais''. Viršunės, kuriuos nėra lapai dar vadinamos vidinėmis viršūnėmis.
Medžio '''aukščiu''' vadinamas atstumas nuo šaknies iki toliausiai esančio lapo. Medžio '''viršūnės lygis''' nusako jos eilės tvarką skaičiuojant nuo šaknies (šaknis yra 1 lygio, jos vaikas 2...).
Eilutė 9:
Pilnas (''full'') dvejetainis medis tai medis, kurio visų lapų aukštis yra vienodas ir visos viršūnės arba neturi vaikų, arba jų turi 2.
Pilnas ''h'' aukščio medis turi 2<sup>h-1</sup> viršūnių, o bet kuris ''h'' aukščio dvejetainis medis turi ne daugiau nei 2<sup>h-1</sup> viršūnių. Atitinkamai ''N'' viršūnių dvejetainių medžių minimalus aukštis yra
=== Dvejetainis paieškos medis ===
| |||