Hvordan slette en node binært søketre

Binære søketrær brukes til å organisere sekvensiell data for enkel gjenfinning. Hver node i et binært søketre har mellom null og to barn. Den venstre barnet for en node er alltid mindre enn noden og den høyre barnet er alltid større. Dermed når vi søker etter en bestemt node, kan vi sammenligne vårt mål til gjeldende node. Hvis målet er større enn gjeldende node vi fortsette å søke på høyre gren, hvis målet er mindre enn gjeldende node vi søke nedover venstre grenen. Dette gir en enorm fordel i å søke i forhold til å tråkke gjennom en ordnet liste over disse verdiene. Slette noder fra et binært tre er litt mer komplisert enn å legge til nye noder eller finne gamle. Avhengig av situasjonen, kan vi måtte omorganisere treet for å sikre at barn av hver node er fortsatt riktig balansert.

Bruksanvisning

Slette et blad Node

1 Kontroller at node har ingen barn.

2 Finn noden ordnede. Sett foreldrenes barnet referanse til null.

3 Fjern noden fra lagringsarray.

Slette en node med ett barn

4 Kontroller at node har bare ett barn.

5 Finn noden ordnede. Sett foreldrenes barnet henvisning til referanse barnet til noden du sletter.

6 Fjern noden fra lagringsarray.

Slette en node med to barn

7 Kontroller at node har to barn.

8 Finn den største node i treet til venstre for node (forgjengeren). Dette kan gjøres ved å tråkke igjen i treet ett trinn, og deretter tråkke rett til det ikke er mer riktige referanser.

9 Sett riktig referanse til forgjengeren til referanse høyre barn av noden du sletter.

10 Bytt foreldrenoden henvisning til forgjengeren.

11 Fjern noden fra lagringsarray.

Hint

• Flere slettinger kan føre til at treet til å bli ubalansert. Hvis du finner ut at programmet kjører sakte etter mange slettinger, bør du programmere den til å balansere treet på anledningen.