本次新建的节点
被复用(两个版本共享同一个节点)
只在旧版本里,新版本不再引用
get 经过的路径
虚线框 = 缓冲区;分支格子里的斜体数字 = 累计大小
规则速查
- 布局:元素按顺序依次在 front、树里的各个叶子、back 中。叶子 1..cap 个元素,分支 1..cap 个孩子,所有叶子同深度,分支记录累计大小 ends(relaxed B-tree)。不超过 cap 个元素的向量整个放在 back 里。
- push:缓冲区没满就只改缓冲区;满了整块变成叶子,用
Tree::concat并入树的那一侧。 - drop:缓冲区非空就只改缓冲区;为空就用
tree.split取出树那一端的叶子当缓冲区,再丢元素。 - get / assoc:先判断落在 front、树还是 back;在树里就用 ends 逐层找孩子。assoc 沿这条路径复制节点,其余子树复用。
- concat:一侧不超过 cap 个元素就逐个 push 进另一侧;否则左树 = a.tree + a.back,右树 = b.front + b.tree,再 join 两棵树:较高的树沿脊柱下降到同一高度,接缝处相邻节点放得下就合并(merge_seam),不到半满的叶子重新均分,孩子超过 cap 就从中间拆开(pack)。
- split:沿根到切点的路径把每层节点拆成左右两半,路径之外的子树整体复用;左边的 back、右边的 front 留空。
- insert / dissoc:在两端时直接 push / drop,否则是 split + concat 的组合,所以是 O(log n),不会像链式结构那样越插越深。
- 重建:split / concat 之后,树高超过 max_height(len)(假设节点只有四分之一满,再加一层余量)就把树里的元素重新切块建树。
- 本页的简化:缓冲区每次都整体复制。真实实现里缓冲区是共享块的切片
data[start..end],drop 只移动 start/end。