및 증가를 AVL 트리, 순서

Question

:

Design a data structure for maintaining dynamic sequence x_1, x_2,... , x_n 
which provides operations: 
Insert(a,i) - inserts a as x_i, indexes from i+1 to n go up by 1 
Delete(i) - deletes x_i, indexes from i+1 to n go down by 1 
Find(i) - returns element x_i 
Sum_even() - returns sum of the elements with even indexes 

순서가 동적 그래서 그것을 유지하기 위해 AVL 트리를 사용하고 싶습니다. 그래서 발견, 삭제 및 삽입을 위해 표준 트릭을 사용할 수 있다고 생각합니다.이 노드에 뿌리를 둔 하위 트리의 각 노드 크기 만 유지하면됩니다. 그러면 O (log n) 시간에 i 번째 요소를 찾기 위해 트리를 쉽게 탐색 할 수 있습니다. 그러면 Inorder가 x_1, x_2, ..., x_n을 제공합니다.

그러나 Sum_even()에 대해 각 노드의 짝수 및 홀수 인덱스가있는 요소의 합계도 있어야합니다. 삽입 또는 삭제 중에는 업데이트하기가 어렵습니다. 어떻게 작동해야합니까? 아무도 도와 줄 수 있습니까?

Answer 1

노드에 하위 트리의 크기를 저장할 필요가 없습니다. AVL 트리는 왼쪽과 오른쪽 서브 트리의 높이 차이를 -1, 0 또는 +1 만 저장합니다.

sum_even을 쉽게 유지하려면 각 노드마다 sum_even 및 sum_odd을 저장해야합니다. 하위 트리에 대한 짝수/홀수 인덱스의 값 합계입니다.

각각의 노드가있을 것이다 변수 :

• difference
• value
• parity 패리티 서브 트리의 크기의 좌측 및 우측 서브 트리의 높이 차이 (0 또는 1)
• sum_even
• sum_odd

삽입 및 삭제의 경우 표준 알고리즘 http://en.wikipedia.org/wiki/AVL_tree을 사용하십시오. 그러나 영향을받는 각 노드 (길의 노드 루트까지와 회전 노드) 업데이트 값 :

나는 나무와 같이 일을했던

parity := (left.parity + right.parity + 1) % 2 
if left.parity == 0 
    sum_even := left.sum_even + right.sum_odd 
    sum_odd := left.sum_odd + right.sum_even + value 
else 
    sum_even := left.sum_even + right.sum_even + value 
    sum_odd := left.sum_odd + right.sum_odd