题外话：为什么叫“伙伴”？因为每块只能和特定的另一块合并。

参考了wiki上伙伴系统实现的链接，在此做一简单总结

这里采用二叉树管理内存单元，分配和释放的搜索时间复杂度O(logN)，在这一点上优于最先匹配、最佳匹配和最差匹配。

 

每个节点标记对应的可用内存块大小

分配：

1. 传入size，将size调整到2的幂大小，检查是否超过根节点的标记。
2. 深度优先搜索，找到恰为size大小的空闲内存块（标记等于size且该层每个节点对应内存块大小为size），修改标记为0。根据size和该节点对应二叉树中的序号以及总大小，可以计算出内存块索引offset。
3. 之后回溯，更新祖先节点的标记，取左右子树较大值，完成分割。

 

释放：

传入offset。从最底层节点向上回溯，遇到标记为0的节点即对应当初分配的内存块，恢复标记为块大小，继续回溯，如果左右子树标记相加等于父节点对应的块大小，则恢复父节点标记为块大小。