Ar kada nors susimąstėte, kaip efektyviai tvarkyti ir saugoti duomenis JavaScript? Dvejetainiai medžiai yra pagrindinė duomenų struktūra, leidžianti tai padaryti. Šiame straipsnyje pasinersite į žavų „JavaScript“ dvejetainių medžių pasaulį. Sužinosite, kas tai yra, kaip jas įgyvendinti, kaip atlikti pagrindines ir išplėstines operacijas bei atrasti geriausios darbo su jais praktikos pavyzdžių. Pasiruoškite plėsti savo žinias ir perkelkite savo programavimo įgūdžius į kitą lygį!
Dvejetainiai medžiai JavaScript
Dvejetainiai medžiai yra hierarchinė duomenų struktūra, kurioje kiekvienas mazgas gali turėti daugiausia du vaikus: kairįjį ir dešinįjį vaikus. Kiekvieną mazgą vaizduoja objektas, kuriame yra reikšmė ir nuorodos į jo vaikus. Ši struktūra yra itin universali ir naudojama daugelyje kompiuterių mokslo sričių, pavyzdžiui, duomenų manipuliavime, paieškos algoritmuose ir optimizavime.
Kodėl verta sužinoti apie dvejetainius medžius „JavaScript“?
„JavaScript“ dvejetainių medžių žinios yra labai svarbios kiekvienam programuotojui, norinčiam suprasti ir efektyviai išspręsti sudėtingas problemas. Dvejetainiai medžiai plačiai naudojami paieškos algoritmuose, pažangiose duomenų struktūrose ir optimizavimo algoritmuose. Žinodami, kaip su jais dirbti, galėsite rašyti efektyvesnį, keičiamo dydžio ir didelio našumo kodą. Be to, daugelis darbdavių vertina kūrėjus, kurie turi patirties dirbant su dvejetainiais medžiais, o tai gali atverti jums naujas karjeros galimybes.
Dvejetainio medžio diegimas JavaScript
Prieš pasinerdami į operacijas ir geriausią praktiką, būtina suprasti, kaip įdiegti dvejetainį medį „JavaScript“. Yra keletas būdų, kaip tai padaryti, tačiau vienas iš labiausiai paplitusių yra naudoti klases ir nuorodas į vaikus. Štai pagrindinis pavyzdys, kaip atrodytų dvejetainio medžio įdiegimas JavaScript:
class Nodo {
constructor(valor) {
this.valor = valor;
this.izquierdo = null;
this.derecho = null;
}
}
class ArbolBinario {
constructor() {
this.raiz = null;
}
// Métodos del árbol binario
}
Šiame pavyzdyje mes sukuriame klasę Nodo kuris žymi kiekvieną medžio mazgą ir klasę ArbolBinario kuri atsakinga už medžio struktūros ir operacijų valdymą. Kiekvienas mazgas turi reikšmę ir nuorodas į jo kairiąją ir dešiniąją antrinę dalį, inicijuotą kaip null numatytasis. Medžio šaknis žymi atributas raiz klasės ArbolBinario.
Pagrindinės operacijos su dvejetainiais medžiais
Įdiegę dvejetainį medį „JavaScript“, galite su juo atlikti įvairias pagrindines operacijas. Šios operacijos leidžia pridėti, pašalinti ir ieškoti elementų medyje. Pažvelkime į kai kurias dažniausiai atliekamas operacijas:
Elemento įterpimas į dvejetainį medį
Įterpiant elementą į dvejetainį medį reikia rasti tinkamą naujo mazgo vietą ir tinkamai jį susieti su esamais mazgais. Štai pavyzdys, kaip galima įterpti elementą į dvejetainį medį:
class ArbolBinario {
// ...
insertar(valor) {
const nuevoNodo = new Nodo(valor);
if (this.raiz === null) {
this.raiz = nuevoNodo;
} else {
this.insertarNodo(this.raiz, nuevoNodo);
}
}
insertarNodo(nodo, nuevoNodo) {
if (nuevoNodo.valor < nodo.valor) {
if (nodo.izquierdo === null) {
nodo.izquierdo = nuevoNodo;
} else {
this.insertarNodo(nodo.izquierdo, nuevoNodo);
}
} else {
if (nodo.derecho === null) {
nodo.derecho = nuevoNodo;
} else {
this.insertarNodo(nodo.derecho, nuevoNodo);
}
}
}
}
Šiame pavyzdyje funkcija insertar(valor) sukuria naują mazgą su nurodyta reikšme ir patikrina, ar yra medžio šaknis null. Jei taip, nustatykite naują mazgą kaip root. Kitu atveju iškvieskite funkciją insertarNodo(nodo, nuevoNodo) rasti tinkamą naujo mazgo padėtį.
Elemento paieška dvejetainiame medyje
Ieškant elemento dvejetainiame medyje, reikia eiti per medį tam tikru būdu, norint rasti mazgą, kuriame yra norima reikšmė. Štai pavyzdys, kaip galima atlikti elemento paiešką dvejetainiame medyje:
class ArbolBinario {
// ...
buscar(valor) {
return this.buscarNodo(this.raiz, valor);
}
buscarNodo(nodo, valor) {
if (nodo === null || nodo.valor === valor) {
return nodo;
} else if (valor < nodo.valor) {
return this.buscarNodo(nodo.izquierdo, valor);
} else {
return this.buscarNodo(nodo.derecho, valor);
}
}
}
Šiame pavyzdyje funkcija buscar(valor) iškviečia funkciją buscarNodo(nodo, valor) perduodant medžio šaknį ir reikšmę, kurios norite ieškoti. Funkcija buscarNodo(nodo, valor) atlieka rekursinę paiešką medyje, patikrindama, ar dabartinis mazgas yra null arba jei jo reikšmė atitinka ieškomą reikšmę. Priklausomai nuo palyginimo, toliau ieškoma kairiojo arba dešiniojo vaiko.
Dvejetainio medžio elemento ištrynimas
Elemento pašalinimas iš dvejetainio medžio gali būti šiek tiek sudėtingesnis, nes reikia atsižvelgti į skirtingus atvejus, atsižvelgiant į medžio struktūrą. Štai pavyzdys, kaip galima pašalinti elementą iš dvejetainio medžio:
class ArbolBinario {
// ...
eliminar(valor) {
this.raiz = this.eliminarNodo(this.raiz, valor);
}
eliminarNodo(nodo, valor) {
if (nodo === null) {
return null;
} else if (valor < nodo.valor) {
nodo.izquierdo = this.eliminarNodo(nodo.izquierdo, valor);
return nodo;
} else if (valor > nodo.valor) {
nodo.derecho = this.eliminarNodo(nodo.derecho, valor);
return nodo;
} else {
if (nodo.izquierdo === null && nodo.derecho === null) {
return null;
} else if (nodo.izquierdo === null) {
return nodo.derecho;
} else if (nodo.derecho === null) {
return nodo.izquierdo;
} else {
const sucesor = this.encontrarSucesor(nodo.derecho);
nodo.valor = sucesor.valor;
nodo.derecho = this.eliminarNodo(nodo.derecho, sucesor.valor);
return nodo;
}
}
}
encontrarSucesor(nodo) {
let sucesor = nodo;
while (sucesor.izquierdo !== null) {
sucesor = sucesor.izquierdo;
}
return sucesor;
}
}
Šiame pavyzdyje funkcija eliminar(valor) iškviečia funkciją eliminarNodo(nodo, valor) perduodant medžio šaknį ir reikšmę, kurią reikia ištrinti. Funkcija eliminarNodo(nodo, valor) atlieka rekursinį trynimą, atsižvelgdamas į skirtingus atvejus, priklausomai nuo medžio struktūros. Jei dabartinis mazgas yra null, grąžinamas null. Jei ieškoma reikšmė mažesnė už dabartinio mazgo reikšmę, ištrynimas atliekamas kairiajame antriniame sluoksnyje. Jei jis vyresnis, jis atliekamas dešiniajam sūnui. Jei mazgas turi abu vaikus, randamas artimiausias įpėdinis ir prieš pašalinant įpėdinį atliekamas vertės apsikeitimas.
Išplėstinės operacijos su dvejetainiais medžiais
Be pagrindinių operacijų, dvejetainiai medžiai palaiko daugybę pažangių operacijų, kurios gali padėti atlikti sudėtingesnes užduotis. Šios operacijos leidžia pervažiuoti medį įvairia tvarka, apskaičiuoti jo aukštį, patikrinti ar jis subalansuotas ir kt. Toliau išnagrinėsime kai kurias iš šių operacijų.
Dvejetainio medžio perėjimas pagal tvarką
Dvejetainio medžio eiliškumas apima apsilankymą mazguose tokia tvarka: pirmiausia kairiajame, tada dabartiniame mazge ir galiausiai dešiniajame. Šio tipo perėjimas yra naudingas norint gauti medžio elementus didėjančia tvarka. Štai pavyzdys, kaip įgyvendinti dvejetainio medžio perėjimą pagal eilę:
class ArbolBinario {
// ...
recorridoEnOrden() {
this.recorrerEnOrden(this.raiz);
}
recorrerEnOrden(nodo) {
if (nodo !== null) {
this.recorrerEnOrden(nodo.izquierdo);
console.log(nodo.valor);
this.recorrerEnOrden(nodo.derecho);
}
}
}
Šiame pavyzdyje funkcija recorridoEnOrden() iškviečia funkciją recorrerEnOrden(nodo) praeinant pro medžio šaknį. Funkcija recorrerEnOrden(nodo) atlieka rekursinį judėjimą eilės tvarka, spausdindamas dabartinio mazgo reikšmę tarp iškvietimų į kairę ir į dešinę antrinę pusę.
Iš anksto užsisakykite dvejetainio medžio perėjimą
Dvejetainio medžio išankstinis užsakymas apima apsilankymą mazguose tokia tvarka: pirmiausia dabartinis mazgas, tada kairysis antrinis ir galiausiai dešinysis vaikas. Šio tipo ekskursijos yra naudingos kuriant medžio kopiją arba spausdinant vaizdinį jo vaizdą. Štai pavyzdys, kaip įgyvendinti dvejetainio medžio išankstinį užsakymą:
class ArbolBinario {
// ...
recorridoPreOrden() {
this.recorrerPreOrden(this.raiz);
}
recorrerPreOrden(nodo) {
if (nodo !== null) {
console.log(nodo.valor);
this.recorrerPreOrden(nodo.izquierdo);
this.recorrerPreOrden(nodo.derecho);
}
}
}
Šiame pavyzdyje funkcija recorridoPreOrden() iškviečia funkciją recorrerPreOrden(nodo) praeinant pro medžio šaknį. Funkcija recorrerPreOrden(nodo) Išankstiniu užsakymu atlieka rekursinį judėjimą, spausdindamas dabartinio mazgo reikšmę prieš iškviesdamas kairįjį ir dešinįjį antrinius.
Postorder perėjimas per dvejetainį medį
Dvejetainio medžio postorder perėjimas apima mazgų lankymą tokia tvarka: pirmiausia kairiajame, tada dešiniajame ir galiausiai dabartiniame mazge. Šio tipo perėjimas yra naudingas norint atlaisvinti medžio užimtą atmintį arba atlikti operacijas, kurios priklauso nuo vaikų prieš apdorojant dabartinį mazgą. Štai pavyzdys, kaip įgyvendinti dvejetainio medžio postorder perėjimą:
class ArbolBinario {
// ...
recorridoPostOrden() {
this.recorrerPostOrden(this.raiz);
}
recorrerPostOrden(nodo) {
if (nodo !== null) {
this.recorrerPostOrden(nodo.izquierdo);
this.recorrerPostOrden(nodo.derecho);
console.log(nodo.valor);
}
}
}
Šiame pavyzdyje funkcija recorridoPostOrden() iškviečia funkciją recorrerPostOrden(nodo) praeinant pro medžio šaknį. Funkcija recorrerPostOrden(nodo) atlieka postorder rekursinį judėjimą, pirmiausia iškviesdamas kairįjį ir dešinįjį vaikus ir tada atspausdindamas dabartinio mazgo reikšmę.
Geriausia darbo su dvejetainiais medžiais „JavaScript“ praktika
Dabar, kai puikiai suprantate pagrindines ir išplėstines operacijas su dvejetainiais medžiais „JavaScript“, svarbu nepamiršti kai kurių geriausių darbo su jais praktikos pavyzdžių. Šios praktikos padės jums parašyti skaitomesnį, efektyvesnį ir lengviau prižiūrimą kodą:
- Tinkamai užregistruokite savo kodą: Dvejetainiai medžiai gali greitai tapti sudėtingi, todėl labai svarbu aiškiai ir glaustai dokumentuoti savo kodą. Paaiškinkite kiekvieno metodo paskirtį, jo parametrus ir numatomą grąžos reikšmę. Taip kodą bus lengviau suprasti jums ir kitiems kūrėjams, kurie ateityje dirbs su projektu.
- Naudokite aprašomuosius kintamųjų ir metodų pavadinimus: pasirinkite pavadinimus, atspindinčius kiekvieno kintamojo ir metodo paskirtį ir funkciją jūsų dvejetainio medžio įgyvendinime. Taip jūsų kodas bus lengviau skaitomas ir suprantamas, todėl jį bus lengviau prižiūrėti ir derinti.
- Atlikite išsamų bandymą: Prieš naudodami dvejetainio medžio įgyvendinimą realiame projekte, būtinai atlikite išsamų testavimą, kad patikrintumėte, ar jis veikia tinkamai. Sukurkite bandomuosius atvejus, apimančius skirtingus scenarijus, ir patikrinkite, ar rezultatai yra tokie, kokių tikėtasi. Tai padės nustatyti galimas klaidas ir užtikrinti, kad diegimas būtų patikimas.
- Apsvarstykite efektyvumą: Dvejetainiai medžiai gali pasiūlyti didelį duomenų apdorojimo ir paieškos efektyvumą, tačiau svarbu atsižvelgti į diegimo efektyvumą. Įvertinkite savo algoritmų našumą ir ieškokite galimybių juos optimizuoti, jei reikia. Pavyzdžiui, galite naudoti medžių balansavimo metodus, kad užtikrintumėte, jog medžio aukštis išliks priimtino lygio.
- Pasinaudokite esamomis bibliotekomis ir ištekliais: JavaScript turi daug įvairių bibliotekų ir išteklių, kurie gali padėti efektyviau dirbti su dvejetainiais medžiais. Tyrinėkite ir naudokite bibliotekas, pvz., binarytree arba bintrees, kad galėtumėte pasinaudoti jau išbandytais ir optimizuotais diegimais. Be to, peržiūrėkite oficialią „JavaScript“ dokumentaciją ir patikimus internetinius išteklius, kad išplėstumėte savo žinias ir išspręstumėte galimus iššūkius.
- Komentuokite savo kodą: Be išorinių dokumentų, svarbu į kodą įtraukti atitinkamų komentarų. Paaiškina tam tikrų kodo skyrių ar eilučių paskirtį, taip pat naudojamus algoritmus ar metodus. Tai padės kitiems kūrėjams (ir jums ateityje) greitai suprasti, kaip veikia jūsų diegimas.
Dažniausiai užduodami klausimai
Štai keletas dažniausiai užduodamų klausimų apie dvejetainius medžius „JavaScript“:
- Kuo skiriasi dvejetainis medis nuo dvejetainio paieškos medžio? Dvejetainis medis yra hierarchinė duomenų struktūra, kurioje kiekvienas mazgas gali turėti iki dviejų vaikų. Dvejetainis paieškos medis yra konkretus dvejetainio medžio tipas, kuriame mazgų reikšmės yra išdėstytos taip, kad mažiausios reikšmės būtų kairiajame antriniame, o didžiausios – dešiniajame. Tai leidžia efektyviai ieškoti medyje.
- Kada vietoj kitų duomenų struktūrų turėtumėte naudoti dvejetainį medį? Turėtumėte naudoti dvejetainį medį, kai jums reikia veiksmingos duomenų struktūros, kad galėtumėte tvarkyti ir saugoti duomenis hierarchiškai. Dvejetainiai medžiai ypač naudingi, kai reikia efektyviai atlikti paieškos, įterpimo ir trynimo operacijas.
- Ar galima subalansuoti dvejetainį medį atlikus kelias įterpimo ir trynimo operacijas? Taip, subalansuoti dvejetainį medį galima atlikus keletą įterpimo ir trynimo operacijų. Yra įvairių balansavimo algoritmų, tokių kaip AVL medis arba raudonai juodas medis, kurie užtikrina, kad medžio aukštis būtų optimalus, ir neleidžia medžiui išsibalansuoti.
- Ar dvejetainiai medžiai naudojami tik skaitiniams duomenims saugoti? Ne, dvejetainiai medžiai gali būti naudojami bet kokio tipo duomenims saugoti, ne tik skaitmeniniams duomenims. Galite įdiegti dvejetainius medžius, kuriuose saugomos teksto eilutės, pasirinktiniai objektai ar kitų tipų duomenys, atsižvelgiant į jūsų poreikius.
- Ar yra „JavaScript“ biblioteka, skirta dirbti su dvejetainiais medžiais? Taip, yra keletas „JavaScript“ bibliotekų, siūlančių išplėstines funkcijas dirbant su dvejetainiais medžiais. Kai kurios populiarios bibliotekos yra „binarytree“, „bintrees“ ir „d3-binarytree“. Šios bibliotekos suteikia jums paruoštą naudoti diegimą ir papildomas funkcijas dirbant su dvejetainiais medžiais.
- Kokie yra dvejetainių medžių praktiniai pritaikymai realiame pasaulyje? Dvejetainiai medžiai naudojami įvairiose realaus pasaulio programose, tokiose kaip duomenų bazės, paieškos algoritmai, glaudinimo algoritmai, failų sistemos ir daug daugiau. Jie yra būtini norint efektyviai tvarkyti ir ieškoti duomenų daugelyje sistemų ir programų.
Išvada
„JavaScript“ dvejetainiai medžiai yra galingas įrankis, leidžiantis efektyviai tvarkyti ir valdyti duomenis. Šiame straipsnyje sužinojote apie dvejetainių medžių pagrindus, kaip juos įdiegti „JavaScript“ ir apie pagrindines bei išplėstines operacijas, kurias galite atlikti su jais. Be to, išnagrinėjome keletą geriausių praktikų ir atsakėme į dažniausiai užduodamus klausimus, kad padėtume jums išplėsti savo žinias.
Dabar, kai puikiai suprantate dvejetainius „JavaScript“ medžius, laikas pritaikyti šias žinias savo projektams ir toliau tyrinėti šios duomenų struktūros teikiamas galimybes. Išplėskite savo programavimo įgūdžius ir perkelkite savo kodą į kitą lygį naudodami dvejetainius „JavaScript“ medžius!