톱 트리

상단 트리는 뿌리 없는 동적 트리에 대한 이진 트리를 기반으로 하는 데이터 구조로, 주로 다양한 경로 관련 작업에 사용된다.그것은 간단한 분할-컨커링 알고리즘을 허용한다.이후 직경, 중심, 중위 등 나무의 다양한 특성을 역동적으로 유지하기 위해 증강되었다.

상단 트리 ${\displaystyle \Re}$은(는) 기본$$트리 $T{\displaystyle \mathcal{}}$ {\$displaystyle$ {\$mathcal {T}$에 대해 정의되며, 외부 경계 정점이라고 하는 최대 두 개의 꼭지점 중$$ $\partial {\displaystyle \mathrm{}}$ ${\displaystyle T}$ ${\$에 대해 정의된다.

용어집

경계 노드

경계 정점 참조

경계 정점

연결된 하위 트리의 꼭지점은 가장자리로 하위 트리 외부의 꼭지점에 연결된 경우 경계 정점이다.

외부 경계 정점

상단 트리 ${\displaystyle \Re}$의 정점 쌍까지 외부 경계 정점이라고 할 수 있으며$$, 전체 상단 트리를 나타내는 클러스터의 경계 정점이라고 생각할 수 있다.

군집

군집은 경계 정점 수가 최대 두 개인 연결된 하위 트리다.The set of Boundary Vertices of a given cluster ${\displaystyle {\mathcal {C}}}$ is denoted as ${\displaystyle \partial {C}.}$ With each cluster ${\displaystyle {\mathcal {C}}}$ the user may associate some meta information ${\displaystyle I({\mathcal {C}}),}$ and give methods to maintain i다양한 내부 작업 하에서.

경로 클러스터

$\pi {\displaystyle }$(${\displaystyle C}$) ${\displaystyle \pi({\mathcal{C}})$에 에지가 하나 이상 포함되어$$ 있으면 $C{\displaystyle \mathcal{}}$ ${\$을(를) 경로 클러스터라고 한다$$.

점 군집

리프 클러스터 참조

리프 클러스터

$\pi {\displaystyle }$(${\displaystyle C}$) ${\displaystyle \pi({\mathcal{C}})$에 에지가 없는$$ 경우.${\displaystyle \mathcal{C}}$ ${\$에는 경계 정점 하나만 있고$$, $C{\displaystyle \mathcal{}}$ ${\$은(는) 리프 클러스터라고 불린다$$.

에지 클러스터

단일 에지를 포함하는 클러스터를 에지 클러스터라고 한다.

리프 에지 클러스터

원래 군집의 잎은 단일 경계 정점만을 가진 군집으로 표현되며 잎 가장자리 군집이라고 불린다.

경로 에지 클러스터

경계 노드가 두 개인 에지 클러스터를 경로 에지 클러스터라고 한다.

내부 노드

$C{\displaystyle \mathcal{}}$ ${\$$}$ $\backslash$${\displaystyle c}$} $displaystyle \partial {C}$의 노드를 $C{\displaystyle \mathcal{}}$ . ${\displaystyle {\mathcal {C}$의 내부 노드라고 한다$$.$}$

클러스터 경로

$C{\displaystyle \mathcal{}}$ ${\$의 경계 꼭지점 사이의 경로를 C ${\$의 $클러스터{\displaystyle \mathcal{}}$ 경로라고 하며$$ $and$ (${\displaystyle }$C )${\displaystyle }$. ${\displaysty \pi({\mathc})$로 표시한다.$}$

병합 가능한 클러스터

Two Clusters ${\displaystyle {\mathcal {A}}}$ and ${\displaystyle {\mathcal {B}}}$ are Mergeable if ${\displaystyle {\mathcal {A}}\cap {\mathcal {B}}}$ is a singleton set (they have exactly one node in common) and ${\displaystyle {\mathcal {A}}\cup {\mathcal {B}}}$ is a Cluster.

소개

위쪽 트리는 링크와 절단 작업 하에서 동적 숲(나무 세트)을 유지하는 데 사용된다.

The basic idea is to maintain a balanced Binary tree ${\displaystyle \Re }$ of logarithmic height in the number of nodes in the original tree ${\displaystyle {\mathcal {T}}}$( i.e. in ${\displaystyle {\mathcal {O}}(\log n)}$ time) ; the top tree essentially represents the recursive subdivision of the original 트리 $T{\displaystyle \mathcal{}}$ ${\$을(를) 클러스터로 생성하십시오.

일반적으로 트리 $T{\displaystyle \mathcal{}}$ ${\$의 가장자리에 중량이 있을 수 있다$$.

원본 트리 $T{\displaystyle \mathcal{}}$ ${\$의 가장자리와 상단 트리 $\Re {\displaystyle \mathrm{}}$ ${\displaystyle \Re}$의 리프 노드와 correspondence ${\displaystyle \Re}$의 각 내부 노드는 그 하위인 클러스터의 결합으로 인해 형성된 클러스터를$$ 나타낸다.

상단 트리 데이터 구조는 $O{\displaystyle \mathcal{}}$( ${\displaystyle n}$) ${\displaystyle {\mathcal{O}(n)}$회$$ 단위로 초기화할 수 있다.

${\displaystyle 따라서}$ 위쪽 트리 ${\displaystyle \Re}$ over$$ (${\displaystyle \mathcal{}}$ ${\displaystyle ,}$ ${\displaystyle${\$mathcal {T},}$ $\partial$${\displaystyle \mathrm{}}$ T ${\$는 다음과 같은 이진수다.

• ${\displaystyle \Re}$의 노드는 (${\displaystyle \mathcal{}}$, ${\displaystyle {\mathcal {T},}$ $\partial$${\displaystyle \mathrm{}}$ ${\displaystyle T}$ ${\$의 클러스터$$;$$
• ${\displaystyle \Re}$의 잎은 $T{\displaystyle \mathcal{}}$; ${\displaystyle {\mathcal{T};}$의 가장자리 입니다$$.
• 형제 군집은 그들이 하나의 꼭지점에서 교차한다는 점에서 이웃이고, 그들의 부모 군집은 그들의 결합이다.
• ${\displaystyle \Re}$의 루트는 트리 $T{\displaystyle \mathcal{}}${\$displaystyle${\$mathcal {T}$ 그$$ 자체로$$ 외부 경계 정점 세트가 최대 두 개 입니다.

꼭지점이 하나 있는 나무는 맨 위 트리가 비어 있고, 가장자리만 있는 나무는 한 개의 노드에 불과하다.

이러한 트리는 사용자가 블랙박스라고도 하는 데이터 구조의 내부 작업 세부사항에 들어가지 않고도 자유롭게 확장할 수 있다.

동적 운영

다음 세 가지는 사용자 허용 포레스트 업데이트 입니다.

• 링크(v, w):다른 나무들은 어디 v{\displaystyle v}과 w{w\displaystyle} 있vertices T{\displaystyle{{T\mathcal}}}1과 T{\displaystyle{{T\mathcal}}}2.단 한명의 톱 나무 ℜ{\displaystyle \Re}v을 나타내는ℜ{\displaystyle \Re}w∪(vw){\d{\displaystyle \cup}∪을 반환합니다.$isplaystyle \cup{(v,w)}}}$
• Cut(vw):}나무 T{\displaystyle{{T\mathcal}에서}가장자리(vw){\displaystyle{(v,w)}을 제거합니다}최고 나무 ℜ과,{\displaystyle \Re,} T{\displaystyle{{T\mathcal}}}v와 T{\displaystyle{{T\mathcal}}}w와 2위의 나무들 돌아오는{\displ ℜ 두 나무로 변하며.아아!$스타일{\displaystyle \mathrm{}}$ $\Re$ } 및$$and$$_v ${\displaystyle \Re$ $\}.$_w
• 노출(S): 상위 트리에서 대부분의 쿼리를 구현하기 위한 하위 루틴으로 불린다.${\displaystyle S}$ ${\displaystyle S}$에는 최대 2개의 정점이 있다.원래 외부 정점을 정상 정점으로 만들고 $S{\displaystyle }$ ${\displaystyle S}$의 정점을 상단$$ 트리의 새로운 외부 경계 정점으로 만든다.$S{\displaystyle }$ ${\displaystyle S}$이(가) 비어 있지 않으면 새 루트 ${\displaystyle 클러스터}$ $C{\displaystyle \mathcal{}}$ ${\$을(를) 반환하고 vert${\displaystyle \mathrm{}}$C${\displaystyle }$= ${\displaystyle S.}$ ${\displaystyle \partial {C}=S.}$ 노출$$({v,w})이 실패함.

내부 운영

포리스트 업데이트는 모두 최대 $O{\displaystyle \mathcal{}(\log }$ $){\displaystyle {\mathcal{O}(\logn)}$ 내부$$ 운영의 시퀀스에 의해 수행되며, 이 시퀀스는${\displaystyle }추가{\displaystyle \mathcal{}}$ O(${\displaystyle \log )n}$ $){\displaystyle${\$mathcal}(\$logn) 시간 단위로$$ $계산된다.$트리를 업데이트하는 동안 리프 클러스터가 경로 클러스터와 반대로 변경될 수 있다.상위 트리에 대한 업데이트는 이러한 내부 작업에 의해 독점적으로 수행된다.

$I{\displaystyle }$( ${\displaystyle C}$) ${\displaystyle I({\mathcal{C})}$은(는) 각 내부 작업과 관련된 사용자 정의 함수를 호출하여 업데이트된다$$.

• Merge${\displaystyle ({\mathcal {A}},{\mathcal {B}}){:}}$ Here ${\displaystyle {\mathcal {A}}}$ and ${\displaystyle {\mathcal {B}}}$ are Mergeable Clusters, it returns ${\displaystyle {\mathcal {C}}}$ as the parent cluster of ${\displaystyle {\mathcal {A}}}$ and ${\displaystyle \mathcal{B}}$${\displaystyle {\mathcal {B}}}$ and with boundary vertices as the boundary vertices of ${\displaystyle {\mathcal {A}}\cup {\mathcal {B}}.}$ Computes ${\displaystyle I({\mathcal {C}})}$ using ${\displaystyle I({\mathcal {A}})}$ and ${\displaystyle I({\mathcal {B}}).$$}$
• Split${\displaystyle ({\mathcal {C}}){:}}$ Here ${\displaystyle {\mathcal {C}}}$ is the root cluster ${\displaystyle {\mathcal {A}}\cup {\mathcal {B}}.}$ It updates ${\displaystyle I({\mathcal {A}})}$ and ${\displaystyle I({\mathcal {B}})}$ using ${\displaystyle I(\mathcal{C}}$${\displaystyle )}$ ${\displaystyle I({\mathcal {C})}$ 및$$ 그 $이상$이면 $\Re {\displaystyle \mathrm{}}${\$displaystyle$$${\$mathcal {C}$에서 클러스터 C ${\$ ${\Re}$을(를) 삭제함$.$

Split is usually implemented using Clean${\displaystyle ({\mathcal {C}})}$ method which calls user method for updates of ${\displaystyle I({\mathcal {A}})}$ and ${\displaystyle I({\mathcal {B}})}$ using ${\displaystyle I({\mathcal {C}})}$ and updates ${\displayst$하위 항목에 보류 중인 업데이트가 필요하지 않다는 것을 알 수 있도록$$ $yle$ I$({\mathcal{C})}$$C{\displaystyle \mathcal{}}$ ${\$mathcal ${C}$은(는) 사용자 정의 함수를 호출하지 않고 폐기된다$$.분할할 필요 없이 쿼리에 대해 청소가 필요한 경우가 많다.분할이 Clean 서브루틴을 사용하지 않고 Clean이 필요한 경우, Merge와 Split을 결합하여 오버헤드로 효과를 얻을 수 있다.

다음 두 함수는 위의 두 함수와 유사하며, 베이스 클러스터에 사용된다.

• 생성${\displaystyle v}$, ${\displaystyle w}$)${\displaystyle }$: ${\$ 에지${\displaystyle (v}$, w${\displaystyle }$)에$$ $대한$ $클러스터$ C {\displaystyle ${\mathcal$ {$C}}$을(를$)$ $생성$하십시오$.$$\}\}{\displaystyle \mathrm{}}$ 집합 ${\displaystyle sets}$ C =$\$ {\$displaystyle \partial${C}=\$partial$${\displaystyle <img\; alt="\{\backslash displaystyle\; \backslash partial\; \{C\}=\backslash partial\; \}"\; aria-hidden="true"\; class="mwe-math-fallback-image-inline"\; src="https://wikimedia.org/api/rest\_v1/media/math/render/svg/d59abab506dc0cae7d12ddfaa4a5b0671db11db3"\; style="vertical-align:\; -0.338ex;\; width:7.501ex;\; height:2.176ex;"\; papago-attr-id="235">\}(v}$,${\displaystyle w}$) {\$displaystyle$ (${\displaystyle v\mathcal{}}$$,$w$){\displaystyle$ I$({\mathcal{C})}$는 처음부터$$ $계산$한다.
• 소거${\displaystyle C}$)${\displaystyle }$: ${\$ $C$${\displaystyle \mathcal{}}$ ${\${\$mathcal{C}}}}}$이(가) 에지 클러스터${\displaystyle (v}$ , ${\displaystyle w}$) 입니다.${\displaystystyle(v,w).$$}$ ${\displaystyle 사용자}$ 정의 함수를 호출하여 I(C ) ${\$displaystyle I({\$mathcal {C})}$을(를) 처리하고$,$ 클러스터$$ $C{\displaystyle \mathcal{}}$ {\$displaystyle {\mathcal {C}$을(를) 위쪽 트리에서 삭제한다$$.

로컬이 아닌 검색

사용자는 선택${\displaystyle C}$)${\displaystyle }$: ${\$ 작업을 정의할$$ 수 있으며, 루트(비리프) 클러스터에 대해 하위 클러스터 중 하나를 선택할 수 있다.상단 트리 블랙박스는 검색${\displaystyle C}$)${\displaystyle }$: ${\$ 루틴을$$ 제공하며, 이 루틴은 선택한 모든 클러스터의 교차로에서 유일한 가장자리를 찾을 수 있도록 상단 트리 선택 쿼리 및 재구성(내부 연산 사용)을 체계화한다.때때로 검색은 경로로 제한되어야 한다.그러한 목적을 위한 비현지적 검색의 변종이 있다.루트 클러스터 $C{\displaystyle \mathcal{}}$ ${\$에 두 개의 외부 경계 정점이 있는 경우$,$ 가장자리는 $){\displaystyle \pi({\mathcal {C})}$ 경로에서만 검색된다$.$다음과 같이 수정하면 충분하다.루트 클러스터 하위 클러스터 중 하나만 경로 클러스터인 경우 선택 작업을 호출하지 않고 기본적으로 선택된다.

로컬이 아닌 검색 예제

$v{\displaystyle \mathcal{}}$ ${\$$displaystyle$ $v}$에서 w ${\displaystyle w}$까지의 긴 경로에서 i번째 에지를 찾는 작업은 C ${\$$displaystyle {C}$=Expose$({$에 이어 적절한 선택을 통해 수행할 수 있다$$.$Choose$를 구현하려면 v {\$displaystyle v}$을(를$)$ 나타내는 전역 변수와 $i{\displaystyle .}$ ${\displaystyle i}$을(를) 나타내는 전역 변수를 사용하십시오. $v{\displaystyle }$ ${\displaystyle \in }$ ${\displaystyle \mathrm{\partial }}$ ∂ {${\displaystyle }$$\$ {\$displaystyle v\in$ $\partial$${A}$인 클러스터 $A{\displaystyle \mathcal{}}$ ${\$$displaystycal {A}$을$({\$$mathcal$)를 선택하십시오$$.$$ $작업$을 지원하려면 길이를 $I{\displaystyle }$ ${\displaystyle I}$에서 유지하십시오$.$

유사한 작업이 단위 길이가 아닌 가장자리가 있는 그래프에 대해 공식화될 수 있다.이 경우 거리는 두 가장자리 사이의 가장자리 또는 꼭지점을 나타낼 수 있다.후자의 경우 정점에 이르는 가장자리가 반환되도록 선택을 정의할 수 있다.상수에 의해 경로를 따라 모든 에지 길이를 증가시키는 정의된 업데이트가 있을 수 있다.이러한 시나리오에서 이러한 업데이트는 루트 클러스터에서만 일정한 시간에 수행된다.지연된 업데이트를 아이들에게 배포하려면 청소가 필요하다.선택을 호출하기 전에 Clean을 호출해야 한다.$I{\displaystyle }$ ${\displaystyle I}$에서 길이를 유지하려면 $I{\displaystyle }$ ${\displaystyle I}$에서도 단위 길이를 유지해야 한다$$.

꼭지점 $v{\displaystyle }$ ${\displaystyle v}$을(를) 포함하는 트리의 중심을 찾는 작업은 중앙을 하나의 끝점으로 하는 바이컨터 에지 또는 에지를 찾는 방법으로 수행할 수 있다$$.가장자리는 $C{\displaystyle \mathcal{}}$ ${\$=Expose({v})에 의해 찾을 수 있으며, 검색(${\displaystyle \mathcal{}}$ ${\$이$($가) 적절한 선택을 통해 찾을 수 있다.The choose selects between children ${\displaystyle {\mathcal {A}},}$ ${\displaystyle {\mathcal {B}}}$ with ${\displaystyle a\in \partial {A}\cap \partial {B}}$ the child with higher maxdistance${\displaystyle (a)}$. To support the operation the maximal distance in the cluster subtree f롬 경계 꼭지점은 $I{\displaystyle }$ ${\displaystyle I}$에서 유지되어야 한다$.$ 이 경우 클러스터 경로 길이도 유지 관리해야 한다.

흥미로운 결과 및 애플리케이션

원래 다른 방법에 의해 구현된 많은 흥미로운 애플리케이션들은 상위 트리의 인터페이스를 사용하여 쉽게 구현되었다.그 중에는 다음과 같은 것도 있다.

• ([슬레이터 및 타르잔 1983]).가중 트리의 동적 컬렉션을 링크당 $O{\displaystyle \mathcal{}(\log }$ ${\displaystyle n}$) ${\displaystyle {\mathcal{O}(\log$ n$)}$회$$ 유지하여 $O{\displaystyle (\log }$ ${\displaystyle n}$) ${\displaystyle O(\log$ n$)}$회$$ 두 꼭지점 사이의 최대 에지 중량에 대한 쿼리를 지원할 수 있다.
  • 증명 개요:각 노드에서 클러스터 경로의 최대 중량(max_wt)을 유지하는 것이 포함되며, 포인트 클러스터인 경우 max_wt(${\displaystyle \mathcal{}}$ ${\$가 -${\displaystyle \mathrm{}\infty .}$ ${\displaystyle -\inful.}$ 클러스터가 두 클러스터 조합인 경우$$, 두 개의 병합된 클러스터의 최대값이다.$v{\displaystyle }$ ${\displaystyle v}$과 $w{\displaystyle }$ ${\displaystyle w}$ 사이에 최대 wt를 찾아야 하는 경우$$ $C{\displaystyle \mathcal{}}$$$${\displaystyle }$= ${\displaystyle {\mathcal}=}$노출$$${\displaystyle v}$, w${\displaystyle ),}$ ${\displaystystyle$${\displaystyle (v,}$$w),$ ${\displaystystyle({\mathc}).$$}$
• ([슬레이터 및 타르잔 1983]).위의 애플리케이션 시나리오에서 $($ ${\displaystyle n}$ ${\displaystyle )}$ ${\displaystyle {O}(\$$displaystyle v}$ $$· ${\displaystyle }$ ${\displaystyle$ w$}$의 지정된$$$$ $경로$에 있는$$ 모든 $에지$에$$공통 $중량$ x {\$displaystyle$$x}$를 추가할 수도 있다.
  • 증명 개요:$\pi {\displaystyle (C}$)$$. {\$displaystyle {\mathcal{C$의 모든 가장자리에 추가하기 위해 extra(${\displaystyle \mathcal{}}$ ${\$$displaystyle \pi({\mathcal {C})$라는 가중치를 도입한다.$}$ Which is maintained appropriately ; split(${\displaystyle {\mathcal {C}}}$) requires that, for each path child ${\displaystyle {\mathcal {A}}}$ of ${\displaystyle {\mathcal {C}},}$ we set max_wt(A) := max_wt(${\displaystyle {\mathcal {A}}}$) + extra(${\displaystyle {\mathcal {C}}}$)및 extra(${\displaystyle \mathcal{}}$ ${\displaystyle$ {\$mathcal {A$ := extra(${\displaystyle \mathcal{}}${\$displaystyle${\$mathcal {A$$$ + extra(${\displaystyle \mathcal{}}${\$displaystystyle${\$mathcal}).$For ${\displaystyle {\mathcal {C}}}$ := join(${\displaystyle {\mathcal {A}},}$ ${\displaystyle {\mathcal {B}}}$), we set max_wt(${\displaystyle {\mathcal {C}}}$) := max {max_wt(${\displaystyle {\mathcal {A}}}$), max_wt(${\displaystyle {\mathcal {B}}}$)} and extra(${\displaystyle \mathcal{C}}$${\displaystyle {\mathcal{C$ := 0.마지막으로 $v{\displaystyle }$ ${\$$displaystyle$ $v}$ $$· · ${\displaystyle }$, ${\displaystyle w,}$ $경로$에서 최대 중량을 찾기 위해 C ${\$ :=$$ 노출${\displaystyle v}$, ${\displaystyle w}$) ${\displaystyle(v$$,w$$)$ 및$$ 반환 max_wt($})$를 설정하십시오$$.$$
• ([골드버그 ET. 1991]).$O{\displaystyle \mathcal{}(\log }$ ${\displaystyle n}$) ${\displaystyle {\mathcal {O}(\log n)}$ 시간에$$$$ 지정된 꼭지점 $v{\displaystyle }$ ${\displaystyle v}$을(를) 포함하는 기본 트리의 최대 중량을 요청할 수 있다.
  • 증명 개요:이를 위해서는 병합 및 분할 작업의 클러스터에 있는 최대 비클러스터 경로 에지에 대한 추가 정보를 유지해야 한다.
• $두{\displaystyle \mathcal{}}$ 꼭지점 $v{\displaystyle }$ ${\$$displaystyle$ $v}$과 $w{\displaystyle }$ ${\$displaystyle w} 사이의 $거리는$O$($로그 ${\displaystyle (n}$ )$displaystyle$ {\$mathcal{O}(\log n)}$시간에서$$ 길이${\displaystyle }$expose $($로 확인할 수 있다$$.$$
  • 증명 개요:클러스터 경로의 길이(${\displaystyle \mathcal{}}$ ${\$를 유지 관리한다.$길이$는 C {\$displaystyle {\mathcal {C}$이(가) ${\displaystyle \mathcal{}}$(Merge)에 의해 생성된$$ 경우$($C {\$displaystyle$ {\$mathcal {C$가 경로 자식과 함께 저장된 길이의 합계인 것을 제외하고 최대 중량으로 유지된다.
• 트리의 직경 및 이후 유지보수에 대한 쿼리는 O${\displaystyle (}log{\displaystyle \mathcal{}\mathrm{logn}}$) ${\displaystyle {\mathcal {O}(\log$ n$)}$시간이$$ 소요된다.
• 센터와 중위수는 링크(Merge) 및 컷(Split) 작업으로 유지 관리할 수 있으며 $비{\displaystyle \mathcal{}}$ 로컬 검색으로 O$){\displaystyle {\mathcal$ {$O}(\log n)}$시간$$ 내에 쿼리할 수 있다.
• 그래프는 에지 세트를 업데이트하고 에지 2 연결성에 대한 쿼리를 요청할 수 있도록 유지될 수 있다.업데이트의 상각 복잡성은 $O{\displaystyle ({\log }^{}}$ ${\displaystyle {4\mathrm{}}^{}}$ ${\displaystyle {}^{}n}$) ${\displaystyle O(\log ^{4}n$ 쿼리는 훨씬 더 빨리 구현될 수 있다.알고리즘은 사소한 것이 아니며, $I{\displaystyle }$(${\displaystyle C\mathcal{}}$ ) ${\displaystyle$ I$({\mathcal{C}})$은 $\theta {\displaystyle \mathrm{}({\mathrm{로그}}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}n}$) ${\displaystyle \Theta(\log ^{2}n)}$ 공간$$([HOLM, LICHTENBERG, SORUP 2000]을 사용한다$$.
• 그래프는 에지 세트를 업데이트하고 정점 2 연결성에 대한 쿼리를 요청할 수 있도록 유지될 수 있다.업데이트의 상각 복잡성은 $O{\displaystyle ({\log }^{}}$ ${\displaystyle {5\mathrm{}}^{}}$ ${\displaystyle {}^{}n}$) ${\displaystyle O(\log ^{5}n$ 쿼리는 훨씬 더 빨리 구현될 수 있다.알고리즘은 사소한 것이 아니며, $I{\displaystyle }$(${\displaystyle C\mathcal{}}$ ) ${\displaystyle$ I$({\mathcal{C}})$은 $\theta {\displaystyle \mathrm{}({\mathrm{로그}}^{}}$ ${\displaystyle {2\mathrm{}}^{}}$ ${\displaystyle {}^{}n}$ ${\displaystyle )}$ ${\displaystyle \Theta(\log ^{2}n)}$ 공간$$([HOLM, LICHTENBERG, SORUP 2001]을 사용한다$$.
• 위쪽 트리는 DAG 압축보다 결코 나쁘지 않은 방식으로 나무를 압축하는 데 사용될 수 있지만 기하급수적으로 더 좋을 수 있다.^[1]

실행

탑 트리는 다양한 방식으로 구현되어 왔으며, 그 중에는 멀티레벨 파티션(Top-tree 및 동적 그래프 알고리즘 Jacob Holm과 Kristian de Lichtenberg)을 사용한 구현도 포함되어 있다.기술 보고서), 그리고 심지어 Sleator-Tarjan s-t 트리(일반적으로 상각된 시간 범위 포함), Frederickson의 토폴로지 트리(최악의 경우 시간 범위 포함)를 사용함(Alstrip et al.상단 트리가 있는 완전 동적 트리에서의 정보 유지).

상각된 구현은 더 단순하며, 시간 복잡성에 있어 작은 배증적 요인이 있다.반대로 최악의 경우 구현을 통해 쿼리 중에 불필요한 정보 업데이트를 꺼 쿼리 속도를 높일 수 있다(지속성 기법에 의해 구현됨).쿼리에 응답한 후에는 최상위 트리의 원래 상태가 사용되고 쿼리 버전은 폐기된다.

멀티레벨 파티셔닝

트리 $T{\displaystyle \mathcal{}}$ ${\$의 클러스터 분할은 $트리{\displaystyle \mathcal{}}$ T ${\$의 각 클러스터를 에지로$$ 교체하여$$ 클러스터 파티션 트리 CPT${\displaystyle T}$)${\displaystyle }$, ${\displaystystyle({\mathcal {T})$로 나타낼 수 있다$$.$T{\displaystyle \mathcal{}}$ {\$displaystyle {\mathcal$ {$T}$ 분할에 전략 P를 사용하면 CPT_P $.$ {\$displaystyle {\mathcal {T}}$이(가) CPT가 된다. 이$$ 작업은$$ 에지 하나만 남아 있을 때까지 반복적으로 수행된다.

해당하는 상위 트리 ${\displaystyle \Re }$의 모든 노드가 이 다단계 파티션의 가장자리에 고유하게 매핑되어 있음을$$ 알 수 있다.상단 트리의 어떤 노드에도 해당되지 않는 다단계 파티션에 일부 가장자리가 있을 수 있으며, 이러한 가장자리는 그 아래 레벨에서 단 하나의 아이만을 나타내는 가장자리, 즉 단순 클러스터가 있을 수 있다.복합 클러스터에 해당하는 가장자리만 상위 트리 $\Re {\displaystyle \mathrm{}}$. ${\displaystyle \Re .}$의 노드에 해당한다.

Tree $T{\displaystyle \mathcal{}}$ ${\$을(를) 클러스터로$$ 분할하는 동안 파티셔닝 전략이 중요하다.신중한 전략만이 $우리$가 O${\displaystyle }$(${\displaystyle \log }$ $){\displaystyle {\mathcal {O}(\logn)}$높이의$$ 다단계 파티션(따라서 상단 트리)에 있게 한다.

• 후속 수준의 가장자리 수는 상수 인자에 의해 감소해야 한다.
• 업데이트에 의해 하위 수준이 변경되는 경우, 우리는 최대한 일정한 개수의 삽입 및 삭제를 사용하여 바로 위의 단계를 업데이트할 수 있을 것이다.

위의 분할 전략은 상위 트리를 O(log${\displaystyle \mathcal{}\mathrm{logn}}$ )${\displaystyle {\mathcal$ {$O}(\log$ n$)}$시간 내에$$ 유지하도록 보장한다.

참조

• Stephen Alstrup, Jacob Holm, Kristian De Lictenberg, Mikkel Thorup, 상부 트리가 있는 완전 동적 트리, ACM Transactions on Algorithm, Vol. 1(2005), 243–264, doi:10.1145/1103963.1103966.
• Stephen Alstrup, Jacob Holm, Kristian De Lichtenberg, and Mikkel Thorup, Poly-logarithmic deterministic fully-dynamic algorithms for connectivity, minimum spanning tree, 2-edge, and biconnectivity, Journal of the ACM, Vol. 48 Issue 4(July 2001), 723–760, doi:10.1145/502090.502095
• 도널드 크누스컴퓨터 프로그래밍 기술: 기본 알고리즘, 제3판.애디슨 웨슬리, 1997년 ISBN0-201-89683-4. 섹션 2.3: 나무, 페이지 308–423.
• 토마스 H. 코멘, 찰스 E. Leiserson, Ronald L. Rivest, Clifford Stein.알고리즘 소개, Second Edition.MIT 프레스 앤 맥그로우 힐, 2001.ISBN 0-262-03293-7. 섹션 10.4: 뿌리깊은 나무를 나타냄, 페이지 214–217.12~14장(이진 검색 트리, 적색-흑색 트리, 데이터 구조 증강), 페이지 253~320.

외부 링크

• 위쪽 트리가 있는 완전 동적 트리에서의 정보 유지알월르프 외
• 자체 조정 탑 트리.타르잔과 베르넥, Proc. 16th SodDA, 2005