基于二叉搜索树的高效Malloc实现

我们设计了一个malloc函数，通过维护一个二叉搜索树来管理不同大小的空闲块。每个空闲块本身作为树节点，且每个节点还是一个双向链表的头节点，链表中所有节点大小相同。每个节点拥有left-child、right-child、parent和兄弟四个属性，这些属性使用空闲块中的一个字长空间来存储。

在链表中作为树节点时，我们将left-child用作链表中前一个空闲块的地址，兄弟保存链表中下一个空闲块的地址，同时将右孩子设置为-1，以区分无右孩子的节点（此时右孩子为0）。

此外，空闲块的最小大小为24字节，由4字节的头部和4字节的尾部包裹。当请求的分配大小不超过512时，分配大小为(2^n)+8的空间，例如，申请10个字节将分配一个大小为(2^n)+4+4的块。