Pagrindinis skirtumas – dvejetainis medis ir dvejetainis paieškos medis
Duomenų struktūra yra sistemingas būdas tvarkyti duomenis, kad jie būtų naudojami efektyviai. Duomenų išdėstymas naudojant duomenų struktūrą turėtų sutrumpinti veikimo laiką arba vykdymo laiką. Be to, duomenų struktūrai turėtų būti reikalingas minimalus atminties kiekis. Kartais duomenys gali būti išdėstyti medžio struktūroje. Medis reiškia mazgą, sujungtą briaunomis. Viršutinis mazgas yra šaknis. Kiekvienas mazgas gali turėti daugiausiai du mazgus. Jie žinomi kaip vaikų mazgai. Pagrindinio mazgo kairėje esantis mazgas yra kairysis antrinis mazgas, o pagrindinio mazgo dešinėje esantis mazgas yra dešinysis mazgas. Dvejetainis medis ir dvejetainis paieškos medis yra dvi medžio duomenų struktūros. Dvejetainis medis yra duomenų struktūros tipas, kuriame kiekvienas pirminis mazgas gali turėti daugiausia du antrinius mazgus. Dvejetainis paieškos medis yra dvejetainis medis, kuriame kairiajame antriniame mazge yra tik mazgai, kurių reikšmės mažesnės arba lygios pirminiam mazgui, o dešiniajame antriniame yra tik mazgai, kurių reikšmės yra didesnės nei pirminio mazgo. Tai yra pagrindinis skirtumas. Skirtingai nuo duomenų struktūrų, tokių kaip masyvai, dvejetainis medis ir dvejetainis paieškos medis neturi viršutinės duomenų saugojimo ribos.
Kas yra dvejetainis medis?
Tvarkant duomenis medžio struktūroje, medžio viršuje esantis mazgas vadinamas šakniniu mazgu. Visam medžiui gali būti tik viena šaknis. Bet kuris mazgas, išskyrus šakninį mazgą, turi vieną kraštą aukštyn iki mazgo. Jis vadinamas pirminiu mazgu. Po pirminiu kodu esantis mazgas vadinamas antriniu mazgu. Kiekvienas pirminis mazgas gali turėti ne daugiau kaip du antrinius mazgus. Jie vadinami kairiuoju antriniu mazgu ir dešiniuoju antriniu mazgu. Mazgas be jokio antrinio mazgo vadinamas lapo mazgu. Nėra konkretaus būdo, kaip sutvarkyti duomenis dvejetainiame medyje. Nuo šakninio mazgo iki kiekvieno mazgo yra kelias.
01 pav.: dvejetainio medžio pavyzdys
Aukščiau pateiktas dvejetainio medžio pavyzdys. 2 elementas, esantis medžio viršuje, yra šaknis. Kiekvienas mazgas turi ne daugiau kaip du mazgus. Jei medyje yra kilpų arba jei viename mazge yra daugiau nei du mazgai, jis negali būti klasifikuojamas kaip dvejetainis medis. Norint pereiti iš vieno mazgo į kitą, visada yra vienas kelias. 2 šakninio mazgo antriniai mazgai yra 7 ir 5. Taip pat mazgas gali neturėti mazgų. Bet bet kuris mazgas negali turėti daugiau nei dviejų mazgų. Dešinysis šaknies elementas yra 5. Šis elementas 5 yra pirminis 9 antrinio mazgo mazgas. 4 ir 11 mazgai neturi antrinių elementų. Todėl jie yra lapų mazgai.
Dvejetainis medis naudojamas duomenims saugoti hierarchine tvarka. Ji panaši į kompiuterio failų struktūrą. Duomenų struktūra kaip masyvas gali saugoti tam tikrą duomenų kiekį. Tačiau dvejetainiame medyje nėra viršutinės mazgų skaičiaus ribos.
Kas yra dvejetainis paieškos medis?
Dvejetainis paieškos medis yra dvejetainė medžio duomenų struktūra. Panašiai kaip dvejetainis medis, dvejetainis paieškos medis taip pat gali turėti du mazgus. Bet kuris mazgas, išskyrus šakninį mazgą, turi vieną kraštą aukštyn iki mazgo. Jis vadinamas pirminiu mazgu. Žemiau duotosios esantis mazgas, sujungtas jo kraštu žemyn, vadinamas antriniu mazgu. Mazgas be jokio antrinio mazgo vadinamas lapo mazgu. Kiekvienas pirminis mazgas gali turėti daugiausiai du mazgus. Yra antriniai mazgai, nurodantys kairįjį antrinį mazgą ir dešinįjį antrinį mazgą. Viršutinis elementas vadinamas šakniniu mazgu. Kairėje antrinėje pusėje yra tik mazgai, kurių reikšmės yra mažesnės arba lygios pirminiam mazgui. Dešiniajame antriniame mazge yra tik mazgai, kurių reikšmės yra didesnės arba lygios pirminiam mazgui.
02 pav.: dvejetainio paieškos medžio pavyzdys
8 elementas yra aukščiausias elementas. Todėl tai yra šakninis mazgas. Jei 3 yra pirminis mazgas, tai 1 ir 6 yra antriniai mazgai. 1 yra kairysis antrinis mazgas, o 6 yra dešinysis antrinis mazgas. Kairėje antrinėje pusėje yra reikšmės, mažesnės arba lygios pirminiam mazgui. Kai 3 yra pirminis mazgas, kairėje pusėje turėtų būti elementas, kuris yra mažesnis arba lygus 3. Šiame pavyzdyje jis yra 1. Dešiniajame antriniame mazge yra tik mazgai, kurių reikšmės yra didesnės nei pirminio mazgo. Kai 3 yra pirminis mazgas, dešinysis antrinis mazgas turi turėti didesnę reikšmę nei 3. Šiame pavyzdyje ji yra 6. Taip pat yra tam tikra tvarka kiekvienam duomenų elementui išdėstyti dvejetainį paieškos medį. Tai duomenų struktūra, suteikianti efektyvų būdą rūšiuoti, gauti ir ieškoti duomenų.
Kokie yra dvejetainio medžio ir dvejetainio paieškos medžio panašumai?
- Tiek dvejetainis medis, tiek dvejetainis paieškos medis yra hierarchinės duomenų struktūros.
- Tiek dvejetainis medis, tiek dvejetainis paieškos medis turi šaknis.
- Ir dvejetainis medis, ir dvejetainis paieškos medis gali turėti daugiausia du antrinius mazgus.
Kuo skiriasi dvejetainis medis ir dvejetainis paieškos medis?
Dvejetainis medis vs dvejetainis paieškos medis |
|
| Dvejetainis medis yra duomenų struktūros tipas, kuriame kiekvienas pirminis mazgas gali turėti daugiausia du antrinius mazgus. | Dvejetainis paieškos medis yra dvejetainis medis, kuriame kairiajame antriniame mazge yra tik mazgai, kurių reikšmės yra mažesnės už pirminį mazgą arba jam lygios, o dešiniajame antriniame yra tik mazgai, kurių reikšmės yra didesnės nei pirminio mazgo. |
| Duomenų išdėstymo tvarka | |
| Dvejetainis medis neturi konkrečios duomenų elementų išdėstymo tvarkos. | Dvejetainis paieškos medis turi tam tikrą duomenų elementų išdėstymo tvarką. |
| Naudojimas | |
| Dvejetainis medis naudojamas kaip veiksminga duomenų ir informacijos paieška medžio struktūroje. | Dvejetainis paieškos medis naudojamas duomenims įterpti, ištrinti ir ieškoti. |
Santrauka – dvejetainis medis ir dvejetainis paieškos medis
Duomenų struktūra yra duomenų tvarkymo būdas. Kartais duomenys gali būti išdėstyti medžio struktūroje. Du iš jų yra dvejetainis medis ir dvejetainis paieškos medis. Šiame straipsnyje aptariamas skirtumas tarp dvejetainio medžio ir dvejetainio paieškos medžio. Dvejetainis medis yra duomenų struktūros tipas, kuriame kiekvienas pirminis mazgas gali turėti daugiausia du antrinius mazgus. Dvejetainis paieškos medis yra dvejetainis medis, kuriame kairiajame antriniame mazge yra tik mazgai, kurių reikšmės yra mažesnės už pirminį mazgą arba jam lygios, o dešiniajame antriniame yra tik mazgai, kurių reikšmės yra didesnės nei pirminio mazgo.
Atsisiųskite dvejetainio medžio ir dvejetainės paieškos medžio PDF failą
Galite atsisiųsti šio straipsnio PDF versiją ir naudoti ją neprisijungus, kaip nurodyta citatos pastaboje. Atsisiųskite PDF versiją čia: Skirtumas tarp dvejetainio medžio ir dvejetainio paieškos medžio
