Razlika između binarnog stabla i binarnog stabla pretraživanja

Što je Binarno stablo?

Binarno drvo je hijerarhijska struktura podataka u kojoj svaki čvor ima nulu, jedno ili najviše dvoje djece. Svaki čvor sadrži pokazivač "lijevo", "desni" pokazivač i podatkovni element. Pokazivač korijena predstavlja gornji čvor na stablu. Svaki čvor u strukturi podataka izravno je povezan s proizvoljnim brojem čvorova na obje strane, koji se nazivaju djecom. Nulti pokazivač predstavlja binarno stablo. Ne postoji određeni nalog kako organizirati čvorove u binarnom stablu. Čvorovi koji nemaju dječje čvorove nazivaju se lisni čvorovi ili vanjski čvorovi.

Jednostavno rečeno, definira organiziranu funkciju označavanja na čvorovima, koja zauzvrat dodjeljuje neku slučajnu vrijednost svakom čvorištu. Sve što ima dvoje djece i jedan roditeljski čvor binarno je stablo. Binarna stabla koriste se za pohranu podataka koje na vašem osobnom računalu čine hijerarhiju poput datotečnog sustava. Za razliku od nizova, stabla nemaju gornju granicu broja čvorova jer su povezana pomoću pokazivača, poput povezanih lista. Glavne funkcije Binarnog stabla uključuju predstavljanje hijerarhijskih podataka, sortiranje popisa podataka, pružanje učinkovitih operacija umetanja / brisanja itd. Čvorovi stabala predstavljeni su pomoću struktura u C.

Što je Binarno stablo pretraživanja?

Binarno stablo pretraživanja je vrsta strukture podataka binarnog stabla u kojoj su čvorovi raspoređeni po redoslijedu, a potom se nazivaju i "uređeno binarno stablo". To je struktura podataka zasnovana na čvorima koja pruža učinkovit i brz način razvrstavanja, pretraživanja, pretraživanja podataka. Za svaki čvor elementi u lijevoj podrezi moraju biti manji ili jednaki ključu u njegovom nadređenom čvoru (LP). Ne bi trebalo biti dvostrukih ključeva. Jednostavno rečeno, to je posebna vrsta podataka binarnih stabala koja učinkovito pohranjuje i upravlja stavkama u memoriji.

Omogućuje brz pristup informacijama, umetanje i uklanjanje podataka, a može se koristiti i za implementaciju tablica za pretraživanje koje omogućuju pretraživanje predmeta po jedinstvenim tipkama, poput pretraživanja telefonskog broja osobe po imenu. Jedinstveni ključevi sortirani su na organiziran način, tako da se pregledavanje i ostale dinamičke operacije mogu izvoditi pomoću binarnog pretraživanja. Podržava tri glavne operacije: pretraživanje elemenata, umetanje elemenata i brisanje elemenata. Binarno stablo pretraživanja omogućava brzo pronalaženje elemenata pohranjenih u stablu jer se svaki ključ čvora temeljito uspoređuje s korijenskim čvorom koji odbacuje polovicu stabla.

Razlika između binarnog stabla i binarnog stabla pretraživanja

1. Definicija binarnog stabla i binarnog stabla pretraživanja - Binarno stablo je hijerarhijska struktura podataka u kojoj dijete može imati nulu, jedan ili najviše dva dječja čvorova; svaki čvor sadrži lijevi pokazivač, desni pokazivač i podatkovni element. Ne postoji određeni red kako organizirati čvorove na stablu. Stablo binarnog pretraživanja, s druge strane, je uređeno binarno stablo u kojem postoji relativni redoslijed kako čvorovi trebaju biti organizirani.
2. Struktura od Binarno stablo i stablo binarnog pretraživanja- Najviši čvor na stablu predstavlja pokazivač korijena u binarnom stablu, a lijevi i desni pokazivač predstavljaju manja stabla s obje strane. To je specijalizirani oblik stabla koji predstavlja podatke u strukturi stabala. Binarno stablo pretraživanja, s druge strane, vrsta je binarnog stabla u kojem su svi čvorovi u lijevom podreziju manji ili jednaki vrijednosti korijenskog čvora, a oni u desnom stablu su veći ili jednaki vrijednosti korijenskog čvora.
3. operacija od Binarno stablo i stablo binarnog pretraživanja- Binarno stablo može biti sve što ima dvoje djece i jednog roditelja. Uobičajene operacije koje se mogu izvoditi na binarnom stablu jesu umetanje, brisanje i prelazak. Stabla binarnog pretraživanja više su sortirana binarna stabla koja omogućuju brzo i učinkovito pretraživanje, umetanje i brisanje stavki. Za razliku od binarnih stabala, stabla binarnog pretraživanja svoje ključeve sortiraju pa pretraga obično implementira binarno pretraživanje za operacije.
4. vrste od Binarno stablo i stablo binarnog pretraživanja- Postoje različite vrste binarnih stabala, a uobičajene su "Potpuno binarno stablo", "Kompletno binarno stablo", "Savršeno binarno drvo" i "Prošireno binarno drvo". Neke uobičajene vrste stabala za binarno pretraživanje uključuju T-stabla, AVL stabla, Splay stabla, tango stabla, crveno-crna stabla itd..

Binarno stablo nasuprot stablu binarnog pretraživanja: usporedni grafikon

Sažetak Binarnog stabla i Binarnog stabla za pretraživanje

Dok oba simuliraju hijerarhijsku strukturu stabala koja predstavlja skup čvorova sa svakim čvorom koji predstavlja vrijednost, oni se međusobno prilično razlikuju u pogledu načina na koji se mogu implementirati i koristiti. Binarno stablo slijedi jedno jednostavno pravilo da svaki roditeljski čvor nema više od dva podređena čvora, dok je binarno stablo pretraživanja samo varijanta binarnog stabla koja slijedi relativni redoslijed kako čvorovi trebaju biti organizirani u stablu.