如何基于秩实现BST的insert()与split()函数
基于秩的顺序统计二叉搜索树实现思路
现有insert代码的核心问题排查
你写的insert代码存在两处硬逻辑错误,完全无法达到预期效果:
- 左子树插入分支的传参错误:当判定待插入位置在当前节点左子树范围内时,递归传入的秩参数错写为左子树的大小
rank,没有保留原始待插入秩r,会导致插入位置偏移。 - 右子树插入分支的操作对象错误:当判定待插入位置在当前节点右子树范围内时,代码仍然操作当前节点的左指针、递归插入左子树,完全缺失右子树的插入逻辑。
正确的insert函数实现逻辑
实现前提:每个Node节点自带size属性,代表以该节点为根的子树的总节点数;fix_size()函数负责在子树结构变动后,重新计算当前节点的size值(计算规则为:当前节点size = 左子树size + 右子树size + 1);秩计数从0开始,整棵树的第0个节点是中序遍历的第一个节点。
正确的递归insert流程:
- 递归终止:如果当前节点
T是空指针,直接返回新建的节点(新节点初始size为1)。 - 计算当前节点的左子树总节点数:
int left_size = T->left ? T->left->size : 0,这个值就是当前节点在以T为根的树中的秩(即当前节点前面有多少个节点)。 - 分支递归:
- 若待插入秩
r <= left_size:新节点属于左子树范围,将左子树递归插入返回的新指针赋值给T->left,递归传入的秩就是原始值r(左子树内部的秩和整棵树左半段的秩完全对齐,无需偏移)。 - 若待插入秩
r > left_size:新节点属于右子树范围,将右子树递归插入返回的新指针赋值给T->right,递归传入的秩为r - left_size -1(需要扣掉左子树的总节点数、再扣掉当前节点自身占的1个位置,对齐右子树内部的从0开始的秩计数)。
- 若待插入秩
- 子树插入完成后调用
fix_size(T)更新当前节点的size,最后返回T。
修正后的参考代码:
Node *insert(Node *T, int v, int r) { if(T == nullptr) { Node *new_node = new Node(v); new_node->size = 1; // 叶子节点size初始为1 return new_node; } int left_size = T->left ? T->left->size : 0; if (r <= left_size) { // 插入到左子树,秩无偏移 T->left = insert(T->left, v, r); } else { // 插入到右子树,秩需要偏移 T->right = insert(T->right, v, r - left_size - 1); } fix_size(T); return T; }
split函数的实现思路
split函数的功能是:输入原树T、拆分秩r,返回两棵树L和R,其中L包含T中所有秩小于r的节点,R包含T中所有秩大于等于r的节点,拆分后所有节点的size属性保持正确。
核心递归逻辑和insert的分支判断完全对齐,全程只需要沿树的单条路径递归,不会重复遍历节点:
- 递归终止:如果当前节点
T是空,直接返回空的L和R即可。 - 计算当前节点的左子树总节点数
left_size,也就是当前节点在T为根的树中的秩。 - 分支判断:
- 若
left_size < r:说明当前节点本身、当前节点的整棵左子树的所有节点秩都小于r,全部属于L树。此时只需要对当前节点的右子树做拆分,拆分的秩参数为r - left_size -1(对齐右子树内部的秩计数)。拆分右子树会得到两个结果(right_L, right_R):把当前节点的右指针接到right_L上,重新调用fix_size(T)更新当前节点的size,此时以T为根的整棵子树就是最终L树,本次递归的返回结果就是(L = T, R = right_R)。 - 若
left_size >= r:说明当前节点本身、当前节点的整棵右子树的所有节点秩都大于等于r,全部属于R树。此时只需要对当前节点的左子树做拆分,拆分的秩参数为r(左子树内部的秩和整棵树左半段的秩完全对齐,无需偏移)。拆分左子树会得到两个结果(left_L, left_R):把当前节点的左指针接到left_R上,重新调用fix_size(T)更新当前节点的size,此时以T为根的整棵子树就是最终R树,本次递归的返回结果就是(L = left_L, R = T)。
- 若
参考函数签名(C++形式):
// 返回值为pair<左树L, 右树R> pair<Node*, Node*> split(Node *T, int r) { if (T == nullptr) return {nullptr, nullptr}; int left_size = T->left ? T->left->size : 0; if (left_size < r) { auto [right_L, right_R] = split(T->right, r - left_size - 1); T->right = right_L; fix_size(T); return {T, right_R}; } else { auto [left_L, left_R] = split(T->left, r); T->left = left_R; fix_size(T); return {left_L, T}; } }
内容的提问来源于stack exchange,提问作者Zoie
相关产品推荐
相关产品推荐

