Вставка в двоичное сбалансированное дерево — довольно дешевая операция. Расход времени на добавление нового узла в это дерево состоит из двух частей: поиск места для вставки нового узла и балансировка дерева после вставки. Поиск места по расходу времени примерно аналогичен методу половинных делений, а балансировка дерева состоит в переназначении некоторых указателей в дереве. Дешево и сердито.
Аналогично и с удалением: расходы на удаление состоят из поиска удаляемого элемента, operator delete и балансировка дерева после удаления.
Вообще по сбалансированным деревьям можно почитать уйму материалов в интернете начиная со статей на Хабре и заканчивая Википедией. А в гугле можно найти и реализацию этих деревьев.
Вставка в двоичное сбалансированное дерево — довольно дешевая операция. Расход времени на добавление нового узла в это дерево состоит из двух частей: поиск места для вставки нового узла и балансировка дерева после вставки. Поиск места по расходу времени примерно аналогичен методу половинных делений, а балансировка дерева состоит в переназначении некоторых указателей в дереве. Дешево и сердито.
Аналогично и с удалением: расходы на удаление состоят из поиска удаляемого элемента, operator delete и балансировка дерева после удаления.
Вообще по сбалансированным деревьям можно почитать уйму материалов в интернете начиная со статей на Хабре и заканчивая Википедией. А в гугле можно найти и реализацию этих деревьев.