통계 트리 순서 지정
Order statistic tree컴퓨터 공학에서 순서 통계 트리는 이진 검색 트리(또는 더 일반적으로 B-트리[1])의 변형으로서 삽입, 조회 및 삭제를 넘어 다음의 두 가지 추가 작업을 지원한다.
- 선택(i) – 트리에 저장된 i번째 최소 요소 찾기
- 순위(x) – 트리에서 요소 x의 순위, 즉 트리의 요소 정렬 목록에서 요소 x의 색인 찾기
두 연산 모두 자체 균형화 트리를 기본 데이터 구조로 사용할 경우 O(log n) 최악의 경우 수행될 수 있다.
증강 검색 트리 구현
일반 검색 트리를 순서 통계 트리로 바꾸려면 트리의 노드가 해당 노드에 뿌리를 둔 하위 트리의 크기(즉, 그 아래의 노드 수)인 한 개의 추가 값을 저장해야 한다.트리를 수정하는 모든 작업은 다음 불변성을 보존하기 위해 이 정보를 조정해야 한다.
size[x] = size[왼쪽[x] + size[오른쪽] + 1
어디에size[nil] = 0정의상선택 후 다음[2]: 342 계정으로 구현 가능
함수 선택(t, i) // t ← 크기[왼쪽[t]+1] 원소의 i번째 원소(0인덱싱됨)를 반환한다. i = i = i = t를 반환하면 선택(왼쪽[t], i) 또는 선택(오른쪽[t], i - l)
랭크는 다음과[3]: 342 같이 구현될 수 있다.
함수 순위(T, x) // 트리 T r ← 크기[왼쪽[x] + 1 y ← x의 선형 정렬 목록에서 x (1-색인)의 위치를 반환하고, y = 오른쪽[p[y] r + 크기[p[y]] + 1 y ← p[y] 리턴 r의 위치를 반환한다.
주문 통계 트리는 균형을 유지하기 위해 부기 정보로 추가 수정될 수 있다(예: 주문 통계 AVL 트리를 얻기 위해 트리 높이를 추가하거나 빨간색-검은색 통계 트리를 얻기 위해 색상 비트를 추가할 수 있다).또는 크기 필드를 추가 저장 비용 없이 무게 균형 조정 방식과 함께 사용할 수 있다.[4]
참조
- ^ "Counted B-Trees". 11 December 2004. Retrieved 18 January 2014.
- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2001) [1990]. Introduction to Algorithms (2nd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03293-7.
- ^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald L.; Stein, Clifford (2009) [1990]. Introduction to Algorithms (3rd ed.). MIT Press and McGraw-Hill. ISBN 0-262-03384-4.
- ^ Roura, Salvador (2001). A new method for balancing binary search trees. ICALP. Lecture Notes in Computer Science. Vol. 2076. pp. 469–480. doi:10.1007/3-540-48224-5_39. ISBN 978-3-540-42287-7.
