在不使用父指針的情況下在紅黑樹中查找排名

Question

我在課堂上獲得了紅黑樹的代碼。用於創建節點的結構沒有父指針。我的大部分項目都在工作，但我無法弄清楚如何計算O（lg n）時間的排名。通過排名，我的意思是如果你要做一個遍歷遍歷並將索引保​​存到索引1的數組中，那麼將存儲給定鍵的索引。這樣做會在O（n）時間，儘管這是不允許的。

通過CLRS閱讀，Augmenting Data Structures章節的代碼返回給定密鑰的等級。這正是我需要的，但問題是代碼使用父指針。由於我們從未在任何紅黑樹示例中使用父指針，並且此代碼不包含父指針，所以我不相信我們要改變整個給定代碼只是爲了讓等級起作用，這導致我相信有一種方法可以不使用父指針。 （字段？）存在於節點結構中的是：一個key（int），一個指向左側子元素的指針，右側子元素的指針，子樹大小（int）和color（int） 。

所有的代碼都在C中完成。我在尋找的是如果這是可能的，以及我如何在有或沒有源代碼的情況下完成這項工作（一個很好的解釋將是完美的）。

Answer 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樹的通常從左到右的由低到高的順序。