Wat is een zoekboom?

Een zoekboom is een gegevensstructuur die in computerprogrammering wordt gebruikt om een ​​lijst met gegevens te bevatten en te organiseren. Elke zoekboom bestaat uit een geordende set knooppunten. Deze knooppunten kunnen met nul of meer worden verbonden. De afzonderlijke knooppunten bevatten zowel gegevens als koppelingen naar andere knooppunten. De gegevens in de knooppunten van de boomstructuur worden vaak op een bepaalde manier geordend om efficiënte algoritmen te laten zoeken, plaats en verwijder eenvoudig knooppunten.

De knooppunten van een zoekboom worden beschreven met vier belangrijke termen: de bovenkant van een boom, waar de eerste knoop zich bevindt, wordt de root genoemd. Als een knoop links naar sub bevat -knooppunten, dat knooppunt staat bekend als een ouder. Knooppunten die zich onder het bovenliggende element bevinden, worden kinderen genoemd, en elke knooppunt zonder kindknooppunten wordt een blad genoemd. een basisknooppunt wordt geïdentificeerd omdat het geen ouder heeft en bladknooppunten geen kinderen zullen hebben.

Een programma kan door een boom bladeren op zoek naar gegevens door te beginnen bij een bepaald knooppunt, een voorwaardelijke controle uit te voeren en vervolgens naar het volgende logische knooppunt te gaan als de vereiste gegevens niet aanwezig zijn. , kan deze zoekopdracht een variabele tijd duren. Als de zoekboom is georganiseerd tijdens het toevoegen en verwijderen van knooppunten, kan de zoekactie zeer snel zijn. Wanneer een boom is samengesteld willekeurig, is ongesorteerd of staat meerdere ouders toe, het zoeken kan erg lang duren.

Een factor die het gebruik van zoekbomen beïnvloedt, is het probleem van evenwicht: een gebalanceerde boom is een boom waarin zowel de rechter- als de linkerkinderen van de hoofdknoop dezelfde diepte van onderliggende knooppunten bevatten of binnen een telling van één knooppunt van elkaar. De diepte van een boom is het aantal knooppunten van het laagste blad van een boom tot de wortel. Een ongebalanceerde boom kan alle knooppunten aan slechts één zijde hebben of alle de knooppunten zijn lineair gerangschikt zonder takken. Wanneer de diepte van een boom toeneemt, kan de snelheid van zoekalgoritmen dramatisch afnemen.

Er zijn bepaalde soorten zoekbomen die worden beschreven als zelfbalancerend.Deze bomen gebruiken bewerkingen zoals boomrotatie om het evenwicht te behouden terwijl de volgorde van de gegevens in de bladeren behouden blijft. boomrotaties kunnen een programma vertragen bij het toevoegen en verwijderen van knooppunten, dit wordt tegengegaan door de snelheid waarmee gegevens kunnen worden opgehaald.

Hoewel er veel soorten zoekbomen zijn, is de meest voorkomende boomstructuur een binaire zoekboom. Dit gegevenstype bestaat uit knooppunten die elk nul tot twee onderliggende knooppunten hebben. Er is slechts één hoofdknooppunt, en alle bladeren in de boom zijn van links naar rechts geordend in oplopende waarden volgens de gegevens die ze bevatten. Veel algoritmen bestaan ​​voor binaire zoekbomen die kunnen maak bestelgegevens heel gemakkelijk.

Er is geen enkele standaardimplementatie voor zoekboomknooppunten. De knooppunten kunnen worden weergegeven door een grote verscheidenheid aan gegevensstructuren. Arrays van arrays kunnen worden gebruikt, net als vermenigvuldigde gekoppelde lijsten. Vaak is een Search Tree gebruikt een aangepaste gegevensstructuur die is ontworpen om te helpen bij het voltooien van de benodigde bewerkingen die door het programma worden gevraagd.Sommige standaard programmabibliotheken bevatten zelfs hun eigen interne implementaties van zoekbomen.