Video: 15 Cool Amphibious Vehicles and Multi-Purpose Vehicles 2024
En spesiell type trestruktur er binærhunne, som plasserer hver av nodelementene i en spesiell rekkefølge. Søk trær lar deg lete etter data raskt. Å skaffe dataelementer, plassere dem i rekkefølge i et tre, og deretter søke det treet er en av de raskere måtene å finne informasjon.
I en binær haug inneholder rotnoden alltid den minste verdien. Når du ser på grener, ser du at øvre grener er alltid en mindre verdi enn grener og blader på lavere nivå. Effekten er å holde treet balansert og i en forutsigbar rekkefølge slik at søkingen blir ekstremt effektiv. Kostnaden er å holde treet balansert.
Av alle oppgavene som applikasjoner gjør, søker er jo mer tidkrevende og også den mest nødvendige. Selv om du legger til data (og sortering det senere) krever litt tid, vil fordelen ved å opprette og vedlikeholde datasett komme fra å bruke den til å utføre nyttig arbeid, noe som betyr at du søker etter viktig informasjon. Derfor kan du noen ganger komme forbi med mindre effektiv CRUD-funksjonalitet og til og med en mindre enn optimal sorteringsrutine, men søkene må fortsette så effektivt som mulig. Det eneste problemet er at ingen søk utfører hver oppgave med absolutt effektivitet, så du må veie alternativene dine basert på hva du forventer å gjøre som en del av søkerutene.
To av de mer effektive søkemåtene innebærer bruk av binær søketreet (BST) og binær bunke. Begge søketeknikker er avhengig av en trelignende struktur for å holde nøklene som brukes til å få tilgang til dataelementer. Imidlertid er arrangementet av de to metodene forskjellige, og derfor har man fordeler over det andre når man utfører visse oppgaver. Denne figuren viser arrangementet for en BST.
Legg merke til hvordan tastene følger en rekkefølge hvor færre tall vises til venstre, og større tall vises til høyre. Rotnoden inneholder en verdi som ligger midt i rekkevidden av nøkler, noe som gir BST en lett forståelig balansert tilnærming til lagring av nøklene. Kontrast dette arrangementet til den binære bunken som vises her.
Hvert nivå inneholder verdier som er mindre enn forrige nivå, og roten inneholder den maksimale nøkkelverdien for treet. I tillegg, i dette tilfellet vises de mindre verdiene til venstre og jo større til høyre (selv om denne ordren ikke er strengt håndhevet). Figuren viser faktisk en binær maxhøyde. Du kan også opprette en binær minhunne der roten inneholder den laveste nøkkelverdien, og hvert nivå bygger til høyere verdier, med de høyeste verdiene som vises som en del av bladene.
Som tidligere nevnt, har BST noen fordeler over binær haug når den brukes til å utføre et søk. Følgende liste gir noen av høydepunktene av disse fordelene:
- Søker etter et element krever O (log n) tid, i motsetning til O (n) tid for en binær haug.
- Utskrift av elementene i rekkefølge krever kun O (log n) tid, i motsetning til O (n log n) tid for en binær haug.
- Finne gulv og tak krever O (log n) tid.
- Finne Kth minste / største elementet krever O (log n) tid når treet er riktig konfigurert.
Om disse tider er viktige, avhenger av søknaden din. BST har en tendens til å fungere best i situasjoner der du bruker mer tid på å søke og mindre tid å bygge treet. En binær haug har en tendens til å fungere best i dynamiske situasjoner der nøkler endres jevnlig. Den binære bunken gir også fordeler, som beskrevet i følgende liste:
- Å lage de nødvendige strukturer krever færre ressurser fordi binære hauger stole på arrays, noe som gjør dem også cachevennerligere.
- Å bygge en binær haug krever O (n) tid, i motsetning til BST, som krever O (n log n) tid.
- Det er ikke nødvendig å bruke pekere for å implementere treet.
- Basert på binære haugvariasjoner (for eksempel Fibonacci Heap), tilbyr du fordeler som økning og reduksjon av nøkkeltider for O (1) tid.
