Slik fjerner noder fra en Binary treet

Binære trær er samlinger av "noder" som er koblet i en struktur som ligner et tre der hver gren har to eller færre baner. En node er en blokk med minne som inneholder spor for informasjon pluss to "pekere". En peker er et spor som er akkurat stor nok til å inneholde adressen til to andre noder. Den første noden i treet kalles rot; den inneholder pekere til to andre noder, og hver av disse har to pekere til andre noder, og så videre inntil et "blad" node er nådd - en node som ikke inneholder pekere til andre noder.

Bruksanvisning

1 Søk etter bladet du ønsker å fjerne. Dette vil være et spørsmål om å se gjennom treet til du finner noden med riktig indeksen. Hvis treet er tilrettelagt slik at den venstre undertreet inneholder alle postene med en mindre indeks av tall og retten treet inneholder alle postene med større indekser, kan du gå rett til bladet du ønsker å fjerne. Hvis nodene ikke er i noen form for orden, vil du vanligvis har til å se gjennom halvparten av treet.

2 Hold styr på to pekere. Adressene til postene er ofte kalt pekere fordi de "pek på" posten. Som du søke etter posten du vil slette, må du holde styr på to pekere - den som peker til den gjeldende rekord og en som peker til den forrige rekorden. Dette er fordi når du finne målet posten, må du gjøre en endring til en adresse i den forrige rekorden - adressen som peker til den posten du vil slette. For å gjøre denne endringen, må du ha en peker til den posten hvor du gjør endringen.

3 Endre pekeren til bladet du skal fjerne en blank. Du vil også trenge å returnere minnet som ble brukt til å holde bladet posten. Når du bygger treet, må du be om en "node" for hver post du vil legge til, og når du sletter et blad, må du returnere den plass som holdt den. Operativsystemet holder orden på minnetildeling og gjenvinning. Trær vokser og krymper etter hvert som du bruker dem. Hvordan du ber om nye noder, resirkulere noder og til og med tomme-out adresser avhenger av programmeringsspråk du bruker.

Hint

• Søke et tre er mye raskere hvis treet er "balansert" - Hvis venstre og høyre subtre er omtrent samme størrelse. Noen ganger trær rebalanseres over natten for å være klar for neste dag.
• Oppdatere to pekere kan være vanskelig. Begge pekere starte med å peke til roten. På det første skrittet på "dagens" pekeren er avansert, men den "forrige" peker fortsatt peker til roten. Fra da av, på slutten av hvert trinn, kopiere gjeldende pekeren til forrige pekeren og sette den nye pekeren i som den nåværende pekeren. Hvis du ikke gjør det på akkurat denne måten, vil algoritmen ikke fungerer.