如何根据排名实现 BST 函数 insert() 和 split()？

Question

我想弄清楚如何实现 insert()（将一个元素插入树中）、split()（将等级为 r 的树分成 L 和 R 两棵树）的代码. L 包含等级 < r 和 R 包含等级 >= r。对于这个作业，我傻眼了。我相信我的插入代码正确有效：

Node *insert(Node *T, int v, int r)
{
    if(T == nullptr)
    {
        return new Node(v);
    }
    int rank = T->left ? T->left->size : 0;
    
    if (r <= rank)
    {
        T -> left = insert(T -> left, v, rank);
    }
    else
    {
        T -> left = insert(T -> left, v, r - rank - 1);
    }
    fix_size(T);
    return T;
}

对于我的 split() 函数，我几乎没有任何可用的东西。有人可以解释一下如何完成这两个功能的算法吗？谢谢！

Answer 1

我假设我们在这里处理不平衡的 BST（平衡使这更难）。

拆分空树很简单 (return (null, null))。

给定一棵 non-null 树 T，将根的等级与 r 进行比较。如果小于，则递归拆分右child得到(R<,R≥)和return(T′,R≥) 其中T′为T与右child的根替换为 R<。相似性，如果根的秩大于等于r，则递归拆分左边child为(L<, L≥)和return(L<, T′′) 其中T ′′是T，根的左边child替换为L≥.

这有一个巧妙的迭代实现，带有 Node** 个指针，我将把它留作练习。

如何根据排名实现 BST 函数 insert() 和 split()？

How to implement BST functions insert() and split() based upon rank?

c++

c

algorithm

binary-search-tree