Kas yra dvejetainis paieškos medis?

Dvejetainis paieškos medis yra viena iš įvairių duomenų struktūrų, padedančių tvarkyti ir rūšiuoti duomenis. Tai efektyvus būdas saugoti duomenis hierarchijoje ir yra labai lankstus.

Šiame straipsnyje mes atidžiau pažvelgsime į tai, kaip jis veikia, taip pat į jo savybes ir pritaikymą.

Kas yra dvejetainis paieškos medis?

Dvejetainis paieškos medis yra duomenų struktūra, sudaryta iš mazgų, panašių į susietus sąrašus. Gali būti dviejų tipų mazgai: tėvų ir vaikų. Šakninis mazgas yra struktūros, išsišakojusios į du antrinius mazgus, vadinamus kairiuoju ir dešiniuoju mazgu, pradžios taškas.

Kiekvieną mazgą gali nurodyti tik jo pirminis asmuo, o mes galime pereiti medžio mazgus priklausomai nuo krypties. Dvejetainis paieškos medis turi tris pagrindines savybes:

1. Kairysis mazgas yra mažesnis nei jo pirminis mazgas.
2. Dešinysis mazgas yra didesnis nei jo pirminis mazgas.
3. Kairysis ir dešinysis pomedžiai turi būti dvejetainiai paieškos medžiai.

Tobulas dvejetainis paieškos medis pasiekiamas, kai užpildomi visi lygiai ir kiekvienas mazgas turi kairįjį ir dešinįjį antrinį mazgą.

Susijęs: Duomenų mokslo bibliotekos, skirtos Python, turėtų naudoti kiekvienas duomenų mokslininkas

Pagrindinės dvejetainio paieškos medžio operacijos

Dabar jūs geriau suprantate, kas yra dvejetainis paieškos medis, toliau galime pažvelgti į pagrindines jo operacijas.

1. Paieškos operacija

Paieška leidžia mums rasti tam tikrą reikšmę medyje. Galime naudoti dviejų tipų paieškas: paiešką pagal plotį (BFS) ir paiešką pagal gylį (DFS). Paieška pagal plotį yra paieškos algoritmas, kuris prasideda nuo šakninio mazgo ir eina horizontaliai, iš vienos pusės į kitą, kol randamas tikslas. Šios paieškos metu kiekvienas mazgas aplankomas vieną kartą.

Kita vertus, paieška pagal gylį kerta medį vertikaliai – pradedant nuo šaknies mazgo ir nuleidžiant vieną šaką. Jei tikslas randamas, operacija baigiasi. Bet jei ne, ji ir ieško kitų mazgų.

2. Įterpimo operacija

Įterpimo operacija naudoja paieškos operaciją, kad nustatytų vietą, kur turėtų būti įterptas naujas mazgas. Procesas prasideda nuo šakninio mazgo, o paieška prasideda tol, kol pasiekiamas tikslas. Įterpiant reikia atsižvelgti į tris atvejus.

• 1 atvejis: kai mazgo nėra. Įterpiamas mazgas taps šakniniu mazgu.

• 2 atvejis: vaikų nėra. Tokiu atveju mazgas bus lyginamas su šakniniu mazgu. Jei jis didesnis, jis taps tinkamu vaiku; kitu atveju jis taps kairiuoju vaiku.

• 3 atvejis: kai yra šaknis ir jos vaikai. Naujasis mazgas bus lyginamas su kiekvienu jo kelyje esančiu mazgu, siekiant nustatyti, kurį mazgą jis aplankys toliau. Jei mazgas yra didesnis nei šakninis mazgas, jis eis žemyn dešiniuoju pomedžiu arba kairiuoju. Panašiai kiekviename lygyje atliekami palyginimai, siekiant nustatyti, ar jis eis į dešinę ar į kairę, kol pasieks savo tikslą.

3. Ištrynimo operacija

Ištrynimo operacija naudojama tam tikram medžio mazgui pašalinti. Ištrynimas laikomas sudėtingu, nes pašalinus mazgą, medį reikia atitinkamai pertvarkyti. Yra trys pagrindiniai atvejai, į kuriuos reikia atsižvelgti:

• 1 atvejis: lapo mazgo ištrynimas. Lapo mazgas yra mazgas be jokių vaikų. Tai lengviausia pašalinti, nes tai neturi įtakos jokiam kitam mazgui; tiesiog kertame medį, kol jį pasiekiame, ir ištriname.

• 2 atvejis: mazgo ištrynimas su vienu vaiku. Ištrynus pirminį elementą, turintį vieną mazgą, vaikas užims savo poziciją, o visi paskesni mazgai pakils vienu lygiu. Pomedžių struktūra nesikeis.

• 3 atvejis: mazgo su dviem vaikais ištrynimas. Kai turime pašalinti mazgą su dviem vaikais, pirmiausia turime rasti kitą mazgą, kuris galėtų užimti savo poziciją. Du mazgai gali pakeisti pašalintą mazgą, eilės įpėdinį arba pirmtaką. Eilės įpėdinis yra kairysis dešiniojo pomedžio vaikas, o eilės pirmtakas yra kairiojo pomedžio dešinysis vaikas. Nukopijuojame įpėdinio / pirmtako turinį į mazgą ir ištriname eilės įpėdinį / pirmtaką.

Susijęs: Kaip sukurti duomenų struktūras naudojant „JavaScript“ ES6 klases

Kaip pereiti dvejetainį paieškos medį

Perėjimas yra procesas, kurio metu naršome dvejetainį paieškos medį. Tai atliekama norint surasti konkretų elementą arba atspausdinti medžio kontūrą. Mes visada pradedame nuo šakninio mazgo ir turime sekti kraštus, kad patektume į kitus mazgus. Kiekvienas mazgas turėtų būti laikomas antriniu medžiu, o procesas kartojamas tol, kol aplankomi visi mazgai.

• Kelionė pagal užsakymą: Važiuojant eilės tvarka, žemėlapis bus sudarytas didėjančia tvarka. Šiuo metodu pradedame nuo kairiojo pomedžio ir tęsiame iki šaknies ir dešiniojo pomedžio.

• Išankstinis užsakymas: Taikant šį metodą, pirmiausia aplankomas šakninis mazgas, po to kairysis pomedis ir dešinysis pomedis.

• Apžiūra po užsakymo: Šis perėjimas apima paskutinį apsilankymą šakniniame mazge. Pradedame nuo kairiojo pomedžio, tada dešiniojo pomedžio ir tada šakninio mazgo.

Realaus pasaulio programos

Taigi, kaip mes naudojame dvejetainius paieškos medžio algoritmus? Kaip galima numanyti, jie itin efektyviai ieško ir rūšiuoja. Didžiausia dvinarių medžių stiprybė yra jų organizuota struktūra. Tai leidžia ieškoti nepaprastai greitai, per pusę sumažinant duomenų, kuriuos turime analizuoti, kiekį.

Dvejetainiai paieškos medžiai leidžia efektyviai palaikyti dinamiškai kintantį duomenų rinkinį organizuotoje formoje. Programoms, kuriose dažnai įterpiami ir pašalinami duomenys, jie labai naudingi. Vaizdo žaidimų varikliai naudoja algoritmą, pagrįstą medžiais, vadinamais dvejetainiu erdvės skaidiniu, kad būtų lengviau pateikti objektus tvarkingai. „Microsoft Excel“ ir dauguma skaičiuoklių programinės įrangos naudoja dvejetainius medžius kaip pagrindinę duomenų struktūrą.

Galbūt nustebsite sužinoję, kad Morzės kodas duomenims koduoti naudoja dvejetainį paieškos medį. Kita svarbi priežastis, dėl kurios dvejetainės paieškos medžiai yra tokie naudingi, yra įvairūs jų variantai. Dėl jų lankstumo buvo sukurta daugybė variantų, skirtų įvairioms problemoms išspręsti. Tinkamai naudojant, dvejetainiai paieškos medžiai yra puikus turtas.

Dvejetainiai paieškos medžiai: puikus atspirties taškas

Vienas iš pagrindinių būdų įvertinti inžinieriaus patirtį yra jo žinios ir duomenų struktūrų taikymas. Duomenų struktūros yra naudingos ir gali padėti sukurti efektyvesnę sistemą. Dvejetainiai paieškos medžiai yra puikus įvadas į duomenų struktūras bet kuriam pradedantiesiems kūrėjui.

15 „JavaScript“ masyvo metodų, kuriuos turėtumėte išmokti šiandien

Norite suprasti „JavaScript“ masyvus, bet negalite su jais susitvarkyti? Peržiūrėkite „JavaScript“ masyvo pavyzdžius.

Skaitykite toliau

Apie autorių