증강 트리

O(logN)

O(N)

 

알파벳 순서상 5번째 사람은?

i = 5( 찾고싶은 것)

k = 2 (왼쪽 트리의 갯수 + 1)

 

왼쪽으로 이동할 때는 i 변동 없으나, 오른쪽으로 이동하면 i = i-k; 임

i == k 일 때 찾고자 하는 값이 위치함.

 

동적 통계 트리임. 

실제 코드를 짤 수 있는 정도 avl tree 까지 봐야 하는지.?

my_select(x, i =5)
{
	int k;
	k = size[left[x]]+1;
    if(i==k)
    	return x;
    if(i<k)
    	my_selec(left[x], i);
    else
    	my_select(right[x], i-k)l

	return;
}

 

propagate 를 해야함. 

이것을 관리하는 방법이 중요하네.

 

agmented value가 들어가야 함.