• 
  

  Ta bort en nod binära sökträd

  
  

Binära sökträd används för att organisera sekventiella data för enkel hämtning . Varje nod i ett binärt sökträd har mellan noll och två barn . Den vänstra barnet till en nod är alltid mindre än noden och rätt barnet är alltid större . Så när vi söker efter en specifik nod , kan vi jämföra vårt mål att den aktuella noden. Om vårt mål är större än den aktuella noden vi fortsätta söka ner rätt gren , om vårt mål är mindre än den aktuella noden söker vi ner den vänstra grenen . Detta ger en enorm fördel i att söka jämfört med stegar genom en ordnad lista av dessa värden . Ta bort noder från ett binärt träd är något mer komplicerat än att lägga till nya noder eller hitta gamla . Beroende på situationen , kan vi ordna trädet för att säkerställa att barn till varje nod är fortfarande väl avvägda

. Ta bort en löv


1 .
Kontrollera att noden har inga barn .
2 .
Hitta nodens förälder . Ställ förälderns barn hänvisning till null .
3 .
Ta bort noden från din lagringsmatrisen.


bort en nod med ett barn


1 .
Kontrollera att noden har bara ett barn .
2 .
Hitta nodens förälder . Ställ förälderns barn hänvisning till referens barn till noden du tar bort .
3 .
Ta bort noden från din lagringsmatrisen.


bort en nod med två barn


1 .
Kontrollera att noden har två barn.
2 .
Hitta den största nod i trädet till vänster om noden ( föregångaren ) . Detta kan göras genom ökade kvar i trädet ett steg , och sedan med höger fot tills det inte mer rätt referenser .
3 .
Ställ rätt referens föregångaren till referens höger barn till nod du tar bort.
4 .
tillbaka förälder nod hänvisning till föregångaren .
5 .
Ta bort noden från din lagringsmatrisen.


tips och varningar




Flera strykningar kan orsaka ditt träd att bli obalanserat . Om du tycker att ditt program går långsamt efter många strykningar , bör du programmera den att balansera trädet ibland .

Previous：nothing Next：hur man använder en SQL-fråga för att få tillgång till egenskaper databasfält

Relaterade artiklar