회전 거리

Rotation distance

이산 수학과 이론 컴퓨터 과학에서, 같은 수의 노드를 가진 두 이진 트리 사이의 회전 거리는 한 트리를 다른 트리로 재구성하는 데 필요한 최소 회전 수입니다.2진수 트리와 볼록 폴리곤의 삼각 측량 사이의 조합적 등가성으로 인해 회전 거리는 볼록 폴리곤의 삼각 측량 시 플립 거리와 동일합니다.

회전 거리는 1982년 [1]카렐 취릭 2세와 데릭 우드에 의해 처음 정의되었다.모든 두 개의 n-노드 이진 트리는 최대 2n - 6개의 회전 거리를 가지며, 일부 트리 쌍은 정확히 이 거리를 가집니다.회전 거리를 계산하는 계산의 복잡성은 [2]알려지지 않았다.

정의.

트리 회전

바이너리 트리는 노드 세트로 구성되며, 그 중 하나는 루트 노드로 지정되며, 나머지 각 노드는 다른 노드의 왼쪽 자식 또는 오른쪽 자식이며, 어떤 노드로부터의 부모 링크를 따라가면 결국 루트 노드로 이어지는 구조입니다(일부 소스에서는 여기에 기술된 노드를 "i"라고 합니다).nternal nodes"는 "nternal nodes"라고 불리는 또 다른 노드 세트가 존재하며, 각 내부 노드에는 정확히 2개의 하위 노드가 있어야 하며, 각 외부 노드에는 [1]0개의 하위 노드가 있어야 합니다.여기서 설명하는 버전은 이러한 트리에서 모든 외부 노드를 삭제함으로써 얻을 수 있습니다.)

트리의 임의의 노드x에 대해 x에 루트를 두고 부모링크를 팔로우함으로써 x에 도달할 수 있는 모든 노드로 구성된 같은 형식의 서브트리가 있습니다.각 바이너리 트리에는 노드의 왼쪽에서 오른쪽 순서로 순서가 매겨져 있습니다.순서 트래버설은 왼쪽 서브트리(자녀의 경우 루트의 왼쪽 서브트리)를 재귀적으로 횡단한 후 루트 자체를 나열한 후 오른쪽 서브트리를 재귀적으로 횡단함으로써 얻을 수 있습니다.바이너리 서치 트리에서는, 각 노드가 서치 키에 관련지어져 왼쪽에서 오른쪽으로의 순서가 [2]키의 순서와 일치할 필요가 있다.

트리 회전은 왼쪽에서 오른쪽으로 순서를 변경하지 않고 이진 트리의 구조를 변경하는 작업입니다.여러 자체 밸런싱 바이너리 검색 트리 데이터 구조에서는 이러한 회전을 재조정 알고리즘의 초기 작업으로 사용합니다.회전은 2개의 노드 x와 y에서 동작하며, 여기서 x는 y의 부모이며, y를 x의 부모로 하고, 트리에서 x의 자리를 차지하는 것으로 트리를 재구성한다.y의 하위 링크 중 하나를 해제하고 y의 하위 링크로 x를 링크할 공간을 확보하기 위해 이 작업은 y의 하위 링크 중 하나를 x의 하위 링크로 이동해야 할 수도 있습니다.이 작업에는 두 가지 종류가 있습니다.즉, y가 x의 왼쪽 자식으로 시작하고 x가 y의 오른쪽 자식으로 끝나는 오른쪽 회전과 y가 y의 왼쪽 자식으로 시작하는 왼쪽 회전에서는 y가 x의 오른쪽 자식으로 시작하고 x가 y의 왼쪽 회전은 y가 [2]y의 왼쪽 자식으로 끝나는 것입니다.

왼쪽에서 오른쪽으로 동일한 노드 시퀀스를 가진 두 개의 트리는 일련의 회전 시퀀스에 의해 서로 변환될 수 있습니다.두 트리 사이의 회전 거리는 이 변환을 수행하는 가능한 가장 짧은 회전 시퀀스의 회전 수입니다.또한 회전 그래프에서 최단 경로 거리로 설명할 수 있습니다. 이 그래프는 주어진 왼쪽에서 오른쪽으로의 노드 시퀀스에 각 이진 트리의 정점과 두 [2]트리 사이의 각 회전마다 모서리가 있는 그래프입니다.이 회전 그래프는 정점과 사면체의 [3]모서리 그래프입니다.

뒤집기 거리에 대한 동등성

3노드 및 4노드 이진 트리의 회전에 해당하는 오각형과 육각형의 플립 그래프

일부 기하학적 객체의 삼각 측량 패밀리가 주어진 경우, 플립은 두 삼각형 사이의 모서리를 제거하고 그 결과 사각형에 반대 대각선을 더함으로써 한 삼각형을 다른 삼각으로 변환하는 연산입니다.두 삼각 측량 사이의 플립 거리는 한 삼각 측량을 다른 삼각 측량으로 변환하는 데 필요한 최소 플립 횟수입니다.또한 각 삼각측량에 대한 정점과 두 삼각측량 사이의 각 플립에 대한 모서리가 있는 그래프인 플립 그래프에서 최단 경로 거리로 설명할 수 있습니다.플립 및 플립 거리는 유클리드 평면의 점 집합의 삼각 측량, 폴리곤의 삼각 측량, 추상 다지관의 삼각 측량 등 여러 가지 다른 종류의 삼각 측량에 대해 이 방법으로 정의할 수 있습니다.

지정된 루트 에지를 가진 볼록 폴리곤의 삼각측량과 n-side 폴리곤의 삼각측량을 n - 2노드를 가진 이진 트리로 만드는 이진 트리 사이에는 일대일 대응 관계가 있다.이 대응에서 삼각측량의 각 삼각형은 2진수 트리의 노드에 대응한다.루트 노드는 지정된 루트 에지를 한 변으로 갖는 삼각형이며, 대응하는 삼각형이 삼각측량에서 대각선을 공유할 때 트리에서 두 노드가 부모 및 자녀로 연결됩니다.이 대응에서 이진 트리의 회전은 해당 삼각 측량에서의 플립과 정확히 일치합니다.따라서 (n - 2)-노드 트리의 회전 거리는 n면 볼록 다각형의 삼각 측량에서의 플립 거리와 정확히 일치합니다.

최대값

Chulik & Wood(1982)는 이진 트리의 "오른쪽 척추"를 루트부터 시작하여 오른쪽 자식 링크를 따라 오른쪽 자식 없는 노드에 도달함으로써 얻을 수 있는 경로로 정의한다.트리가 모든 노드가 오른쪽 척추에 속하지 않는 속성을 가진 경우 오른쪽 척추의 길이를 늘리는 올바른 회전이 항상 존재합니다.이 경우 오른쪽 척추에 하나 이상의 노드 x가 존재하며 오른쪽 척추에 없는 왼쪽 자식 y가 있습니다.x와 y에서 오른쪽 회전을 수행하면 다른 노드를 제거하지 않고 오른쪽 척추에 y가 추가됩니다.오른쪽 척추의 길이를 반복적으로 늘림으로써, 모든 노드가 오른쪽 척추에 속하는 동일한 노드 순서로 n-node 트리를 고유 트리로 변환할 수 있다.동일한 노드 순서를 가진 임의의 2개의 트리를 지정하면 첫 번째 트리를 오른쪽 척추에 있는 모든 노드가 있는 트리로 변환한 다음 두 번째 트리의 동일한 변환을 최대 2n-2 단계로 역전시킴으로써 한 트리를 다른 트리로 변환할 수 있습니다.따라서 Chulik & Wood(1982)가 증명했듯이, 두 나무 사이의 회전 거리는 최대 2n - [1]2이다.

Sleator, Tarjan 및 Thurston(1988)은 나무의 회전 대신 볼록 다각형의 공중제비 문제를 고려함으로써 회전 거리가 최대 2n - 6이라는 것을 보여줄 수 있었다.볼록 다각형의 삼각측량에서 오른쪽 척추는 루트 에지의 오른쪽 끝점에 입사하는 삼각형의 시퀀스이며, 모든 정점이 척추에 놓여 있는 트리는 이 정점에 대한 팬 삼각측량에 대응합니다.이러한 개선의 주요 아이디어는 주어진 삼각측량을 루트 가장자리의 오른쪽 끝점만이 아니라 모든 정점에 대해 팬 삼각측량으로 플립하는 것입니다.이러한 모든 선택사항이 동시에 각 시작 삼각 측량으로부터 최악의 경우 거리 n - 1을 제공하는 것은 불가능하며,[2] 따라서 개선 효과를 얻을 수 있습니다.

Sleator, Tarjan & Thurston(1988)도 기하학적 인수를 사용하여 무한히 많은 n 값에 대해 최대 회전 거리가 정확히 2n - 6임을 보여준다.그들은 다시 볼록 다각형의 삼각 측량을 뒤집는 관점에서 문제의 해석을 사용하고, 시작과 끝 삼각 측량을 볼록 다면체의 윗면과 아랫면으로 해석하고, 볼록 다면체 자체는 이 다면체에서 해밀턴 회로로 해석한다.이 해석에 따르면, 한 삼각형에서 다른 삼각형으로의 일련의 플립은 주어진 3차원 다면체를 삼각 측량하는 사면체의 집합으로 해석될 수 있다.그들은 (3차원 쌍곡 기하학에서) 다면체의 부피는 크지만, 그 안에 있는 모든 사면체는 훨씬 더 작은 부피를 가지고 있다는 특성을 가진 다면체의 패밀리를 발견하는데, 이는 모든 삼각측량에 많은 사면체가 필요하다는 것을 의미한다.이 다면체의 윗면과 아랫면 세트를 다시 나무로 변환하여 얻은 이원 나무는 적어도 2n - 6개의 [2]높은 회전 거리를 가진다.

그 후, Fournin(2014)은 모든 n µ 11에 대해 최대 회전 거리가 정확히 2n - 6이라는 증거를 제공했다. Pournin의 증거는 조합적이며 쌍곡 [3]기하학 사용을 피한다.

계산의 복잡성

수학의 미해결 문제:

두 나무 사이의 회전 거리를 계산하는 것은 얼마나 복잡합니까?

(수학에서 풀리지 않은 문제가 더 많다)

Chulik & Wood(1982)는 회전 거리를 정의할 뿐만 아니라 주어진 두 나무 사이의 회전 거리를 계산하는 계산의 복잡성을 물었다.임의의 두 나무 사이에 짧은 회전 시퀀스가 존재한다는 것은 회전 거리가 최대 k개 복잡도 등급 NP에 속하는지 여부를 테스트하는 것을 의미하지만, NP-완전인 것으로 알려져 있지 않으며 다항식 시간 내에 해결 가능한 것으로 알려져 있지 않다.그러나 Fordham의 알고리즘은 선형 시간으로 회전 거리를 계산하지만, (ab)c = a(bc)와 a(bc)d = a(bc)의 두 가지 종류의 회전만 허용합니다.Fordham 알고리즘은 노드를 7가지 유형으로 분류하는 데 의존하며, 룩업 테이블을 사용하여 한 유형의 노드를 다른 노드로 변환하는 데 필요한 회전 수를 구합니다.

두 트리 사이의 회전 거리는 폴리곤 삼각 측량의 동등한 뷰에서 하나의 삼각 측량에서 제거하고 다른 삼각 측량을 생성하기 위해 다른 대각선으로 대체해야 하는 대각선의 수에 따라 하한 경계를 지정할 수 있습니다.또한 문제를 삼각 측량 간에 공유되는 대각선을 따라 하위 문제로 분할한 다음 각 하위 문제에 취릭 & 우드(1982) 방법을 적용하여 이 숫자의 두 배로 상한을 설정할 수 있다.이 방법에서는 문제에 대한 근사 알고리즘을 [4]2의 근사 비율로 제공합니다.공유 대각선을 따라 하위 문제로 분할하는 유사한 접근방식은 [5][6]정확하게 회전 거리를 계산하기 위한 고정 파라미터 추적 가능한 알고리즘으로 이어진다.

파라미터화 없이 정확하게 회전 거리를 계산하는 복잡성은 해결되지 않은 상태로 남아 있으며, 현재 이 문제에 대해 알려진 최선의 알고리즘은 지수 [7]시간 내에 실행됩니다.그러나 Fordham 알고리즘의 존재는 회전 거리를 계산하기 위한 선형 시간 알고리즘이 존재함을 강하게 시사한다.

레퍼런스

  1. ^ a b c Čulík, Karel, II; Wood, Derick (1982), "A note on some tree similarity measures", Information Processing Letters, 15 (1): 39–42, doi:10.1016/0020-0190(82)90083-7, MR 0678031
  2. ^ a b c d e f Sleator, Daniel D.; Tarjan, Robert E.; Thurston, William P. (1988), "Rotation distance, triangulations, and hyperbolic geometry", Journal of the American Mathematical Society, 1 (3): 647–681, doi:10.1090/S0894-0347-1988-0928904-4, JSTOR 1990951, MR 0928904
  3. ^ a b Pournin, Lionel (2014), "The diameter of associahedra", Advances in Mathematics, 259: 13–42, doi:10.1016/j.aim.2014.02.035, MR 3197650
  4. ^ Cleary, Sean; St. John, Katherine (2010), "A linear-time approximation for rotation distance", Journal of Graph Algorithms and Applications, 14 (2): 385–390, doi:10.7155/jgaa.00212, MR 2740180
  5. ^ Cleary, Sean; St. John, Katherine (2009), "Rotation distance is fixed-parameter tractable", Information Processing Letters, 109 (16): 918–922, arXiv:0903.0197, doi:10.1016/j.ipl.2009.04.023, MR 2541971
  6. ^ Lucas, Joan M. (2010), "An improved kernel size for rotation distance in binary trees", Information Processing Letters, 110 (12–13): 481–484, doi:10.1016/j.ipl.2010.04.022, MR 2667389
  7. ^ Kanj, Iyad; Sedgwick, Eric; Xia, Ge (2017), "Computing the flip distance between triangulations", Discrete & Computational Geometry, 58 (2): 313–344, arXiv:1407.1525, doi:10.1007/s00454-017-9867-x, MR 3679938