O (logn)의 rbtree에서 알고리즘을 찾으십시오.

Question

다음 작업으로 수행 할 수있는 데이터 구조를 찾아야합니다.

• 빌드 (s, k) -O (nlogn)
• 검색 (S, K) -O (logn)
• 삽입 (S, K) -O (logn)
• 삭제 (s, k) -O (logn)
• 감소 (s, k, d) -o (logn) -이 방법은 <= k 인 모든 노드 D (d> 0)를 빼야합니다.

명백한 첫 번째 선택은 Redblacktree였습니다.

그러나 O (LOGN)의 감소에 관한 솔루션을 찾을 수 없습니다. K가 트리의 최대 키보다 더 크면 어떻게 되는가 - 그 경우는 전체 트리를 업데이트해야합니다.

누군가가 다른 것을 제안 할 수 있습니까? 어쩌면 몇 가지 팁?

Answer 1

트리의 각 노드에 추가 값을 저장할 수 있습니다. 델타라고합시다. 실제 키를 얻기 위해 모든 후손에 저장된 키에 노드의 델타를 추가합니다. 따라서 특정 노드에서 키의 실제 값을 얻으려면 모든 델타를 루트에서 해당 노드로 합류 하고이 합계를 저장된 키에 추가합니다.

할 것 Decrease-Upto, 당신은 루트에서 한 경로에서 o (log n) 노드의 델타를 변경합니다.

이 작업 후 트리 구조를 변경할 필요는 없습니다. 키의 순서를 변경하지 않기 때문입니다.