Innehållsförteckning:
- Definition - Vad betyder självbalanserande binärt sökträd?
- Techopedia förklarar Self-Balancing Binary Search Tree
Definition - Vad betyder självbalanserande binärt sökträd?
Ett självbalanserande binärt sökträd är en typ av datastruktur som självjusterar för att ge konsekventa nivåer av nodåtkomst. I ett självbalanserande binärt sökträd sorteras och justeras anslutningarna från den övre noden till ytterligare noder så att trädet är jämnt och sökbanelinjerna för varje slutnod är lika långa.
Ett självbalanserande binärt sökträd kallas också ett balanserat träd eller höjdbalanserat binärt sökträd.
Techopedia förklarar Self-Balancing Binary Search Tree
Ett binärt sökträd generellt ger en datastruktur med en nod överst och antingen en eller två noder anslutna till den på varje efterföljande nivå. Binära sökträd stödjer tre operationer - operatörer kan infoga komponenter, radera komponenter eller slå upp ett antal eller annat nodinnehåll. En del av fördelen med binära sökträd är att systemet kan sortera för att ignorera hälften av trädet på varje nivå, vilket leder till effektivare sökarbetsbelastningar.
Den positiva aspekten av ett självbalanserande binärt sökträd är att nodåtkomst är lika - till exempel istället för att behöva gå fem steg på en sida av trädet, eller tre steg på andra sidan av trädet på grund av jaget -justerad nodstruktur, sökningen skulle bara gå ett visst antal steg (n) till en given slutnod. Detta uppnås genom att ta ut enskilda nodanslutningar och ersätta dem med binära för att förkorta vissa lemmar i trädet.
Nackdelen med en självbalanserande binär sökning tre är att den bara fungerar om nodanslutningarna är "nivå-agnostiska" - med andra ord, om en individuell nod kan justeras om till en tidigare nivå för att förkorta trädgrenen . Om till exempel ett självbalanserande binärt sökträd är sammansatt med ett givet nummer överst och två efterföljande siffror på vardera sidan, och det finns en kedja med tre ytterligare nummer med en enda nodanslutningar, skulle justeringen av trädet sätta den femte noden tillsammans med den tredje noden istället för den fjärde noden, så att den tredje noden har två anslutningsnoder istället för en. Men om datastrukturen behöver identifiera specifikt nodinnehåll som relaterat i ett specifikt förälder / barn-förhållande, kommer inte justering av dessa noder att passa trästrukturens jämnhet att fungera.
