基于红黑树与双向链表的内存管理：如何实现O(1)内存合并？

一、双向链表实现O(1)内存合并的核心逻辑 #

双向链表按内存块起始地址严格排序，每个空闲块节点维护prev（指向地址更小的前序空闲块）、next（指向地址更大的后序空闲块）、size三个核心字段。合并操作的O(1)特性来自无需遍历链表：

• 释放某块内存时，直接通过当前节点的prev和next指针定位前后相邻的空闲块
• 仅需两次地址校验：
  • 前序块的起始地址 + size 是否等于当前块的起始地址（判断前块与当前块是否连续）
  • 当前块的起始地址 + size 是否等于后序块的起始地址（判断当前块与后块是否连续）
• 只要满足任一条件，直接修改双向链表的指针完成合并：比如合并当前块与后块时，将当前块的size累加后块的size，再把当前块的next指向后块的next，同时更新后块next的prev指向当前块。全程仅指针操作，无遍历，时间复杂度为O(1)。

二、红黑树解决双向链表插入/删除的O(N)瓶颈 #

纯双向链表的问题在于释放内存时，需遍历找到对应插入位置，导致O(N)的时间开销。红黑树的作用是快速定位插入/删除的目标位置：

• 红黑树以内存块的起始地址为键，每个树节点与双向链表的对应空闲块节点关联
• 释放内存（插入空闲块）时：
  1. 通过红黑树查找，快速定位当前块的前驱（地址最大且小于当前块的空闲块）和后继（地址最小且大于当前块的空闲块），查找操作时间复杂度为O(logn)
  2. 将当前块直接插入双向链表的前驱与后继之间，此步骤为O(1)
  3. 将当前块节点插入红黑树，操作时间复杂度O(logn)
• 分配内存（删除空闲块）时：
  1. 若按首次适配/最佳适配策略，红黑树可按内存块大小构建索引（或维护一棵按size排序的红黑树），快速定位符合需求的空闲块，时间复杂度O(logn)
  2. 从红黑树和双向链表中删除目标块节点，操作时间复杂度O(logn)；若分配后剩余部分仍为有效空闲块，将剩余块插入红黑树和双向链表，同样为O(logn)

三、完整协同流程示例（以释放内存为例） #

1. 用户调用free(ptr)，计算出该内存块的起始地址与size
2. 通过红黑树查找，定位到地址小于当前块的前驱空闲块，以及地址大于ptr+size的后继空闲块
3. 将当前块插入双向链表的前驱与后继节点之间
4. 校验前驱块的末尾地址是否等于当前块起始地址：若是，合并前驱块与当前块，修改双向链表指针，并从红黑树中删除前驱节点
5. 校验当前块的末尾地址是否等于后继块起始地址：若是，合并当前块与后继块，修改双向链表指针，并从红黑树中删除后继节点
6. 将合并后的新空闲块（或原块，若未合并）插入红黑树

整个流程中，红黑树操作均为O(logn)，合并操作为O(1)，最终释放内存的时间复杂度为O(logn)，分配内存的逻辑同理。

内容的提问来源于stack exchange，提问作者Sandman