Wat is een zoekboom?

Een zoekboom is een gegevensstructuur die wordt gebruikt in computerprogrammering om een lijst met gegevens te bevatten en te organiseren. Elke zoekboom bestaat uit een geordende set knooppunten. Deze knooppunten kunnen worden aangesloten op nul of meerandere knooppunten. De afzonderlijke knooppunten bevatten enkele gegevens en links naar andere knooppunten. De gegevens die in de knooppunten van de boom zijn opgenomen, worden op een bepaalde manier op een bepaalde manier besteld om efficiënte algoritmen te laten zoeken,Plaats en verwijder met gemak knooppunten.

De knooppunten van een zoekboom worden beschreven met vier belangrijke termen. De bovenkant van een boom, waar het eerste knooppunt zich bevindt, wordt de wortel genoemd.Als een knooppunt links naar sub-knooppunten bevat, staat dat knooppunt bekend als een ouder. Knooppunten die onder de ouder zijn, worden kinderen genoemd, en elk knooppunt dat geen kinderknooppunten heeft, iseen blad genoemd. Dus een rootknooppunt wordt geïdentificeerd omdat het geen ouder heeft en bladknooppunten geen kinderen hebben.

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

Een factor die het gebruik van zoekbomen beïnvloedt, is de kwestie van evenwicht. Een uitgebalanceerde boom iseen waarin zowel de rechter als de linker kinderen van het rootknooppunt ofwel dezelfde diepte van onderliggende knooppunten bevatten of binnen een telling van elkaar zijn. De diepte van een boom is het aantal knooppunten vanhet laagste blad van een boom naar de wortel. Een onevenwichtige boom kan alle knooppunten aan slechts één kant hebben of alle knooppunten hebbenop een lineaire manier 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 zelfveranderend.Deze bomen gebruiken bewerkingen zoals boomrotatie om de balans te behouden en tegelijkertijd de volgorde van de gegevens in de bladeren te behouden. Hoewel het uitvoeren van boomrotaties een programma kan 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 boomgegevensstructuur een binaire zoekboom. Dit gegevenstype bestaat uit knooppunten die elk nul hebbennaar twee onderliggende knooppunten. Er is slechts één rootknooppunt en alle bladeren in de boom worden van links naar rechts geordend in oplopende waarden volgens de gegevens die ze bevatten. VeelAlgoritmen bestaan voor binaire zoekbomen die bestelgegevens heel eenvoudig kunnen maken.

Er is geen enkele standaard iMplementatie voor zoekboomknooppunten. De knooppunten kunnen worden weergegeven door een breed scala aan gegevensstructuren. Arrays van arrays kunnen worden gebruikt, zoals gekoppelde lijsten kunnen vermenigvuldigen. Vaak gebruikt een zoekboom een aangepastGegevensstructuur die is ontworpen om te helpen bij het voltooien van de noodzakelijke bewerkingen die door het programma worden gevraagd. Sommige standaard programmeerbibliotheken bevatten zelfs hun eigen interne implementaties van zoekbomen.