이진 검색 트리의 지오메트리

컴퓨터 과학에서, 이진수 검색 트리의 온라인 알고리즘에 대한 동적 최적성 문제에 대한 한 접근법은 경계에 ^[1]두 점만 있는 직사각형을 피하기 위해 가능한 한 적은 수의 추가 점으로 평면 내의 집합을 증가시키는 관점에서 문제를 기하학적으로 재구성하는 것을 포함한다.

접속 순서와 경쟁률

일반적으로 온라인 바이너리 검색 트리 문제에는 고정 키 $\{1,2,...,n\}$ 세트 { $\{1,2,...,n\}$ , $\{1,2,...,n\}$ 2, $\{1,2,...,n\}$ . $\{1,2,...,n\}$ . , n $}({$ $displaystyle$ $\$ 1, $2, ..., n$ 에 정의된 검색 트리가 포함됩니다.액세스 시퀀스는 $x_{1},x_{2},$ 1, $x_{1},x_{2},$ $x_{1},x_{2},$ , $x_{1},x_{2},$ { $1}, x_{2},$ ..., $x_{1},x_{2},$ 각 $x_{i}$ i {\ $displaystyle x_{i$ 가 키에 속합니다.

바이너리 검색 트리(스플레이 트리 알고리즘이나 Iacono의 작업 세트 구조 등)를 유지하기 위한 특정 알고리즘에는 액세스 시퀀스의 각 키를 차례로 검색하기 위해 구조를 사용하는 데 걸리는 시간을 모델링하는 각 액세스 시퀀스에 대한 비용이 있습니다.검색 비용은 검색 트리 알고리즘에 바이너리 검색 트리로 가는 단일 포인터가 있다고 가정하여 모델링됩니다. 바이너리 검색 트리는 각 검색 시작 시 트리의 루트를 가리킵니다.알고리즘은 다음 조작의 임의의 시퀀스를 실행할 수 있습니다.

포인터를 왼쪽 자식으로 이동합니다.
포인터를 오른쪽 자식으로 이동합니다.
포인터를 부모로 이동합니다.
포인터와 그 부모에서 1회 트리를 회전합니다.

이 조작 시퀀스의 어느 시점에서는 키를 포함한 노드로 포인터를 이동하기 위해 검색이 필요하며, 검색 비용은 시퀀스에서 실행되는 조작의 수입니다.액세스 시퀀스X 위의 알고리즘A의 총비용_A(X)은 시퀀스 내의 각 연속된 키에 대한 검색 비용의 합계입니다.

경쟁 분석의 표준과 마찬가지로 알고리즘A의 경쟁률은 모든 액세스시퀀스에 걸쳐 A에 대한 비용 대비 알고리즘이 달성할 수 있는 최선의 비용 비율의 최대값으로 정의됩니다.

\displaystyle \rho _{A}=\sup _{X}{\frac {mathrm {cost}_{A}(X)}{\mathrm {opt}}(X)}}.}

동적 최적성 추측은 스플레이 트리가 일정한 경쟁률을 갖는다고 말하지만, 이는 입증되지 않은 상태로 남아 있다.이진 검색 트리의 기하학적 뷰는 (공통적으로) 일정한 경쟁률을 가질 수 있는 대체 알고리즘의 개발로 이어진 문제를 이해하는 다른 방법을 제공합니다.

기하학적 점 세트로 변환

온라인 바이너리 검색 트리 문제의 기하학적 뷰에서는 액세스 $x_{1},...,x_{m}$ 1, $x_{1},...,x_{m}$ . $x_{1},...,x_{m}$ . $x_{1},...,x_{m}$ , $m ($ 키 ${1,2,...,n}$ 1, ${1,2,...,n}$ , ${1,2,...,n}$ . , ${1,2,...,n}$ \ $display$ { $1$ , 2 $,$ . $n$ $x_{1},...,x_{m}$ )이 ( $x$ $style$ i ${(x_{i},i)}$ )의 ${(x_{i},i)}$ 세트로 매핑됩니다 $.$ $le$ {( $x_{i},i$ X축은 키 공간을 나타내고 Y축은 시간을 나타냅니다.이것에 터치 노드 세트가 추가됩니다.터치 노드란 다음을 의미합니다.트리의 노드에 대한 포인터가1개 있는 BST 액세스알고리즘에 대해 생각해 보겠습니다.특정 $x_{i}$ $x_{i}$ i $(\$ 에 대한 액세스 시작 시 이 포인터는 트리의 루트로 초기화됩니다.포인터가 노드로 이동하거나 노드로 초기화될 때마다 노드가 ^[2]터치되었다고 합니다.터치하는 각 항목에 대한 점을 그려 특정 입력 시퀀스에 대한 BST 알고리즘을 나타냅니다.

예를 들어, 4개의 노드에서 다음과 같은 BST가 제공된다고 가정합니다. 키 집합은 {1, 2, 3, 4}입니다.

액세스 시퀀스 3, 1, 4, 2만의 매핑.

이진 검색 트리 알고리즘의 기하학적 보기입니다.

3, 1, 4, 2를 액세스시퀀스로 하겠습니다

첫 번째 액세스에서는 노드 3만이 터치된다.
두 번째 액세스에서는 노드 3, 1이 터치된다.
세 번째 액세스 - 3과 4가 터치됩니다.
네 번째 액세스에서 3, 1, 그 다음 2를 누릅니다.

터치는 기하학적으로 표현됩니다.아이티 액세스 조작으로 아이템x 를 터치하면 점(x,i)이 플롯 됩니다.

수목적으로 만족한 점 세트

직사각형에 두 점을 걸칩니다.이 점 집합은 수목적으로 만족되지 않습니다.

이것은 수목적으로 만족하는 점 집합의 예입니다.

점 세트는 다음 특성이 유지되면 수목적으로 충족된다고 합니다. 동일한 수평선 또는 수직선상에 놓여 있지 않은 점 쌍에 대해 처음 두 점(경계 내부 또는 경계)에 걸쳐 있는 직사각형에 세 번째 점이 존재합니다.

정리

포인트 $(x_{i},i)$ $(x_{i},i)$ , $(x_{i},i)$ i $(x_{i},i)$ ) { $displaystyle$ ( x $_$ { $i$ , $i$ ) } 를 $(x_{i},i)$ 포함한 포인트세트는 입력 $x_{1},x_{2},...,x_{m}$ 1, $x_{1},x_{2},...,x_{m}$ 2, $x_{1},x_{2},...,x_{m}$ $x_{1},x_{2},...,x_{m}$ { $displaystyle x_{1}, x_{m$ 의 유효한 BST 에 대응하는 경우에만 수목적으로 만족합니다.

증명

먼저 유효한 BST 알고리즘에 대해 설정된 포인트가 수목적으로 충족되는지 확인합니다.포인트 $(x,i)$ $)$ { $displaystyle (x,i)}$ $(y,j)$ 및 $(x,i)$ ( $)$ { $displaystyle (y,j$ 을 검토합니다. $여기$ 서 x는 시간 $i$ 에, $y$ 는 $시간$ j에 터치합니다.대칭에 따라 x $x<y$ < $x<y$ \ $style$ x < $y$ $>$ 와 $i<j$ < $i<j$ \ $displaystyle$ i < $i<j$ j $i<j$ 라고 가정합니다.직사각형에 ( $(x,i)$ , $(x,i)$ ) { $displaystyle (x , i$ ) } { displaystyle $(x$ , i ) $(y,j)$ } 및 $(x,i)$ ( $(y,j)$ $,$ $\mathrm {LCA} _{t}(a,b)$ $(y,j)$ ) { $displaystyle$ { $LCA$ } { $displaystyle {$ LCA } $_$ { $t （ a$ , $\mathrm {LCA} _{t}(a,b)$ b $)$ $(x,i)$ 와 $\mathrm {LCA} _{t}(a,b)$ 같이 모서리가 있는 세 번째 점이 있음을 보여야 합니다. $\mathrm {LCA} _{t}(a,b)$ L C $\mathrm {LCA} _{t}(a,b)$ t t의 $\mathrm {LCA} _{t}(a,b)$ $앞부분$ 과 t의 가장 낮은 공통점을 $\mathrm {LCA} _{t}(a,b)$ .몇 가지 경우가 있습니다.

$\mathrm {LCA} _{i}(x,y)\neq x$ $\mathrm {LCA} _{i}(x,y)\neq x$ $\mathrm {LCA} _{i}(x,y)\neq x$ ( $\mathrm {LCA} _{i}(x,y)\neq x$ , $\mathrm {LCA} _{i}(x,y)\neq x$ ) $\mathrm {LCA} _{i}(x,y)\neq x$ x $\mathrm {LCA} _{i}(x,y)\neq x$ \ $displaystyle \mathrm$ { $LCA } _$ { $i}(x , y$ ) \ $neq$ x $\mathrm {LCA} _{i}(x,y)\neq x$ 인 $\mathrm {LCA} _{i}(x,y)\neq x$ $\mathrm {LCA} _{i}(x,y)$ $(\mathrm {LCA} _{i}(x,y),i)$ $\mathrm {LCA} _{i}(x,y)$ $(\mathrm {LCA} _{i}(x,y),i)$ ( $\mathrm {LCA} _{i}(x,y)$ , $(\mathrm {LCA} _{i}(x,y),i)$ ) 、 $(\mathrm {LCA} _{i}(x,y),i)$ ) $(\mathrm {LCA} _{i}(x,y),i)$ 、 \ $displaystyle$ ( \ $mathrm$ { $LCA } _$ { $i$ x , y ） $(\mathrm {LCA} _{i}(x,y),i)$ $i$ ）、、。
$\mathrm {LCA} _{j}(x,y)\neq y$ C $\mathrm {LCA} _{j}(x,y)\neq y$ j ( $\mathrm {LCA} _{j}(x,y)\neq y$ , $\mathrm {LCA} _{j}(x,y)\neq y$ ) $\mathrm {LCA} _{j}(x,y)\neq y$ y $\mathrm {LCA} _{j}(x,y)\neq y$ \ $displaystyle$ \ $mathrm$ { $(\mathrm {LCA} _{j}(x,y),j)$ $} _$ { $j （ x$ , $y$ ) \ $neq$ y $\mathrm {LCA} _{j}(x,y)\neq y$ 일 $\mathrm {LCA} _{j}(x,y)\neq y$ 점 $(\mathrm {LCA} _{j}(x,y),j)$ $(\mathrm {LCA} _{j}(x,y),j)$ A $(\mathrm {LCA} _{j}(x,y),j)$ ( $(\mathrm {LCA} _{j}(x,y),j)$ , $(\mathrm {LCA} _{j}(x,y),j)$ ) $(\mathrm {LCA} _{j}(x,y),j)$ , j ) \ displaystyle ( \ $mathrm$ { $LCA$ } _ { $x$ , y , $y$ } ) _ { $neq$ y })을 $(\mathrm {LCA} _{j}(x,y),j)$ $(\mathrm {LCA} _{j}(x,y),j)$ 할 수 있습니다.
위의 두 경우 모두 해당되지 않는 $경우$ x는 $시간$ i 직전 y의 $조상$ 이고 $y$ 는 $시간$ j 직전 x의 $조상$ 이어야 합니다.그 후 $어느$ $(i\leq k<j)$ 에서는 $(i\leq k<j)$ k ( i $(i\leq k<j)$ k < $(i\leq k<j)$ ) { $displaystyle ( i$ \ $leq$ k < $j$ ) $(i\leq k<j)$ }, $y$ 가 x $위$ 에서 회전하고 있어야 합니다.그러면 점 $(y,k)$ , $(y,k)$ $){$ $displaystyle ( y$ , $k$ )를 $(y,k)$ 사용할 수 있습니다.

다음으로 다른 방향을 제시합니다.수목적으로 만족하는 점 세트가 주어지면 해당 점 세트에 대응하는 유효한 BST를 구축할 수 있습니다.BST를 treap으로 정리하고 다음 터치 타임까지 힙 순서로 정리합니다.next-touch-time은 관계가 있으므로 고유하게 정의되어 있지 않지만 관계를 끊을 수 있는 방법이 있는 한 이는 문제가 되지 않습니다. $도달$ 했을 때 터치된 노드는 힙 순서 속성을 통해 맨 위에 연결된 하위 트리를 형성합니다.다음으로 이 서브트리에 새로운 넥스트 터치 시간을 할당하고 새로운 로컬트리로 재배열합니다.한 쌍의 $노드$ $x$ 와 y가 treap의 터치 부분과 터치되지 않은 부분의 경계를 가로지르는 경우 y가 x보다 $빨리$ 터치되는 $경우$ ( $(x,now)\to (y,next-touch(y))$ $(x,now)\to (y,next-touch(y))$ w ) $(x,now)\to (y,next-touch(y))$ ( $(x,now)\to (y,next-touch(y))$ , $(x,now)\to (y,next-touch(y))$ e $(x,now)\to (y,next-touch(y))$ $(x,now)\to (y,next-touch(y))$ - $(x,now)\to (y,next-touch(y))$ $(x,now)\to (y,next-touch(y))$ $(x,now)\to (y,next-touch(y))$ h ( $(x,now)\to (y,next-touch(y))$ y $(x,now)\to (y,next-touch(y))$ ) \ $display style$ ( $(x,now)\to (y,next-touch(y))$ x , now $)\ to$ ( y , $next$ - $touch$ ( $(x,now)\to (y,next-touch(y))$ y )\ )\ $to$ ( y , next - touch ( x , now ) ） ( because $(x,now)\to (y,next-touch(y))$ because because because because because because because because because because because because because 。.

결과

입력 $x_{1},x_{2},...,x_{m}$ 1, $x_{1},x_{2},...,x_{m}$ 2, $x_{1},x_{2},...,x_{m}$ $x_{1},x_{2},...,x_{m}$ {\ $displaystyle$ x_ ${1},x_{$ 2}, $x_{m}$ 에 $x_{1},x_{2},...,x_{m}$ 대해 최적의 BST 실행을 찾는 것은 (기하학적 표현으로 입력을 포함하는) 포인트의 최소 카디널리티 슈퍼셋을 찾는 것과 같습니다.일반적인 입력 포인트 세트(y좌표당 $1개$ 의 입력 포인트로 제한되지 않음)의 최소 카디널리티를 수목적으로 만족하는 슈퍼셋을 찾는 보다 일반적인 문제는 ^[1]NP-완전인 것으로 알려져 있다.

탐욕 알고리즘

다음 그리디 알고리즘은 수목적으로 만족할 수 있는 집합을 구성합니다.

y 좌표를 $늘려$ 수평선으로 점 세트를 스위프합니다.
$시간$ i에서 y $y=i$ {\ $displaystyle$ y $=i}$ 에 $y=i$ $y=i$ 포인트 수를 배치하여 y $y\geq i$ {\ $displaystyle$ y $\geq$ i}까지 $y\geq i$ 설정된 포인트를 만족시킵니다.이 최소 포인트 세트는 고유하게 정의됩니다. 한쪽 모서리에 ( $(x_{i},i)$ i , $(x_{i},i)$ ) { $displaystyle (x_{i$ , $i$ )}이 $(x_{i},i)$ $(x_{i},i)$ 가) 형성된 만족스럽지 못한 직사각형의 경우 y $y=i$ { $display$ y $=i$ 에 다른 모서리를 추가합니다.

알고리즘은 가법항 내에서 ^[3]최적인 것으로 추측되었다.

기타 결과

바이너리 검색 트리의 지오메트리는 바이너리 검색 트리 알고리즘이 동적으로 ^[4]최적인 경우 동적으로 최적인 알고리즘을 제공하기 위해 사용되었습니다.

「」를 참조해 주세요.

레퍼런스

^ ^a ^b Demaine, Erik D.; Harmon, Dion; Iacono, John; Kane, Daniel; Pătraşcu, Mihai (2009), "The geometry of binary search trees", In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York: 496–505, doi:10.1137/1.9781611973068.55, ISBN 978-0-89871-680-1
^ Demaine, Erik D.; Harmon, Dion; Iacono, John; Pătraşcu, Mihai (2007), "Dynamic optimality—almost", SIAM Journal on Computing, 37 (1): 240–251, CiteSeerX 10.1.1.99.4964, doi:10.1137/S0097539705447347, MR 2306291, S2CID 1480961
^ Fox, Kyle (August 15–17, 2011). Upper bounds for maximally greedy binary search trees (PDF). Algorithms and Data Structures: 12th International Symposium, WADS 2011. Lecture Notes in Computer Science. Vol. 6844. New York: Springer. pp. 411–422. arXiv:1102.4884. doi:10.1007/978-3-642-22300-6_35.
^ Iacono, John (2013). "In Pursuit of the Dynamic Optimality Conjecture". Space-Efficient Data Structures, Streams, and Algorithms. Lecture Notes in Computer Science. 8066: 236–250. arXiv:1306.0207. Bibcode:2013arXiv1306.0207I. doi:10.1007/978-3-642-40273-9_16. ISBN 978-3-642-40272-2. S2CID 14729858.

[DHIKP09-1] Demaine, Erik D.; Harmon, Dion; Iacono, John; Kane, Daniel; Pătraşcu, Mihai (2009), "The geometry of binary search trees", In Proceedings of the 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2009), New York: 496–505, doi:10.1137/1.9781611973068.55, ISBN 978-0-89871-680-1

[2] Demaine, Erik D.; Harmon, Dion; Iacono, John; Pătraşcu, Mihai (2007), "Dynamic optimality—almost", SIAM Journal on Computing, 37 (1): 240–251, CiteSeerX 10.1.1.99.4964, doi:10.1137/S0097539705447347, MR 2306291, S2CID 1480961

[3] Fox, Kyle (August 15–17, 2011). Upper bounds for maximally greedy binary search trees (PDF). Algorithms and Data Structures: 12th International Symposium, WADS 2011. Lecture Notes in Computer Science. Vol. 6844. New York: Springer. pp. 411–422. arXiv:1102.4884. doi:10.1007/978-3-642-22300-6_35.

[Iacono2013-4] Iacono, John (2013). "In Pursuit of the Dynamic Optimality Conjecture". Space-Efficient Data Structures, Streams, and Algorithms. Lecture Notes in Computer Science. 8066: 236–250. arXiv:1306.0207. Bibcode:2013arXiv1306.0207I. doi:10.1007/978-3-642-40273-9_16. ISBN 978-3-642-40272-2. S2CID 14729858.

[1]

[2]

[3]

[4]

Search

이진 검색 트리의 지오메트리

네임스페이스

더

목차

접속 순서와 경쟁률

기하학적 점 세트로 변환

수목적으로 만족한 점 세트

정리

증명

결과

탐욕 알고리즘

기타 결과

「」를 참조해 주세요.

레퍼런스

Search

이진 검색 트리의 지오메트리

접속 순서와 경쟁률

기하학적 점 세트로 변환

수목적으로 만족한 점 세트

정리

증명

결과

탐욕 알고리즘

기타 결과

「 」를 참조해 주세요.

레퍼런스

「」를 참조해 주세요.