Ну так как проблема как раз в этом дереве. На каждый удаленный блок пишется дополнительная структура. Блок взяли а что делать со структурой?

проблемы-то нет. Каждая структура (или класс, если на С++) листка этого бинарного дерева сидит в блоке со свободной памятью - вы же ее удалить не можете, так как после нее есть блок с занятой памятью. Очевидно, если блок был в конце файла, то лучше его просто удалить и из бинарного дерева и из файла. А вот головка, или корень этого бинарного дерева - это несколько десятков байт, и их можно в оперативке сохранить.

Самописный код бинарного дерева

380 725 7945 bintree.c
83 191 1942 bintree.h
463 916 9887 итого

меньше 500 строк сишника, в современном С++ есть соответствующий класс, и не надо велосипед выдумывать. Предполагаю, что в других языках и бинарное дерево, и двухсвязанные списки тоже в стандартных библиотеках имеются. Весь код такого аллокатора:

380 725 7945 bintree.c
83 191 1942 bintree.h
112 216 2158 decmem.c
463 969 11349 dmem.c
93 267 3159 dmem.h
336 592 5963 memc.c
62 170 1358 memc.h
292 1127 7883 memf.f
303 639 6732 quemem.c
2124 4896 48489 итого

у меня в свое время получился слегка больше двух тысяч строк и в 90-х я это примерно за месяц запрограммировал и радовался. Как я говорю, сейчас все это решается стандартными средствами С++, поэтому код дарить не буду, но рассказать-объяснить постараюсь. Если хотите, или так будет проще, могу войсом, тогда в личке телефонами обменяться надо будет.