Põhierinevus – binaarne puu vs binaarne otsingupuu
Andmestruktuur on süstemaatiline viis andmete korraldamiseks, et neid tõhus alt kasutada. Andmete korrastamine andmestruktuuri abil peaks vähendama töö- või täitmisaega. Samuti peaks andmestruktuur nõudma minimaalset mälumahtu. Mõnikord saab andmeid paigutada puustruktuuri. Puu tähistab servadega ühendatud sõlme. Kõige ülemine sõlm on juur. Igal sõlmel võib olla maksimaalselt kaks sõlme. Neid tuntakse lapsesõlmedena. Vanemsõlmest vasakul asuv sõlm on vasakpoolne alamsõlm, samas kui emasõlmest paremal asuv sõlm on parem sõlm. Binaarne puu ja binaarne otsingupuu on kaks puu andmestruktuuri. Binaarne puu on andmestruktuur, kus igal ülemsõlmel võib olla kuni kaks alamsõlme. Binaarne otsingupuu on kahendpuu, kus vasakpoolne alamsõlme sisaldab ainult sõlmi, mille väärtused on väiksemad või sellega võrdsed, ja kus parempoolses alamsõlmes on ainult sõlmed, mille väärtused on suuremad kui emasõlme väärtused. See on peamine erinevus. Erinev alt andmestruktuuridest, nagu massiivid, ei ole binaarsel puul ja binaarsel otsingupuul andmete salvestamiseks ülempiiri.
Mis on kahendpuu?
Andmete järjestamisel puustruktuuris nimetatakse puu ülaosas olevat sõlme juursõlmeks. Kogu puu kohta saab olla ainult üks juur. Igal sõlmel, välja arvatud juursõlm, on üks serv ülespoole sõlmeni. Seda nimetatakse emasõlmeks. Vanemkoodi all olevat sõlme nimetatakse selle alamsõlmeks. Igal ülemsõlmel võib olla maksimaalselt kaks alamsõlme. Neid nimetatakse vasakpoolseks alamsõlmeks ja parempoolseks alamsõlmeks. Ilma alamsõlmeta sõlme nimetatakse lehesõlmeks. Puudub kindel viis andmete korraldamiseks binaarpuus. Juursõlmest iga sõlmeni on tee.
Joonis 01: binaarpuu näide
Üleval on näide kahendpuust. Element 2 puu ülaosas on juur. Igal sõlmel on maksimaalselt kaks sõlme. Kui puu sisaldab silmuseid või kui üks sõlm sisaldab rohkem kui kahte sõlme, ei saa seda liigitada kahendpuuks. Ühest sõlmest teise liikumiseks on alati üks tee. Juuresõlme 2 alamsõlmed on 7 ja 5. Samuti on võimalik, et sõlmel puuduvad sõlmed. Kuid ühelgi sõlmel ei saa olla rohkem kui kaks sõlme. Juure parem element on 5. See element 5 on alamsõlme 9 vanemsõlm. Sõlmedel 4 ja 11 pole alamelemente. Seetõttu on need lehtede sõlmed.
Binaarset puud kasutatakse andmete salvestamiseks hierarhilises järjekorras. See sarnaneb arvuti failistruktuuriga. Andmestruktuur nagu massiiv võib salvestada teatud hulga andmeid. Kuid kahendpuus pole sõlmede arvul ülempiiri.
Mis on binaarne otsingupuu?
Binaarne otsingupuu on kahendpuu andmestruktuur. Sarnaselt binaarsele puule võib ka binaarsel otsingupuul olla kaks sõlme. Igal sõlmel, välja arvatud juursõlm, on üks serv ülespoole sõlmeni. Seda nimetatakse emasõlmeks. Antud punkti all olevat sõlme, mis on ühendatud selle servaga allapoole, nimetatakse selle alamsõlmeks. Ilma alamsõlmeta sõlme nimetatakse lehesõlmeks. Igal vanemsõlmel võib olla maksimaalselt kaks sõlme. Seal on alamsõlmed, mis viitavad vasakpoolsele alamsõlmele ja paremale alamsõlmele. Kõige ülemist elementi nimetatakse juursõlmeks. Vasakpoolne alamsõlm sisaldab ainult sõlme, mille väärtused on väiksemad või võrdsed põhisõlmega. Õige alamsõlme sisaldab ainult sõlmi, mille väärtused on suuremad või võrdsed ülemsõlmest.
Joonis 02: Binaarse otsingupuu näide
Element 8 on kõige ülemine element. Seetõttu on see juursõlm. Kui 3 on põhisõlm, siis 1 ja 6 on alamsõlmed. 1 on vasakpoolne alamsõlm, samas kui 6 on parem alamsõlm. Vasakpoolne alampunkt sisaldab väärtusi, mis on väiksemad või võrdsed ülemsõlmega. Kui vanemsõlm on 3, peaks vasakpoolsel küljel olema element, mis on väiksem kui 3 või sellega võrdne. Selles näites on see 1. Parempoolne alamsõlm sisaldab ainult sõlme, mille väärtused on suuremad kui emasõlm. Kui 3 on emasõlm, peaks parempoolsel alamsõlmel olema suurem väärtus kui 3. Selles näites on see 6. Samamoodi on iga andmeelemendi binaarseks otsingupuuks korraldamiseks kindel järjekord. See on andmestruktuur, mis pakub tõhusat viisi andmete sortimiseks, toomiseks ja otsimiseks.
Millised on kahendpuu ja binaarse otsingupuu sarnasused?
- Nii kahendpuu kui ka kahendotsingu puu on hierarhilised andmestruktuurid.
- Nii kahendpuul kui ka binaarsel otsingupuul on juur.
- Nii kahendpuul kui ka binaarsel otsingupuul võib olla maksimaalselt kaks alamsõlme.
Mis vahe on kahendpuul ja binaarsel otsingupuul?
Binaarne puu vs binaarne otsingupuu |
|
| Binaarpuu on andmestruktuuri tüüp, kus igal ülemsõlmel võib olla maksimaalselt kaks alamsõlme. | Binaarne otsingupuu on kahendpuu, kus vasakpoolne alamsõlm sisaldab ainult sõlmi, mille väärtused on väiksemad või sellega võrdsed, ja parempoolne alamsõlme sisaldab ainult sõlme, mille väärtused on suuremad kui emasõlme. |
| Andmete korraldamise järjekord | |
| Binaarpuul ei ole andmeelementide järjestamiseks kindlat järjekorda. | Binaarsel otsingupuul on andmeelementide järjestamiseks kindel järjekord. |
| Kasutus | |
| Binaarpuud kasutatakse puustruktuuris andmete ja teabe tõhusaks otsimiseks. | Andmete sisestamiseks, kustutamiseks ja otsimiseks kasutatakse binaarset otsingupuud. |
Kokkuvõte – binaarne puu vs binaarne otsingupuu
Andmestruktuur on andmete korraldamise viis. Mõnikord saab andmeid paigutada puustruktuuri. Kaks neist on kahendpuu ja binaarne otsingupuu. Selles artiklis käsitleti binaarse puu ja binaarse otsingupuu erinevust. Binaarne puu on andmestruktuur, kus igal ülemsõlmel võib olla kuni kaks alamsõlme. Binaarne otsingupuu on kahendpuu, kus vasakpoolne alamsõlm sisaldab ainult sõlmi, mille väärtused on väiksemad või sellega võrdsed, ja kus parempoolne alamsõlme sisaldab ainult sõlmi, mille väärtused on ülemsõlmest suuremad.
Laadige alla binaarne puu vs binaarne otsingupuu PDF
Saate alla laadida selle artikli PDF-versiooni ja kasutada seda võrguühenduseta kasutamiseks vastav alt tsitaadi märkusele. Laadige PDF-versioon alla siit: Binaarse puu ja binaarse otsingupuu erinevus
