You need to enable JavaScript to run this app. 如何基于秩实现BST的insert()与split()函数
优惠活动
大模型
产品
解决方案
定价
更多

如何基于秩实现BST的insert()与split()函数

基于秩的顺序统计二叉搜索树实现思路

现有insert代码的核心问题排查

你写的insert代码存在两处硬逻辑错误,完全无法达到预期效果:

  • 左子树插入分支的传参错误:当判定待插入位置在当前节点左子树范围内时,递归传入的秩参数错写为左子树的大小rank,没有保留原始待插入秩r,会导致插入位置偏移。
  • 右子树插入分支的操作对象错误:当判定待插入位置在当前节点右子树范围内时,代码仍然操作当前节点的左指针、递归插入左子树,完全缺失右子树的插入逻辑。

正确的insert函数实现逻辑

实现前提:每个Node节点自带size属性,代表以该节点为根的子树的总节点数;fix_size()函数负责在子树结构变动后,重新计算当前节点的size值(计算规则为:当前节点size = 左子树size + 右子树size + 1);秩计数从0开始,整棵树的第0个节点是中序遍历的第一个节点。

正确的递归insert流程:

  1. 递归终止:如果当前节点T是空指针,直接返回新建的节点(新节点初始size为1)。
  2. 计算当前节点的左子树总节点数:int left_size = T->left ? T->left->size : 0,这个值就是当前节点在以T为根的树中的秩(即当前节点前面有多少个节点)。
  3. 分支递归:
    • 若待插入秩r <= left_size:新节点属于左子树范围,将左子树递归插入返回的新指针赋值给T->left,递归传入的秩就是原始值r(左子树内部的秩和整棵树左半段的秩完全对齐,无需偏移)。
    • 若待插入秩r > left_size:新节点属于右子树范围,将右子树递归插入返回的新指针赋值给T->right,递归传入的秩为r - left_size -1(需要扣掉左子树的总节点数、再扣掉当前节点自身占的1个位置,对齐右子树内部的从0开始的秩计数)。
  4. 子树插入完成后调用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的分支判断完全对齐,全程只需要沿树的单条路径递归,不会重复遍历节点:

  1. 递归终止:如果当前节点T是空,直接返回空的L和R即可。
  2. 计算当前节点的左子树总节点数left_size,也就是当前节点在T为根的树中的秩。
  3. 分支判断:
    • 若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

相关产品推荐
方舟 Agent Plan

超全模态模型 × Harness 升级,最新支持 Deepseek-V4.1-Flash、GLM-5.3 系列、Doubao-Seedream-5.0-pro、Kimi-K3 (部分), 限时 9.9 元起

最近更新时间:2026.11.18 17:36:05