BST가 지원하는 정렬 된 집합의 요소를 O(logN)에 있습니다. 이제이 요소의 색인을 원합니다. 예를 들어 {1, 3, 4, 10} 세트에서 4의 인덱스는 2이고 1의 인덱스는 0입니다.정렬 된 집합의 요소 색인을 찾는 방법은 무엇입니까?
분명히, 나는 세트를 반복 할 수 있으므로, 사소한 해결책은 O(N)입니다. 아마도 BST 속성 및/또는 보조 데이터 구조를 사용하여 더 잘 수행 할 수 있습니까?
요소를 임의로 삽입하는 순서가 간단한 BST를 사용하면 트리를 걷지 않고도 주어진 요소보다 정확히 작은 요소 수를 결정할 수 있습니다.
빨강 - 검정 나무와 같은 균형 잡힌 나무가있는 경우 나무 높이의 경계로 인해 색인에 상한값과 하한값을 둘 수 있습니다. BST에 요소를 삽입하는 순서가 다시 무작위이면 나무 높이를 걷지 않고 무언가를 말하고 대략적인 색인을 추정 할 수 있습니다.
보조 데이터 구조의 경우 요소를 해당 색인에 매핑하는 보조 사전을 만들 수 있습니다. 그러나 BST에 새 요소를 추가 할 때 해당 인덱스를 작성하는 데 O (N)이 걸리고 인덱스가 부실해지기 때문에 업데이트가 자주없는 BST에만 적합합니다.
다른 해결책은 인덱스와 카운트라는 두 가지 속성으로 BST 노드를 확장하는 것입니다. 인덱스는이 노드에있는 요소보다 작은 요소가 트리에 얼마나 많은지를 나타냅니다. 수는 노드 색인을 마지막으로 갱신 할 때 BST에 몇 개의 요소가 있었는지를 표시합니다. BST에서 삽입, 삭제 및 검색을 비교적 간단하게 변경하면 일정 시간 이상 기본 작업에 영향을 미치지 않고 O (1)에서 요소의 색인을 직접 가져올 수 있습니다.
기본적으로 새 노드를 삽입 할 때 경로에서 아래로 전달하는 모든 노드에 대해 새 요소가 더 작 으면 (즉, 다음 단계가 왼쪽 자식에 대한 경우) 해당 노드의 색인과 개수를 모두 늘립니다. 새로운 요소의 위치를 찾으면 부모에 기반한 개수와 그 부모와 왼쪽 자식을 기반으로 한 인덱스를 부여합니다. 이렇게하면 잘못된 색인이있는 새 요소보다 큰 요소가 남지만 부모의 계수 값을 참조하여 요소를 검색 할 때 해당 요소를 쉽게 업데이트 할 수 있습니다. 부모와 자식의 개수의 차이는 마지막으로 하위 색인을 업데이트 한 이후에 더 작은 요소를 얼마나 많이 삽입했는지 파악하여 해당 차이를 색인에 추가하기 만하면됩니다.