데이터 구조에 대한 강의를 진행하고 있으며 다음 주 초에 스플레이 트리를 다룰 예정입니다. 스플레이 트리에 관한 논문을 여러 번 읽었으며 데이터 구조의 분석과 직관에 익숙합니다. 그러나 Sleator와 Tarjan이 분석에 사용하는 잠재적 기능에 대한 확실한 직감을 찾을 수 없습니다.

분석은 트리 내의 임의의 중량을 각각의 소자에 할당함으로써 동작 $w_{i}$

후, 크기 설정, $s (x)$

s(x)

를 루트로하는 서브 트리의 노드의 가중치의 합이 될 수있는 노드의 $x$

. 그런 다음이 값의 로그를 취하여 노드 의 순위 을 얻으 $r (x)$

r(x)

므로 $r (x) = \log s (x)$

r(x)=log⁡s(x)

입니다. 마지막으로, 트리의 잠재적 기능은 모든 노드의 순위의 합으로 정의됩니다.

이 잠재적 기능이 올바르게 작동하고 분석을 따를 수 있음을 이해하지만 왜 그들이이 잠재력을 선택하는지 알 수 없습니다. 각 노드에 크기를 할당한다는 아이디어는 나에게 의미가 있습니다. 크기를 합하면 트리의 가중 경로 길이를 얻을 수 있기 때문입니다. 그러나 왜 그들이 무게의 로그를 가져 와서 대신 요약하기로 결정했는지 알 수 없습니다.이 나무에 해당하는 자연 속성이 보이지 않습니다.

스플레이 트리의 잠재적 기능이 트리의 일부 자연 속성에 해당합니까? 그들이“잠재적”이라는 것 외에 그들이이 잠재력을 선택해야하는 특별한 이유가 있습니까? ( 이 강의 노트 세트에 “분석은 흑 마법”이라고 언급 되어 있기 때문에 특히 궁금 합니다.

감사!

답변

로그 합계 가능성을내는 방법

요소 대한 각 액세스에 대해 사전 경로라고 하는 의 검색 경로 에있는 요소 만 사후 트리라고하는 일부 트리로 재배 열하 는 BST 알고리즘 를 고려해 봅시다 . 어떤 요소를 위해 ,하자 및 를 루트로하는 서브 트리의 크기 전에 각각 재 배열 후. 따라서 및 IFF에 따라 다를 수도 . $A$

$x$

$P$

$x$

$a$

$s (a)$

s(a)

$s^{'} (a)$

s′(a)

$a$

$s (a)$

s(a)

$s^{'} (a)$

s′(a)

$a \in P$

a∈P

또한 는 언제든지 검색 경로에서 많은 요소를 끊임없이 재정렬합니다. 이 유형의 알고리즘을 “로컬”알고리즘이라고합니다. 예를 들어, 재생 트리는 로컬입니다. 지그재그, 지그재그로 한 번에 최대 3 개의 요소 만 재 배열합니다. $A$

이제 트리 뒤에 애프터 트리에 “많은”잎을 만드는 로컬 알고리즘에는 다음과 같은 멋진 속성이 있습니다.

매핑을 만들 수 있습니다 그러한를 $f : P \to P$
f:P→P

많은 선형있다 , 여기서 . $a \in P$ $s^{'} (f (a)) \leq s (a) / 2$

지속적으로 많은있다 여기서 $a \in P$ 크지 만 하찮게 대부분에있을 수 . $s^{'} (f (a))$ $n$

다른 요소 , $a \in P$ . $s^{'} (f (a)) \leq s (a)$

검색 경로 변경을 펼쳐서이를 확인할 수 있습니다. 매핑은 실제로 매우 자연 스럽습니다. 이 논문 인 Splaying의 Global Geometric View 는 위의 관찰을 보는 방법을 자세히 보여줍니다.

이 사실을 알고 나면 로그 합계 가능성을 선택하는 것이 매우 당연합니다. 우리는 전체 재 배열 비용을 지불하기 위해 type-1 요소의 잠재적 변경을 사용할 수 있기 때문입니다. 또한 다른 유형의 요소의 경우 최대 로그에 의한 잠재적 변경에 대해 지불해야합니다. 따라서 대수 상각 비용을 도출 할 수 있습니다.

사람들이 이것이 “흑 마술”이라고 생각하는 이유는 이전 분석이 검색 경로의 전체적인 변화를 “펼치지”않고 실제로 한 단계에서 어떤 일이 일어나는지 확인하기 때문입니다. 대신, 그들은 각각의 “로컬 변환”에 대한 잠재력의 변화를 보여준 다음, 이러한 잠재적 변화가 마술처럼 망원경 될 수 있음을 보여줍니다.

추신이 논문은 심지어 로그의 합계 가능성의 한계를 보여줍니다. 즉 , 로컬 알고리즘에만 잠재적 인 로그 합을 통해 액세스 보조의 만족을 증명할 수 있습니다 .

로그 합계 잠재력의 해석

Georgakopoulos와 McClurkin의 논문 에서 BST의 잠재력을 정의하는 또 다른 방법이 있습니다. 이는 Sleator Tarjan의 논문에서 로그의 합계와 본질적으로 동일합니다. 그러나 이것은 나에게 좋은 직감을 제공합니다.

이제 종이 표기법으로 전환합니다. 모든 노드 가중치 를 할당합니다 . 를 의 서브 트리 가중치의 합 이라고합시다 . (이것은 모든 노드의 가중치가 1 일 때 의 서브 트리 크기입니다 .) $w (u)$

w(u)

$u$

$W (u)$

W(u)

$u$

이제 노드에서 순위를 정의하는 대신 가장자리에 순위를 정의하여 진행률 이라고 합니다.

p f (e) = log (W (u) / W (v)) .

그리고 나무 의 잠재력 $S$

은

Φ (S) = \sum e \in S p f (e) .

이 가능성은 자연스럽게 해석됩니다. 검색하는 동안 모서리 를 탐색하면 검색 공간이 의 자손에서 의 자손으로 감소하고 감소는 검색 공간을 줄입니다. $(u, v)$
(u,v)
$u$
u
$v$
v
$W (u) / W (v)$
W(u)/W(v)
. 우리의 진척도는이 ‘진보’에 대한 로그 측정 값이므로 그 이름입니다. [2.4 절부터]

이것은 Sleator Tarjan의 잠재력과 거의 동일하며 경로에 추가적입니다.

편집 : 이 대안 적 정의와 그 직관은 오래 전에 Kurt Mehlhorn에 의해 설명되었습니다. 그의 책 “데이터 구조와 알고리즘”제 1 권 III 장을 참조하십시오. 6.1.2 플레이 트리, 페이지 263-274.

How IT

언제든지 물어보세요.

태그 보관물: ds.data-structures

Splay Tree 잠재적 기능 : 왜 크기의 로그를 합산합니까? 구조의 분석과 직관에 익숙합니다. 그러나 Sleator와

답변

로그 합계 가능성을내는 방법

로그 합계 잠재력의 해석

답변