Stergerea în arbori binari ordonati

În cazul stergerii unui nod, se disting trei situatii:

1. daca cheia x nu se gaseste în arbore, atunci nu se modifica arborele;
2. daca nodul cu cheia x are cel mult un descendent, atunci nodul cu cheia x se sterge, locul sau fiind luat de unicul sau descendent;
3. daca nodul cu cheia x are doi descendenti, atunci nodul cu cheia x se sterge, fiind înlocuit de nodul cu cheia cea mai mare din subarborele stâng (cel mai din dreapta nod al subarborelui stâng) sau înlocuit de nodul cu cheia cea mai mica din subarborele drept (cel mai din stânga nod al subarborelui drept).