Jeśli usuwany węzeł (mający zawsze co najwyżej jednego syna ) jest czarny, drzewo traci właściwości czerwono-czarne, które muszą zostać przywrócone:
jeśli y.color == BLACK wtedy delete-restore(x); remove(y);
Procedura delete-restore() przywraca własności czerwono-czarne przed wykonaniem fizycznego usunięcia, zaczynając od jedynego syna usuwanego węzła . Jeśli nie miał synów, jest wtedy czarnym wartownikiem. Mogą zajść trzy przypadki:
Jeśli był korzeniem, wtedy nowym korzeniem zostaje węzeł czerwony, co narusza własność 2. Jeśli oraz y.parent były czerwone, naruszamy własność 4, gdyż czerwony węzeł będzie mieć czerwonego syna. Usunięcie sprawia, że wszystkie przechodzące przez niego ścieżki będą mieć o jeden czarny węzeł mniej, co narusza własność 5. Po fizycznym usunięciu węzła można rozróżnić następujące przypadki: jeśli jest czerwony, wówczas nadajemy mu kolor czarny, jeśli jest już czarny, wówczas dokonujemy naprawy drzewa, rozważając przypadki zależne od koloru ojca, brata i jego obu synów. Podobne struktury Alternatywnym sposobem równoważenia BST jest użycie drzew AVL.