Ključna razlika – binarno stablo naspram binarnog stabla pretraživanja
Struktura podataka sustavan je način organiziranja podataka za njihovo učinkovito korištenje. Uređivanje podataka korištenjem strukture podataka trebalo bi smanjiti vrijeme izvođenja ili vrijeme izvođenja. Također, struktura podataka treba zahtijevati minimalnu količinu memorije. Ponekad se podaci mogu posložiti u strukturu stabla. Stablo predstavlja čvor povezan bridovima. Najviši čvor je korijen. Svaki čvor može imati najviše dva čvora. Oni su poznati kao dijete čvorovi. Čvor lijevo od nadređenog čvora je lijevi podređeni čvor dok je čvor desno od nadređenog čvora desni čvor. Binarno stablo i binarno stablo pretraživanja dvije su strukture podataka stabla. Binarno stablo je vrsta strukture podataka gdje svaki nadređeni čvor može imati najviše dva podređena čvora. Binarno stablo pretraživanja je binarno stablo gdje lijevo dijete sadrži samo čvorove s vrijednostima manjim ili jednakim nadređenom čvoru, a desno dijete sadrži samo čvorove s vrijednostima većim od nadređenog čvora. To je ključna razlika. Za razliku od podatkovnih struktura kao što su nizovi, binarno stablo i binarno stablo pretraživanja nemaju gornju granicu za pohranu podataka.
Što je binarno stablo?
Kada raspoređujete podatke u strukturu stabla, čvor na vrhu stabla poznat je kao korijenski čvor. Za cijelo stablo može postojati samo jedan korijen. Svaki čvor osim korijenskog čvora ima jedan rub prema gore prema čvoru. Zove se roditeljski čvor. Čvor ispod nadređenog koda naziva se njegov podređeni čvor. Svaki nadređeni čvor može imati najviše dva podređena čvora. Oni se nazivaju lijevi podređeni čvor i desni podređeni čvor. Čvor bez čvora djeteta naziva se čvor lista. Ne postoji poseban način za raspoređivanje podataka u binarnom stablu. Postoji put od korijenskog čvora do svakog čvora.
Slika 01: Primjer binarnog stabla
Gore je primjer binarnog stabla. Element 2, na vrhu stabla, je korijen. Svaki čvor ima najviše dva čvora. Ako stablo sadrži bilo kakve petlje ili ako jedan čvor sadrži više od dva čvora, ne može se klasificirati kao binarno stablo. Za prelazak s jednog čvora na drugi uvijek postoji jedan put. Čvorovi dijete korijenskog čvora 2 su 7 i 5. Također je moguće da čvor nema čvorova. Ali bilo koji čvor ne može imati više od dva čvora. Desni element korijena je 5. Taj element 5 je nadređeni čvor za podređeni čvor 9. Čvor 4 i 11 nemaju podređene elemente. Stoga su oni lisnati čvorovi.
Binarno stablo se koristi za pohranu podataka u hijerarhijskom redu. Slična je datotečnoj strukturi računala. Struktura podataka poput polja može pohraniti određenu količinu podataka. Ali u binarnom stablu ne postoji gornja granica broja čvorova.
Što je stablo binarnog pretraživanja?
Binarno stablo pretraživanja je struktura podataka binarnog stabla. Slično binarnom stablu, binarno stablo pretraživanja također može imati dva čvora. Svaki čvor osim korijenskog čvora ima jedan rub prema gore prema čvoru. Zove se roditeljski čvor. Čvor ispod datog spojen rubom prema dolje naziva se njegov podređeni čvor. Čvor bez čvora djeteta naziva se čvor lista. Svaki nadređeni čvor može imati najviše dva čvora. Postoje podređeni čvorovi koji se odnose na lijevi podređeni čvor i desni podređeni čvor. Najviši element naziva se korijenski čvor. Lijevi podređeni element sadrži samo čvorove s vrijednostima manjim ili jednakim nadređenom čvoru. Desno dijete sadrži samo čvorove s vrijednostima većim ili jednakim nadređenom čvoru.
Slika 02: Primjer stabla binarnog pretraživanja
Element 8 je najviši element. Stoga je to korijenski čvor. Ako je 3 nadređeni čvor, tada su 1 i 6 podređeni čvorovi. 1 je lijevi podređeni čvor dok je 6 desni podređeni čvor. Lijevi dijete sadrži vrijednosti manje ili jednake nadređenom čvoru. Kada je 3 nadređeni čvor, lijeva strana treba imati element koji je manji ili jednak 3. U ovom primjeru, to je 1. Desno dijete sadrži samo čvorove s vrijednostima većim od nadređenog čvora. Kada je 3 nadređeni čvor, desni podređeni čvor trebao bi imati višu vrijednost od 3. U ovom primjeru, to je 6. Isto tako, postoji određeni redoslijed za raspoređivanje svakog podatkovnog elementa u binarno stablo pretraživanja. To je struktura podataka koja pruža učinkovit način za razvrstavanje, dohvaćanje i pretraživanje podataka.
Koje su sličnosti između binarnog stabla i binarnog stabla pretraživanja?
- I binarno stablo i binarno stablo pretraživanja hijerarhijske su strukture podataka.
- I binarno stablo i binarno stablo pretraživanja imaju korijen.
- I binarno stablo i binarno stablo pretraživanja mogu imati najviše dva podređena čvora.
Koja je razlika između binarnog stabla i binarnog stabla pretraživanja?
Binarno stablo naspram binarnog stabla pretraživanja |
|
| Binarno stablo je vrsta strukture podataka gdje svaki nadređeni čvor može imati najviše dva podređena čvora. | Stablo binarnog pretraživanja je binarno stablo gdje lijevo dijete sadrži samo čvorove s vrijednostima manjim ili jednakim nadređenom čvoru, a desno dijete sadrži samo čvorove s vrijednostima većim od nadređenog čvora. |
| Redoslijed sređivanja podataka | |
| Binarno stablo nema određeni redoslijed za raspoređivanje podatkovnih elemenata. | Stablo binarnog pretraživanja ima određeni redoslijed za raspoređivanje podatkovnih elemenata. |
| Upotreba | |
| Binarno stablo se koristi kao učinkovito pretraživanje podataka i informacija u strukturi stabla. | Stablo binarnog pretraživanja koristi se za umetanje, brisanje i pretraživanje podataka. |
Sažetak – binarno stablo naspram binarnog stabla pretraživanja
Struktura podataka je način organiziranja podataka. Ponekad se podaci mogu posložiti u strukturu stabla. Dvije od njih su binarno stablo i binarno stablo pretraživanja. Ovaj članak raspravlja o razlici između binarnog stabla i binarnog stabla pretraživanja. Binarno stablo je vrsta strukture podataka gdje svaki nadređeni čvor može imati najviše dva podređena čvora. Binarno stablo pretraživanja je binarno stablo gdje lijevo dijete sadrži samo čvorove s vrijednostima manjim ili jednakim nadređenom čvoru, a desno dijete sadrži samo čvorove s vrijednostima većim od nadređenog čvora.
Preuzmite PDF binarnog stabla naspram binarnog stabla pretraživanja
Možete preuzeti PDF verziju ovog članka i koristiti ga za izvanmrežne svrhe prema napomeni o citatu. Ovdje preuzmite PDF verziju: Razlika između binarnog stabla i binarnog stabla pretraživanja
