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