我在课堂上得到了一棵红黑树的代码。用于创建节点的结构没有父指针。我的大部分项目都在工作,但我无法弄清楚如何在 O(lg n) 时间内计算排名。通过排名,我的意思是如果您要进行中序遍历并将键保存到从索引 1 开始的数组中,那么给定键将存储的索引。这样做将在 O(n) 时间内完成,但这是不允许的。
通读 CLRS,扩充数据结构一章有代码返回给定键的排名。这正是我所需要的,但问题是代码使用了父指针。由于我们从未在任何红黑树示例中使用父指针,并且此代码不包含父指针,我不认为我们要更改整个给定代码只是为了使排名起作用,这导致我相信有一种方法可以在不使用父指针的情况下做到这一点。
节点结构中存在的(字段?)是:键(int)、指向左孩子的指针、指向右孩子的指针、子树大小(int)和颜色(int)。
所有代码都是用 C 语言完成的。我正在寻找的是这是否可能,以及我如何在有或没有源代码的情况下完成此任务(一个好的解释将是完美的)。