부모 포인터를 사용하지 않고 빨강 - 검정 트리에서 순위 찾기

Question

클래스에 빨간색 검정색 코드가 지정되었습니다. 노드를 만드는 데 사용 된 구조체에는 부모 포인터가 없습니다. 나는 대부분의 프로젝트를 작업하고 있지만 O (lg n) 시간에 계급을 계산하는 방법을 알 수는 없습니다. 순위에 따라, 당신이 inorder-traversal을 수행하고 인덱스 1에서 시작하는 배열에 키를 저장한다면, 주어진 키가 저장 될 인덱스를 지정해야합니다. 이 작업은 허용되지 않지만 O (n) 시간에 수행됩니다.

CLRS를 통해 읽는 데이터 구조 확장 장에는 키가 주어진 순위를 반환하는 코드가 있습니다. 이것은 내가 원하는 것이지만, 문제는 코드가 부모 포인터를 사용한다는 것입니다. 우리는 적색 - 검정 트리 예제에서 부모 포인터를 사용하지 않았고이 코드에는 부모 포인터가 포함되어 있지 않기 때문에 순위 코드를 얻기 위해 전체 코드를 변경해야한다고 생각하지 않습니다. 부모 포인터를 사용하지 않고 그것을 할 수있는 방법이 있다고 생각합니다.

노드 구조체에있는 (필드?)는 키 (int), 왼쪽 자식에 대한 포인터, 오른쪽 자식에 대한 포인터, 하위 트리 크기 (int) 및 색상 (int) .

모든 코드가 C로 이루어집니다. 가능한 경우이 코드를 사용하여 소스 코드를 사용하거나 사용하지 않고 구현할 수 있습니다 (좋은 설명은 완벽 할 것입니다).

Answer 1

가정 : 서브 트리 크기는 서브 트리의 루트 노드를 포함한다. a에서 순서화 할 값을 호출하십시오.

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)) 

완료 :

그런 다음,이 알고리즘은 당신에게 O (LGN)에서 순위를 가져옵니다.

참고 : 일반적으로 왼쪽에서 오른쪽으로 낮은 rb 트리의 순서가 있다고 가정합니다.