Jei esate baigęs kompiuterių mokslo duomenų struktūrų kursą arba esate savamokslis programuotojas, tikėtina, kad susidūrėte su terminu „dvejetainiai medžiai“. Nors jie gali atrodyti šiek tiek pribloškiantys ir sudėtingi, dvejetainio medžio sąvoka yra gana paprasta.

Skaitykite toliau, kai skrodžiame dvejetainius medžius ir kodėl jie yra būtina programuotojų koncepcija.

Kas yra dvejetainiai medžiai?

Dvejetainiai medžiai yra viena iš pirmųjų duomenų struktūrų, kurių mokiniai mokomi duomenų struktūrų kursuose. Dvejetainis medis sudarytas iš daugelio mazgų, o kiekviename dvejetainio medžio mazge yra dvi rodyklės, rodančios kairiojo ir dešiniojo vaikų duomenų mazgus.

Pirmasis dvejetainio medžio mazgas vadinamas „šaknimi“. Paskutinio medžio lygio mazgai vadinami lapais.

Dvejetainio medžio skersmuo

Kiekviename mazge yra duomenų elementas ir du mazgo rodyklės. Tuščią dvejetainį medį žymi nulinis žymeklis. Kaip jau supratote, dvejetainiai medžiai gali turėti tik du vaikus (taigi ir pavadinimas).

Dvejetainių medžių struktūrų tipai

instagram viewer

Priklausomai nuo mazgų padėties, yra keletas skirtingų dvejetainių medžių struktūrų. Dvejetainis medis vadinamas visu dvejetainiu medžiu, kai kiekvienas medžio mazgas turi nulį arba du vaikus. Puikiame dvejetainiame medyje visi mazgai turi du vaikus, o lapai yra viename gylyje.

Susijęs: Geriausi būdai, kaip išmokti koduoti nemokamai

Visas dvejetainis medis turi mazgus, užpildytus kiekviename lygyje, išskyrus paskutinį lygį. Visiškuose dvejetainiuose medžiuose mazgai yra sutelkti kairėje šaknies pusėje. Kita dažna struktūra yra subalansuotas dvejetainis medis; šioje struktūroje dešiniojo ir kairiojo pusmedžių aukščiai turi skirtis daugiausia vienu. Taip pat reikalaujama, kad kairysis ir dešinysis papildomi medžiai taip pat būtų subalansuoti.

Svarbu pažymėti, kad subalansuoto dvejetainio medžio aukštis yra O (logn), kur n yra medžio mazgų skaičius.

Kai kuriais atvejais, jei kiekviename mazge yra tik vienas kairysis arba dešinysis vaikas, dvejetainis medis gali tapti iškreiptu dvejetainiu medžiu. Tada jis elgsis kaip susietas sąrašas, tokie medžiai dar vadinami išsigimusiu medžiu.

Kas yra dvejetainiai paieškos medžiai?

Dvejetainis paieškos medis (BST) iš esmės yra užsakytas dvejetainis medis, turintis specialią savybę, vadinamą „dvejetainės paieškos medžio“ nuosavybe. BST ypatybė reiškia, kad mazgai, kurių pagrindinė vertė yra mažesnė už šaknį, dedami į kairįjį papildomą medį, o mazgai, kurių pagrindinė vertė yra didesnė už šaknį, yra dešiniojo medžio dalis.

BST ypatybė turi būti teisinga kiekvienam vėlesniam medžio pagrindiniam mazgui.

Rūšiuotas dvejetainis medis

Dvejetainiai paieškos medžiai siūlo greitą įterpimą ir paiešką. Įterpimo, ištrynimo ir paieškos operacijų sudėtingiausias laikas yra O (n), kuris yra panašus į susietą sąrašą.

Dvejetainių medžių privalumai

Dvejetainiai medžiai turi daug privalumų, todėl jie išlieka labai naudinga duomenų struktūra. Jie gali būti naudojami norint parodyti struktūrinius ryšius ir hierarchiją duomenų rinkinyje. Dar svarbiau, kad dvejetainiai medžiai leidžia efektyviai ieškoti, ištrinti ir įterpti.

Taip pat labai lengva įdiegti ir prižiūrėti dvejetainį medį. Dvejetainis medis programuotojams siūlo užsakyto masyvo ir susieto sąrašo pranašumus; paieška dvejetainiame medyje vyksta taip pat greitai, kaip ir surūšiuotame masyve, o įterpimo ar ištrynimo operacijos yra tokios pat veiksmingos kaip ir susietuose sąrašuose.

Dvejetainiai medžiai yra svarbios duomenų struktūros

Dvejetainiai medžiai yra labai svarbi duomenų struktūra ir labai svarbu, kad programuotojai jaustųsi patogiai jas taikydami savo programose. Dažnai pašnekovai klausia paprastų dvejetainių medžių problemų, tokių kaip perėjimas, maksimalus gylis, atspindėjimas ir kt.

Mes labai rekomenduojame suprasti dvejetainio medžio koncepciją ir susipažinti su tipiškomis interviu problemomis.

Dalintis„Tweet“Paštu

„TreeViz“: paprastas būdas vizualizuoti duomenų struktūras

Skaityti toliau

Susijusios temos
  • Programavimas
  • Duomenų analizė
  • Programavimas
Apie autorių
M. Fahadas Khawaja (Paskelbti 31 straipsniai)

Fahadas yra „MakeUseOf“ rašytojas ir šiuo metu studijuoja kompiuterių mokslus. Būdamas aistringas technologijų rašytojas, jis nuolatos atnaujina naujausias technologijas. Jis ypač domisi futbolu ir technologijomis.

Daugiau iš M. Fahadas Khawaja

Prenumeruokite mūsų naujienlaiškį

Prisijunkite prie mūsų naujienlaiškio, kad gautumėte techninių patarimų, apžvalgų, nemokamų el. Knygų ir išskirtinių pasiūlymų!

Norėdami užsiprenumeruoti, spustelėkite čia