>>12
どうしてですか？
std::mapの1エントリが、一体どれだけのメモリ量なのか、計算してください
まず、保持すべき整数値IDとポインタで8バイト、
木なので最低でもrightとleftが有るので+8バイト
加えてエントリはnewで確保されるので、頭に管理領域が付く

一方、std::vectorなどで配列で管理する場合、
1エントリに付きポインタ1つの容量なので、4バイト

つまり、配列をかなり無駄遣いしたとしても、配列の方がメモリ量は少ない