Store two values, the maximum and minimum. These need to be checked and potentially updated on every delete. If the minimum is being deleted, call the successor, update the minimum and delete the old item. Similarly, if the maximum is being deleted, call the predecessor, update the maximum and delete the old item. On insert, compare the new item to min/max, if it replaces either one update the min/max accordingly.