0

我在课堂上得到了一棵红黑树的代码。用于创建节点的结构没有父指针。我的大部分项目都在工作,但我无法弄清楚如何在 O(lg n) 时间内计算排名。通过排名,我的意思是如果您要进行中序遍历并将键保存到从索引 1 开始的数组中,那么给定键将存储的索引。这样做将在 O(n) 时间内完成,但这是不允许的。

通读 CLRS,扩充数据结构一章有代码返回给定键的排名。这正是我所需要的,但问题是代码使用了父指针。由于我们从未在任何红黑树示例中使用父指针,并且此代码不包含父指针,我不认为我们要更改整个给定代码只是为了使排名起作用,这导致我相信有一种方法可以在不使用父指针的情况下做到这一点。

节点结构中存在的(字段?)是:键(int)、指向左孩子的指针、指向右孩子的指针、子树大小(int)和颜色(int)。

所有代码都是用 C 语言完成的。我正在寻找的是这是否可能,以及我如何在有或没有源代码的情况下完成此任务(一个好的解释将是完美的)。

4

1 回答 1

1

假设:子树大小包括子树的根节点。调用要在 a 中排序的值。

然后,这个算法让你​​在 O(lgn) 中获得排名:

1: let rank=subtree size(root of tree)
2: if you go left:
- adjust rank=rank - (subtree size(sts) of right child (rc) of root) - 1
- move to left child(lc) of root
3: if you go right:
- adjust rank=rank(prior)
- move to rc(root)
4: iterate 2-3 (replacing root with current node) until you are at the node with value a
5: if this node has a rc, adjust a final time
- rank = rank - (sts(rc))

完毕。

注意:假设 rb 树的通常从左到右从低到高排序。

于 2011-12-01T02:12:39.060 回答