Здравствуйте, watchmaker, Вы писали:

W>Если удаляться могут не только добавленные прямоугольники, и нужно определять такую ситуацию (например, сообщая об невозможности удаления), то можно несложно изменить структуру данных и для такого случая — в дереве сделать ключи уникальными, а в данных, связанных с ключом, хранить множество уникальных идентификаторов для добавленных прямоугольников. Тогда при вызове удаления можно будет определить, добавлялся ранее такой прямоугольник или нет.

Проще говоря, сделать (хеш)-таблицу с ключами — 4-элементными векторами.
Добавляем прямоугольник — добавляем в его таблицу (кстати, проверяем, не был ли он добавлен ранее; что делать с дубликатами?) и добавляем его габариты в мультимножества.
Удаляем — соответственно, проверяем наличие в таблице, удаляем оттуда, и вычёркиваем по одному вхождению из мультимножеств.


А если удаляться могут произвольные прямоугольники (вырезаться из существующего покрытия), то придётся сделать quad-tree.