탱고나무

이 기사는 대체로 또는 전적으로 단일 출처에 의존한다. 관련 토론은 토크 페이지에서 찾을 수 있다. 추가 출처에 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. 출처 찾기: "탄고나무" – 뉴스 · 신문 · 도서 · 학자 · JSTOR (2021년 3월)

탱고 트리는 에릭 D가 제안한 바이너리 검색 트리의 일종이다. 2004년 데메인, 디온 하모니, 존 아이코노, 미하이 피트라슈쿠.^[1]그것은 부에노스 아이레스의 이름을 따서 명명되었는데, 그 중 탱고는 상징적이다.

오프라인 최적 바이너리 검색 트리에 비해 $($${\displaystyle \log }$ ${\displaystyle }$ ${\displaystyle \log }$ ${\displaystyle )}$${\displaystyle n}$ ){\$displaystyle$ O$(\log \log$ n)}의 경쟁률을 달성하는 온라인 바이너리 검색 트리로, 노드당 $메모리{\displaystyle }$ 추가$$ $비트만$ O$(log \log \log$ n)를 사용한다.이는 이전에 가장 잘 알려진 경쟁률에서 개선되었는데, $O{\displaystyle (\log }$ ${\displaystyle n}$) ${\displaystyle$ O$(\log$ n$)}$이었다$.$

구조

탱고 트리는 이진 검색 트리를 보조 트리에 저장되는 일련의 선호 경로로 분할하여 작동한다(따라서 탱고 트리는 나무의 나무로 표현된다.

참조 트리

탱고 트리를 구성하기 위해 우리는 참조 트리라고 불리는 완전한 이진 검색 트리를 시뮬레이션 하는데, 이것은 단순히 모든 요소를 포함하는 전통적인 이진 검색 트리일 뿐이다.이 나무는 실제 구현에서는 결코 나타나지 않지만, 다음의 탱고 나무 조각 뒤에 숨겨진 개념적 기초가 된다.

특히 참조 트리의 높이는 ⌈log₂(n+1)⌉이다.이것은 가장 긴 경로의 길이와 같으며, 따라서 가장 큰 보조 트리의 크기와 같다.보조 트리의 균형을 적절히 유지함으로써 보조 트리의 높이를 O(로그 로그 n)로 제한할 수 있다.이것이 알고리즘의 성능 보증의 원천이다.

선호 경로

첫째, 우리는 각 노드에 대해 선호되는 하위를 정의하는데, 이것은 비공식적으로 기존의 바이너리 검색 트리 검색에서 가장 최근에 방문한 하녀다.보다 공식적으로, p에 뿌리를 둔 하위 트리 T를 아이 l(왼쪽)과 r(오른쪽)과 함께 고려한다.T에서 가장 최근에 액세스한 노드가 r에 뿌리를 둔 하위 트리에 있는 경우 r을 p의 우선 자식으로 설정하고, 그렇지 않은 경우 l을 우선 자식으로 설정했다.가장 최근에 액세스한 T의 노드가 p 그 자체라면, 정의상 l가 선호되는 아이라는 점에 유의한다.

선호 경로는 루트에서 시작하여 leaf 노드에 도달할 때까지 선호되는 아동을 따라 정의된다.이 경로에서 노드를 제거하면 트리의 나머지 부분이 여러 하위 트리로 분할되고 각 하위 트리에서 반복된다(이 하위 트리를 더 많은 하위 트리로 분할하는 루트로부터 기본 경로를 형성함).

보조나무

선호 경로를 나타내기 위해 우리는 균형 잡힌 이진 검색 트리, 특히 빨간색-검은색 트리에 노드를 저장한다.선호 경로 P의 각 비잎 노드 n에 대해, 그것은 새로운 보조 트리의 루트인 비선호 자식 c를 가지고 있다.우리는 이 다른 보조 나무의 뿌리(c)를 P의 n에 붙여서 보조 나무들을 서로 연결시킨다.또한 각 노드에 해당 노드 아래의 하위 트리에 노드의 최소 및 최대 깊이(기준 트리 깊이, 즉 참조 트리 깊이)를 저장함으로써 보조 트리를 증가시킨다.

알고리즘.

검색 중

탱고 트리에서 요소를 검색하려면 참조 트리 검색을 시뮬레이션하기만 하면 된다.우리는 루트에 연결된 선호 경로를 검색하는 것으로 시작하여, 선호 경로에 해당하는 보조 트리를 검색하여 시뮬레이션한다.보조 트리가 원하는 요소를 포함하지 않으면 원하는 요소(다른 선호 경로의 시작)를 포함하는 하위 트리의 루트 부모에서 검색이 종료되므로, 보조 트리에서 해당 선호 경로를 검색하는 등의 방법으로 간단히 진행한다.

업데이트 중

탱고 나무(보조나무가 선호 경로에 해당)의 구조를 유지하기 위해서는 검색 결과 선호도가 높은 아이들이 바뀔 때마다 일부 업데이트 작업을 해야 한다.선호도가 높은 아이가 바뀌면 선호경로의 상단부가 하단부(자체 선호경로가 됨)에서 분리되어 다른 선호경로(새로운 하단부가 됨)에 다시 붙는다.이를 효율적으로 하기 위해, 우리는 우리의 보조 나무에 대한 절단 작업을 정의하고 합류할 것이다.

가입하다

우리의 결합작전은 (참조 트리에서) 하나의 상단 노드가 다른 노드의 하단 노드의 하위 노드(필수적으로, 해당 선호 경로를 연결시킬 수 있는)라는 속성을 그들이 가지고 있는 한 두 개의 보조 트리를 결합할 것이다.이는 한 나무의 모든 원소가 다른 나무의 모든 원소보다 적다는 속성이 있는 한 두 그루의 나무를 결합한 적흑백나무와 그 반대로 갈라지는 적흑백나무의 결합작전을 바탕으로 작용하게 된다.참조 트리에서 상단 경로에는 노드의 키 값이 사이에 있는 경우에만 노드가 하단 경로에 있도록 두 개의 노드가 존재한다는 점에 유의하십시오.이제, 맨 위 길로 가기 위해, 우리는 그 두 개의 노드로 위쪽 경로를 나눈 다음, 맨 아래 경로의 보조 트리의 양쪽에 있는 두 개의 보조 트리를 연결하면, 마지막으로 연결된 보조 트리가 있다.

잘라내다

우리의 컷 오퍼레이션은 선호 경로를 주어진 노드에서 상단과 하단의 두 부분으로 나눌 것이다.좀 더 형식적으로, 보조 트리를 두 개의 보조 트리로 분할해서 하나는 참조 트리의 특정 깊이 또는 그 깊이 이상의 모든 노드를 포함하고 다른 하나는 그 깊이 아래의 모든 노드를 포함한다.조인에서와 마찬가지로 상단 부품에는 하단 부품을 브래킷하는 두 개의 노드가 있다는 점에 유의하십시오.따라서 이 두 개의 노드에 각각 분할하여 경로를 세 부분으로 나눈 다음, 바깥쪽 두 개의 노드를 결합하여 원하는 대로 상단과 하단의 두 부분으로 끝맺을 수 있다.

분석

탱고 나무의 경쟁률을 묶기 위해서는 우리가 벤치마킹으로 사용하는 최적의 오프라인 트리의 성능에서 하한을 찾아야 한다.일단 탱고나무의 성능에서 상한을 찾으면 경쟁률의 결합으로 나눌 수 있다.

인터리브 바운드

최적의 오프라인 바이너리 검색 트리에 의해 수행된 작업에 대한 하한을 찾기 위해 우리는 다시 선호되는 자식 개념을 사용한다.액세스 시퀀스(검색 시퀀스)를 고려할 때 참조 트리 노드가 선호하는 하위 스위치의 횟수를 추적한다.총 스위치 수(모든 노드에 포함)는 주어진 액세스 시퀀스에 대해 어떤 이진 검색 트리 알고리즘에 의해 수행되는 작업에 대해 점증상 하한을 제공한다.이것을 인터리브 하한이라고 한다.^[1]

탱고나무

이것을 탱고 나무와 연결하기 위해, 우리는 탱고 나무에서 주어진 접속 순서에 따라 하는 작업에서 상한을 찾을 것이다.우리의 상한은${\displaystyle }$(${\displaystyle \mathrm{k}}$+ 1${\displaystyle }$) ${\displaystyle O}$ ${\displaystyle (\log }$ ${\displaystyle }$ ${\displaystyle \log }$ ${\displaystyle n}$) ${\displaystyle (k+1)O(\log \log$ n$)}$이 될 것이다$.$ 여기서 k는 인터리브의 수입니다.

총 비용은 두 부분으로 나누어 원소를 검색하고 탱고 나무의 구조를 업데이트하여 적절한 불변제(선호자녀 전환 및 선호경로 재지정)를 유지한다.

검색 중

검색(업데이트하지 않음)이가바인딩에 적합한지 확인하려면, 보조 트리 검색이 실패할 때마다 다음 보조 트리로 이동해야 하며, 이 경우 부모 선호 경로가 현재 자식 선호 경로에 가입하기 위해 방향을 전환하므로 선호되는 자식 스위치가 발생한다는 점에 유의하십시오.$마지막{\displaystyle }$(검색에 성공하면 자연스럽게 중지됨)을 제외한 모든 보조 트리 검색이 실패하므로 k +${\displaystyle 1}$ ${\displaystyle k+1}$보조$$ 트리를 검색한다.보조 트리의 크기는 참조 트리의 높이인$$${\displaystyle \mathrm{로그}}$ ${\displaystyle n}$ ${\$$displaystyle O(\log \log$n)로 제한되기 때문에 각 검색에는 $O{\displaystyle (\mathrm{로그}\mathrm{logn}}$ $){\$$displaystyle \log n}$가 소요된다$.$

업데이트 중

업데이트 비용은 방문 보조 트리에 대해 하나의 컷과 조인만 수행하면 되기 때문에 이 바인딩에도 적합하다.단 한 번의 절단 또는 결합 작업에는 일정한 검색, 분할, 연결만 필요하며, 각 작업에는 보조 트리 크기의 로그 시간이 소요되므로 업데이트 비용은${\displaystyle }$(${\displaystyle \mathrm{k}}$+ 1 )${\displaystyle O(\mathrm{로그}}$ ${\displaystyle }$ ${\displaystyle \mathrm{로그}}$ ${\displaystyle n}$) ${\displaystyle (k+1$)O$(\$log $\log$ \$log n)}$ 입니다$.$

경쟁률

Tango trees are ${\displaystyle O(\log \log n)}$-competitive, because the work done by the optimal offline binary search tree is at least linear in k (the total number of preferred child switches), and the work done by the tango tree is at most ${\displaystyle (k+1)O(\log \log n)}$.

참고 항목

• 스플레이 트리
• 최적의 이진 검색 트리
• 붉은-검은 나무
• 트리(데이터 구조)

참조