Belangrijk verschil - Binaire boom versus binaire zoekboom
Een gegevensstructuur is een systematische manier om gegevens te ordenen om ze efficiënt te gebruiken. Het ordenen van de gegevens met behulp van de gegevensstructuur zou de doorlooptijd of de uitvoeringstijd moeten verkorten. Ook moet de datastructuur een minimale hoeveelheid geheugen vereisen. Soms kunnen de gegevens in een boomstructuur worden gerangschikt. Een boom vertegenwoordigt een knoop die door randen is verbonden. Het bovenste knooppunt is de wortel. Elk knooppunt kan maximaal twee knooppunten hebben. Ze staan bekend als onderliggende knooppunten. Het knooppunt links van het bovenliggende knooppunt is het linker onderliggende knooppunt, terwijl het knooppunt rechts van het bovenliggende knooppunt het rechter knooppunt is. De binaire boom en de binaire zoekboom zijn twee boomgegevensstructuren. Een binaire boom is een type gegevensstructuur waarbij elk bovenliggend knooppunt maximaal twee onderliggende knooppunten kan hebben. De binaire zoekboom is een binaire boom waarin het linkerkind alleen knooppunten bevat met waarden die kleiner zijn dan of gelijk zijn aan het bovenliggende knooppunt, en waar het rechterkind alleen knooppunten bevat met waarden die groter zijn dan die van het bovenliggende knooppunt. Dat is het belangrijkste verschil. In tegenstelling tot datastructuren zoals arrays, hebben de binaire boom en de binaire zoekboom geen bovenlimiet voor het opslaan van gegevens.
Wat is binaire boom?
Bij het rangschikken van de gegevens in een boomstructuur, staat het knooppunt bovenaan de boom bekend als het wortelknooppunt. Er kan maar één wortel zijn voor de hele boom. Elk knooppunt behalve het hoofdknooppunt heeft een rand naar boven naar een knooppunt. Dit wordt het bovenliggende knooppunt genoemd. Het knooppunt onder de bovenliggende code wordt het onderliggende knooppunt genoemd. Elk bovenliggend knooppunt kan maximaal twee onderliggende knooppunten hebben. Ze worden een linkerkindknooppunt en rechterkindknooppunt genoemd. Een knoop zonder onderliggende knoop wordt een bladknoop genoemd. Er is geen specifieke manier om gegevens in de binaire boom te rangschikken. Er is een pad van het hoofdknooppunt naar elk knooppunt.
Figuur 01: Voorbeeld van binaire boom
Hierboven staat een voorbeeld van een binaire boom. Het element 2, in de top van de boom, is de wortel. Elk knooppunt heeft maximaal twee knooppunten. Als een boom lussen bevat of als een knooppunt meer dan twee knooppunten bevat, kan deze niet worden geclassificeerd als een binaire boom. Om van het ene knooppunt naar het andere te gaan, is er altijd één pad. De onderliggende knooppunten van hoofdknooppunt 2 zijn 7 en 5. Het is ook mogelijk dat een knooppunt geen knooppunten heeft. Maar elk knooppunt kan niet meer dan twee knooppunten hebben. Het juiste element van de root is 5. Dat element 5 is het bovenliggende knooppunt voor kindknooppunt 9. Het knooppunt 4 en 11 hebben geen onderliggende elementen. Daarom zijn het bladknopen.
De binaire boom wordt gebruikt om gegevens in hiërarchische volgorde op te slaan. Het is vergelijkbaar met de bestandsstructuur van de computer. De gegevensstructuur zoals een array kan een specifieke hoeveelheid gegevens opslaan. Maar in een binaire boom is er geen bovengrens voor het aantal knooppunten.
Wat is binaire zoekboom?
Een binaire zoekboom is een binaire boomgegevensstructuur. Net als bij een binaire boom, kan de binaire zoekboom ook twee knooppunten hebben. Elk knooppunt behalve het hoofdknooppunt heeft een rand naar boven naar een knooppunt. Dit wordt het bovenliggende knooppunt genoemd. Het knooppunt onder een gegeven dat is verbonden door de rand naar beneden, wordt het onderliggende knooppunt genoemd. Een knoop zonder onderliggende knoop wordt een bladknoop genoemd. Elk bovenliggend knooppunt kan maximaal twee knooppunten hebben. Er zijn child nodes die verwijzen naar een linker child node en een rechter child node. Het bovenste element wordt de root-node genoemd. Het linker kind bevat alleen knooppunten met waarden die kleiner zijn dan of gelijk zijn aan het bovenliggende knooppunt. Het juiste kind bevat alleen knooppunten met waarden groter dan of gelijk aan het bovenliggende knooppunt.
Figuur 02: Voorbeeld van binaire zoekboom
Het element 8 is het bovenste element. Daarom is het de root-node. Als 3 een bovenliggend knooppunt is, dan zijn 1 en 6 onderliggende knooppunten. De 1 is het linker onderliggende knooppunt, terwijl 6 het rechter onderliggende knooppunt is. Het linker kind bevat waarden die kleiner zijn dan of gelijk zijn aan het bovenliggende knooppunt. Als 3 het bovenliggende knooppunt is, moet de linkerkant een element hebben dat kleiner is dan of gelijk is aan 3. In dit voorbeeld is het 1. Het rechterkind bevat alleen knooppunten met waarden die groter zijn dan het bovenliggende knooppunt. Wanneer 3 het bovenliggende knooppunt is, zou het rechter onderliggende knooppunt een hogere waarde dan 3 moeten hebben. In dit voorbeeld is dit 6. Evenzo is er een bepaalde volgorde om elk gegevenselement in een binaire zoekboom te rangschikken. Het is een gegevensstructuur die een efficiënte manier biedt om gegevens te sorteren, op te halen en te zoeken.
Wat zijn de overeenkomsten tussen binaire boom en binaire zoekboom?
- Zowel de binaire structuur als de binaire zoekstructuur zijn hiërarchische gegevensstructuren.
- Zowel de binaire boom als de binaire zoekboom hebben een root.
- Zowel de binaire structuur als de binaire zoekstructuur kunnen maximaal twee onderliggende knooppunten hebben.
Wat is het verschil tussen binaire boom en binaire zoekboom?
Binaire boom versus binaire zoekboom |
|
| Een binaire boom is een type gegevensstructuur waarbij elk bovenliggend knooppunt maximaal twee onderliggende knooppunten kan hebben. | De binaire zoekboom is een binaire boom waarin het linkerkind alleen knooppunten bevat met waarden die kleiner zijn dan of gelijk zijn aan het bovenliggende knooppunt, en waar het rechterkind alleen knooppunten bevat met waarden die groter zijn dan het bovenliggende knooppunt. |
| Gegevens ordenen | |
| Een binaire boom heeft geen specifieke volgorde om de gegevenselementen te rangschikken. | Een binaire zoekboom heeft een specifieke volgorde om de gegevenselementen te rangschikken. |
| Gebruik | |
| Een binaire boom wordt gebruikt voor het efficiënt opzoeken van gegevens en informatie in een boomstructuur. | Een binaire zoekboom wordt gebruikt voor het invoegen, verwijderen en doorzoeken van de gegevens. |
Samenvatting – Binaire boom versus binaire zoekboom
Een datastructuur is een manier om data te organiseren. Soms kunnen de gegevens in een boomstructuur worden gerangschikt. Twee daarvan zijn de binaire boom en de binaire zoekboom. Dit artikel besprak het verschil tussen de binaire boom en de binaire zoekboom. Een binaire boom is een type gegevensstructuur waarbij elk bovenliggend knooppunt maximaal twee onderliggende knooppunten kan hebben. De binaire zoekboom is een binaire boom waarin het linkerkind alleen knooppunten bevat met waarden die kleiner zijn dan of gelijk zijn aan het bovenliggende knooppunt, en waar het rechterkind alleen knooppunten bevat met waarden die groter zijn dan het bovenliggende knooppunt.
Download de PDF van Binary Tree vs Binary Search Tree
U kunt de PDF-versie van dit artikel downloaden en gebruiken voor offline doeleinden volgens de citatienota. Download hier de PDF-versie: Verschil tussen binaire boom en binaire zoekboom
