Binaire zoekboom: verschil tussen versies

Ter illustratie verwijderen we de knoop met waarde 7 uit de onderstaande boom. Als we deze vervangen door de knoop met waarde 6 dan krijgen we de linkersituatie waar de subboom die eerst onder 6 hing nu op de plaats van 6 staat. De knoop met waarde 7 is verwijderd en vervangen door de knoop met waarde 6. In de rechtersituatie is het vergelijkbaar maar dan is de knoop met waarde 7 vervangen door de eerste knoop met een hogere waarde (in dit geval de knoop met waarde 9):

 

 

Zodra we de knoop met een waarde net voor of net na knoop <math>N</math> hebben gevonden, wisselen we deze om met <math>N</math> en verwijderen we die knoop. Aangezien beide van die twee knopen minder dan twee kinderen hebben (anders kunnen ze niet een voorganger of opvolger van <math>N</math> zijn), kan die knoop verwijderd worden op een eerder genoemde manier. Een goede implementatie zorgt er ook voor dat niet telkens dezelfde knoop (bijvoorbeeld telkens de opvolger van <math>N</math>) wordt verwijderd want dit kan resulteren in een ongebalanceerde boom.