Innholdsfortegnelse:
- Definisjon - Hva betyr selvbalanserende binært søketre?
- Techopedia forklarer Self-Balancing Binary Search Tree
Definisjon - Hva betyr selvbalanserende binært søketre?
Et selvbalanserende binært søketre er en type datastruktur som selvjusteres for å gi konsistente nivåer av nodetilgang. I et selvbalanserende binært søketre blir tilkoblingene fra den øverste noden til flere noder sortert og justert på nytt slik at treet er jevnt, og søkebanelinjene for hver sluttnode er like lengde.
Et selvbalanserende binært søketre er også kjent som et balansert tre eller høydebalansert binært søketre.
Techopedia forklarer Self-Balancing Binary Search Tree
Et binært søketre gir generelt en datastruktur med en node øverst, og enten en eller to noder koblet til det på hvert påfølgende nivå. Binære søketrær støtter tre operasjoner - operatører kan sette inn komponenter, slette komponenter eller slå opp et antall eller annet nodeinnhold. En del av fordelen med binære søketrær er at systemet kan sortere for å ignorere halvparten av treet på hvert nivå, noe som fører til mer effektive arbeidsmengder.
Det positive ved et selvbalanserende binært søketre er at nodetilgangen er lik - for eksempel i stedet for å måtte gå fem trinn på den ene siden av treet, eller tre trinn på den andre siden av treet, på grunn av jeget -justert nodestruktur, ville søket bare gå et visst antall trinn (n) til en gitt sluttnode. Dette oppnås ved å ta ut individuelle nodetilkoblinger og erstatte dem med binære koblinger for å forkorte spesielle lemmer på treet.
Ulempen med et selvbalanserende binært søk tre er at det bare fungerer hvis knutetilkoblingene er “nivå-agnostisk” - med andre ord, hvis en individuell node kan justeres til et tidligere nivå for å forkorte tregrenen . For eksempel, hvis et selvbalanserende binært søketre er sammensatt med et gitt nummer øverst, og to påfølgende tall på hver side, og det er en kjede med tre tilleggstall med en enkelt knutetilkobling, ville justeringen av treet sette den femte noden sammen med den tredje noden i stedet for den fjerde noden, slik at den tredje noden har to forbindelsesnoder i stedet for en. Men hvis datastrukturen trenger å identifisere bestemt nodeinnhold som relatert i et spesifikt foreldre / barn-forhold, vil ikke justering av disse nodene for å passe trestrukturens jevnhet fungere.
