Video: NEW ODIA BHAJAN PURI SARAKARA BY SRICHARAN MOHANTY 2024
Un tip special de structură arborescentă este heapul binar, care plasează fiecare dintre elementele nodului într-o ordine specială. Arborele de căutare vă permite să căutați date rapid. Obținerea elementelor de date, plasarea lor în ordine ordonată într-un arbore și apoi căutarea acelui arbore este una dintre modalitățile mai rapide de a găsi informații.
Într-un heap binar, nodul rădăcină conține întotdeauna cea mai mică valoare. Când vizualizați ramurile, vedeți că ramurile de nivel superior sunt întotdeauna o valoare mai mică decât ramurile și frunzele de nivel inferior. Efectul este să păstreze arborele echilibrat și într-o ordine previzibilă, astfel că căutarea devine extrem de eficientă. Costul este în păstrarea copacului echilibrat.
Din toate sarcinile pe care le fac aplicațiile, căutarea este mai consumatoare de timp și, de asemenea, cea mai solicitată. Chiar dacă adăugarea de date (și sortarea acestora mai târziu) necesită o anumită perioadă de timp, beneficiul creării și menținerii unui set de date vine de la utilizarea acestuia pentru a efectua o muncă utilă, ceea ce înseamnă căutarea unor informații importante. În consecință, puteți obține uneori funcționalități CRUD mai puțin eficiente și chiar o rutină de sortare mai puțin optimă, dar căutările trebuie să se desfășoare cât mai eficient posibil. Singura problemă este că nici o căutare nu efectuează fiecare activitate cu o eficiență absolută, deci trebuie să cântăriți opțiunile pe baza a ceea ce vă așteptați să faceți ca parte a rutinelor de căutare.
Două dintre metodele mai eficiente de căutare implică utilizarea arborelui binar de căutare (BST) și a heapului binar. Ambele tehnici de căutare se bazează pe o structură arborescentă pentru a ține cheile folosite pentru a accesa elementele de date. Cu toate acestea, aranjamentul celor două metode este diferit, motiv pentru care unul are avantaje față de celălalt atunci când îndeplinește anumite sarcini. Această figură arată dispunerea unui BST.
Rețineți modul în care tastele respectă o ordine în care sunt afișate numere mai mici în partea stângă, iar numerele mai mari apar în dreapta. Nodul rădăcină conține o valoare care se află în mijlocul gamei de chei, oferind BST o abordare echilibrată ușor de înțeles pentru stocarea cheilor. Contrastați acest aranjament cu halda binară prezentată aici.
Fiecare nivel conține valori mai mici decât nivelul precedent, iar rădăcina conține valoarea maximă a tastei pentru arbore. În plus, în acest caz special, valorile mai mici apar în stânga și mai mare în dreapta (deși această ordine nu este strict impusă). Cifra descrie de fapt un heap max binar. Puteți crea, de asemenea, un heap min binar în care rădăcina conține cea mai mică valoare de cheie și fiecare nivel se construiește la valori mai mari, cu cele mai mari valori care apar ca parte a frunzelor.
După cum sa menționat anterior, BST are anumite avantaje față de heapul binar când este folosit pentru a efectua o căutare. Următoarea listă prezintă câteva din avantajele acestor avantaje:
- Căutarea unui element necesită un timp O (log n), în contrast cu timpul O (n) pentru un heap binar.
- Imprimarea elementelor în ordine necesită doar un timp O (log n), în contrast cu timpul O (n log n) pentru un heap binar.
- Găsirea podelei și a tavanului necesită timp O (log n).
- Localizarea elementului kth cel mai mic / cel mai mare necesită O (log n) timp când arborele este configurat corespunzător.
Dacă aceste momente sunt importante, depinde de cererea dvs. BST tinde să funcționeze cel mai bine în situațiile în care petreceți mai mult timp în căutarea și construirea mai puțin timp a copacului. O grămadă binară tinde să funcționeze cel mai bine în situații dinamice în care cheile se schimbă regulat. De asemenea, heapul binar oferă avantaje, așa cum este descris în următoarea listă:
- Crearea structurilor necesare necesită mai puține resurse deoarece grămezile binare se bazează pe array-uri, făcându-le și cache mai prietenoase.
- Construirea unui heap binar necesită O (n) timp, în contrast cu BST, care necesită timp O (n log n).
- Nu este necesară utilizarea pointerilor pentru a implementa arborele.
- Bazându-se pe variațiile de heifer binare (de exemplu, Fibonacci Heap) oferă avantaje cum ar fi creșterea și scăderea timpilor cheie de timp O (1).
