De la même façon qu'avec des ABR, on supprime un noeud en le remplaçant par le noeud du plus grande clé du sous-arbre gauche, ou celui de plus petite clé du sous-arbre droit. La suppression du minimum ou du maximum a les mêmes conséquences que pour l'insertion, il est nécessaire de contrôler l'équilibre de chaque noeud sur le chemin menant du père de la feuille supprimée à la racine.