데이터 구조는 숫자가

Question

나는 다음과 같은 쿼리에 응답 할 수있는 방식으로 번호를 유지하는 데이터 구조를 제안하십시오 유지 = O (로그 (N))

삽입 K보다 적은 숫자의 수 - O (N 로그())

그것은 숙제 아니지만 내가 더 큰 하나를 해결하기 위해 발생하고 작은 문제 - Number of students with better grades and lower jee rank을

비록 각 노드에서 서브 트리에 노드 수를 유지하면서 avl 트리를 가지고 있습니다. 그러나 삽입이 완료되고 재 밸런싱이 완료되면 각 노드에서이 수를 유지하는 방법을 모릅니다.

Answer 1

또한 AVL 트리를 사용해 보겠습니다. 훨씬 깊게 보지 않고서는 이것이 추가하기가 너무 어려울 것이라고 생각하지 않습니다. AVL 트리의 경우에는 항상 각 노드의 각 하위 트리의 깊이를 알 필요가 있습니다 (또는 적어도 균형 요소). 따라서 하위 트리의 크기를 전파하는 것이 너무 어렵지 않아야합니다. 회전의 경우, 각 노드와 각 하위 트리가 어디에 상주하는지 정확하게 알 수 있으므로 회전 된 노드에 대한 단순한 다시 계산이어야합니다.

Answer 2

이진 트리에서 찾는 것은 O (log (n))입니다. 이 노드의 서브 트리의 크기를 저장하는 경우 :

• 를 사용하면 노드의 카운터를 증가 하위 트리에서 성공적인 삽입에서 돌아 오는 수있다;
• 을 삭제하는 중입니다.

그래서 하위 트리 크기는 찾기와 같습니다. O (log (n)).

Answer 3

힙 데이터 구조의 다양한 변형을 살펴보십시오. here.