• 欢迎访问最初的梦想
  • Github https://github.com/anthonyzhai

增强数据结构

编程 AnthonyZhai 2个月前 (08-13) 72次浏览 已收录 0个评论

常见数据结构,STL库已经足够使用。

1 动态次序统计量

k阶次序统计量:n个元素第k小的元素。
动态集合包括:
+ k阶次序统计量
+ 元素排第几
需要使用红黑树,每个结点新增属性size:p->size表示以p为根结点的子树结点数量。
增强数据结构

其中,
1)leaf->size=0
2)非leaf的p->size=p->left->size+p->right->size+1

1.1 寻找第k个元素

从根开始,根据当前结点在子树中的排名决定向左子树继续查找,还是右子树。
结点p的排名r=p->left->size+1;

RBNode* findKthElement(RBNode *p, size_t k){
    RBNode *p = root;
    size_t r = p->left->size + 1;
    while(k != r){
        if(k < r)
            p = p->left;
        else{
            p = p>right;
            k -= r;
        }
        r = p->left->size + 1;
    }
    return p;
}

运行时间$O(logn)$。

1.2 元素排第几

从当前结点开始,计算其在子树中的排名r,然后向上直到根为止。计算过程中,如果该结点是其父亲的右孩子,则需要修改排名;若果是左孩子,则不影响。

size_t calcElementRank(RBNode *root, RBNode* p){
    size_t r = p->left->size + 1;
    while(p != root){
        if(p->parent->right == p)
            r += p->parent->left->size + 1;
        p = p->parent;
    }
    return r;
}

运行时间$O(logn)$。

1.3 循环不变式

以p为根的子树,其中x在p中的排名是r。
初始化:显然,x当前是根p,r = p->left->size + 1;即便x的左孩子是叶子结点,r = 0 + 1也成立;
维护:若p是其父亲的左孩子,则x在p的父亲中的排名=x的p中的排名;若p是其父亲的右孩子,则x在p的父亲中的排名=p在其父亲中的排名+x在p中的排名;
终止:p为根结点,r是排名。

1.4 维护子树size属性

插入和删除的运行时间依然是$O(logn)$。

1.4.1 插入

增强数据结构

1.4.2 删除

从删除点向上所有结点的size-1,旋转调整和插入类似


最初的梦想 , 版权所有丨如未注明 , 均为原创丨本网站采用BY-NC-SA协议进行授权
转载请注明原文链接:增强数据结构
喜欢 (0)
发表我的评论
取消评论

表情 贴图 加粗 删除线 居中 斜体 签到

Hi,您需要填写昵称和邮箱!

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址