최적의 이진 검색 트리

컴퓨터 과학에서 무게 균형 이진 트리라고도 하는 최적의 이진 검색 트리(Optimal BST)^[1]는 주어진 액세스 순서(또는 액세스 확률)에 대해 가능한 가장 적은 검색 시간(또는 예상 검색 시간)을 제공하는 이진 검색 트리다.최적 BST는 일반적으로 정적과 동적이라는 두 가지 유형으로 나뉜다.

정적 최적성 문제에서는 트리가 생성된 후에는 수정할 수 없다.이 경우 주어진 액세스 확률에 대해 가장 작은 예상 검색 시간을 제공하는 트리 노드의 특정 레이아웃이 존재한다.요소의 접근 확률에 대한 정보가 주어진 정적으로 최적의 트리를 구성하거나 근사하게 하기 위해 다양한 알고리즘이 존재한다.

동적 최적성 문제에서 트리는 일반적으로 나무 회전을 허용함으로써 언제든지 수정할 수 있다.트리는 루트부터 시작하는 커서를 가지고 있으며, 이 커서는 수정 작업을 수행하기 위해 이동하거나 사용할 수 있다.이 경우 커서가 대상 액세스 시퀀스의 모든 노드를 순서대로 방문하도록 하는 최소 비용 운영 순서가 존재한다.splay 트리는 아직 증명되지 않았지만 모든 경우에 동적으로 최적화된 트리에 비해 일정한 경쟁률을 가지고 있는 것으로 추측된다.

정적 최적성

정의

Knuth가 정의한 정적 최적성 문제에서,^[2] 우리는 순서가 정해진 원소 $집합$ 과 $2n+1$ + $2n+1$ 확률 $2n+1$ 집합이 $주어진다.$ We will denote the elements $a_{1}$ through $a_{n}$ and the probabilities $A_{1}$ through $A_{n}$ and $B_{0}$ through $B_{n}$ . $A_{i}$ is t $a_{i}$ $a_{i}$ ${\$ 또는 성공적인 검색)에 대해 검색이 수행될 확률.^[3]검색 don의 1≤ 들어 거야. 검색인 요소를 위해 해 준 나는{\displaystyle a_{나는}}의 n{\displaystyle 1\leq i<, n}, B나는}{\displaystyle B_{나는}이 있고 나는+1{\displaystyle a_{i+1}}(또는다가 못 찾)[3]B 0{\displaystyle B_{0}}&lt은 개연성이 높아졌다.대한 e $a_{1}$ ${\$ }보다 엄격히 작은 원소 및 $B_{n}$ ${\$ 은(는) $a_{n}$ ${\$ 보다 완전히 큰 원소에 대해 검색이 수행될 확률이다 $B_{n}$ $a_{n}$ 이 $2n+1$ + $2n+1$ $2n+1$ 확률에는 $2n+1$ 가능한 모든 검색이 포함되므로 1까지 추가하십시오.

정적 최적성 문제는 $2n+1$ + $2n+1$ $2n+1$ 확률로 $2n+1$ 볼 때 예상 검색 시간을 최소화하는 이진 검색 트리를 찾는 최적화 문제다. $n개$ 요소 집합에서 가능한 트리의 ${2n \choose n}{\frac {1}{n+1}}$ 수가 ( ${2n \choose n}{\frac {1}{n+1}}$ ) ${2n \choose n}{\frac {1}{n+1}}$ + 1 ${2n \choose n}{\frac {1}{n+1}}$ {\ $displaystyle$ { $2n \선택$ n $}{\frac {1}{n+$ 1 ${2n \choose n}{\frac {1}{n+1}}$ ^[2] $n$ 으로 지수화되므로, 보통 브루트 포스 검색은 실행 가능한 해결책이 아니다.

크누스의 동적 프로그래밍 알고리즘

1971년 크누스는 O(n²) 시간 내에 정적으로 최적 트리를 구성할 수 있는 비교적 간단한 동적 프로그래밍 알고리즘을 발표했다.^[2]크누스는 이 작품에서 에드가 길버트와 에드워드 F의 동적 프로그래밍 알고리즘을 확장·개선했다. 무어는 1958년에 소개되었다.^[4]길버트와 무어의 알고리즘과 실패한 검색의 확률,고 하는 것도 검토 최적 2진 탐색 나무 건설(최적의 알파벳 나무로 알려진 problem[5])의 특정 사례가를 위해 설계되었다 O(n3){O(n^{3})\displaystyle}시간 그리고 O(n2){O(n^{2})\displaystyle}공간을 요구했다. ${\textstyle \sum _{i=1}^{n}$ $A_{i}=0$ Knuth의 작업은 다음과 같은 통찰에 의존한 작업: 정적 최적성 문제는 최적의 하부 구조를 보여준다. 즉, 특정 트리가 주어진 확률 분포에 대해 정적으로 최적인 경우, 그 왼쪽과 오른쪽 하위 트리도 분포의 적절한 하위 집합(단조성 프로펠러라고 함)에 대해 정적으로 최적이어야 한다.뿌리의 움푹 들어간 곳).

이를 보려면 크누스가 나무의 "가중 경로 길이"라고 부르는 것을 고려하십시오.n개의 원소가 있는 트리의 $2n+1$ 경로 길이는 $2n+1$ + $2n+1$ $displaystyle 2n+1}$ 가능한 $2n+1$ 검색 경로의 길이를 모두 합한 값으로, 각각의 확률에 의해 가중된다.가중 경로 길이가 최소인 트리는 정의상 정적으로 최적이다.

그러나 가중치 있는 경로 길이에는 흥미로운 특성이 있다.E를 이항 트리의 가중 경로 길이, E는 $왼쪽 L$ 하위 트리의 가중 경로 길이, $E$ 는_R 오른쪽 하위 트리의 가중 경로 길이로 한다.또한 W를 트리에 있는 모든 확률의 합으로 한다.하위 트리 중 하나를 루트에 부착하면 각 요소(따라서 각 검색 경로)의 깊이가 하나씩 증가한다는 것을 관찰하십시오.또한 뿌리 자체의 깊이가 1이라는 것을 관찰하라.즉, 나무와 그 두 개의 하위 트리 사이의 가중 경로 길이의 차이는 정확하게 나무의 모든 확률의 합으로, 다음과 같은 재발을 초래한다.

E=E_{L}+E_{R}++W

이러한 재발은 자연스러운 동적 프로그래밍 솔루션으로 이어진다. $E_{ij}$ $E_{ij}$ ${\$ 를 $a$ 와_i a $사이$ 의_j 모든 값에 대해 정적 최적 검색 트리의 가중 경로 길이로 하고 $E_{ij}$ $W_{ij}$ j ${\$ 를 해당 트리의 총 중량으로 하고 $W_{ij}$ , $R_{ij}$ $R_{ij}$ {\ $displaysty R_{ij}}}$ 을 루트 색인으로 한다 $R_{ij}$ .알고리즘은 다음과 같은 공식을 사용하여 구축할 수 있다.

{\reasoned}E_{i,i-1}=W_{i,i-1}&=B_{i-1}\opername {for} 1\leq i\leq n+1\\\\W_{i,j}&=W_{i,j-1}+A_{j}+B_{j}\E_{i,j}&=\min _{i_{i,r-1}+E_{r+1,j}이상W_{i,j}\operatorname {for} 1\leq i\leq j\leq n\ended}

이 알고리즘의 순진한 구현에는 실제로 O(n³) 시간이 걸리지만 크누스의 논문에는 O(n²) 시간만 걸리는 수정된 알고리즘을 만드는 데 사용할 수 있는 몇 가지 추가 관찰이 포함되어 있다.

크누스는 동적 프로그래밍 알고리즘 외에도 최적의 바이너리 검색 트리를 거의 (대략적으로) 생산하기 위해 두 개의 휴리스틱스(또는 규칙)를 제안했다. $n$ $n$ 이 $n$ (가) 실질적으로 클 때 크누스의 알고리즘 시간과 공간 복잡성이 엄청나게 클 수 있기 때문에 거의 최적의 이진 검색 트리를 연구해야 했다.^[6]

크누스의 규칙은 다음과 같이 볼 수 있다.

규칙 I(Root-max):가장 자주 발생하는 이름을 트리의 루트에 배치한 다음 하위 트리에 비슷하게 진행하십시오.
규칙 II(이분법):왼쪽과 오른쪽 하위 트리의 총 중량을 최대한 균등하게 하기 위해 루트를 선택한 다음 하위 트리에서 비슷하게 진행한다.

크누스의 휴리스틱스는 $O(n\log n)$ $O(n\log n)$ $O(n\log n)$ ){\ $displaystyle$ O $(n\log n)}$ 시간과 $O(n\log n)$ $O(n)$ $O(n)$ 공간으로 $O(n)$ 거의 최적의 바이너리 검색 트리를 구현한다.최적의 크누스의 휴리스틱스로부터 얼마나 멀리 떨어져 있을 수 있는가에 대한 분석은 커트 멜혼이 추가로 제안했다.^[6]

멜혼 근사 알고리즘

크누스의 알고리즘에 의해 걸리는 O(n²) 시간은 짐승의 힘 검색에 필요한 지수 시간보다 실질적으로 더 나은 반면, 나무의 원소 수가 매우 클 때 실용적이기엔 아직 너무 느리다.

1975년에 커트 멜혼은 크누스의 규칙과 관련된 중요한 속성을 증명하는 논문을 발표했다.멜혼의 주요 결과는 크누스의 휴리스틱스(Rule II) 중 오직 하나만이 항상 거의 최적의 바이너리 검색 트리를 생산한다고 말한다.반면에, 루트-맥스 법칙은 종종 다음과 같은 간단한 논거를 바탕으로 매우 "나쁜" 탐색 나무로 이어질 수 있다.^[6]

내버려두다

${\textstyle {\begin}n=2^{k}-1,~~A_{i}=2^{-k}+\varepsilon _{i}~\varepsilon 이름 {with}~\{i=1}^{n}}\varepsilon _{i=2^{-k}}}}}end{liged}}}}}}}}}}}}}}}}.$

그리고

${\textstyle {\begin{aligned}\varepsilon _{1},\varepsilon _{2},\dots ,\varepsilon _{n}>0~~\operatorname {for} ~~1\leqq i\leqq n~~\operatorname {and} ~~B_{j}=0\operatorname {for} ~~0\leqq j\leqq n.\end{aligned}}}$

이전 정의를 기반으로 생성된 트리의 가중 $P$ 경로 길이 $P$ $P$ 을(를) 고려할 때 다음이 있다.

${\textstyle {\reason{aigned}P&=\sum _{i=1}^{n}A_{i}(a_{i}+1)+\sum _{j=1}^{n}B_{j}b_\&=\sum _{i=1}^{n}A_{i}i\\&\geq 2^{-k}\sum _{i=1}^{n}i=2^{-k}{\frac {n(n+1){2}{2}{2}}{2}}{2}}}}}\geq {\frac {n}{2}.\end{정렬}}}$

따라서 루트-맥스 규칙에 의한 결과 트리는 오른쪽(나무의 가장 깊은 층은 제외)에서만 자라는 트리가 될 것이며, 왼쪽에는 항상 터미널 노드가 있을 것이다.이 트리는 경로 길이가 ${\textstyle \Omega ({\frac {n}{2}})}$ ${\textstyle \Omega ({\frac {n}{2}})}$ ) ${\textstyle \Oomega({\frac{n}{2}})$ 로 제한되며, 균형 ${\textstyle \Omega ({\frac {n}{2}})}$ 잡힌 검색 트리( ${\textstyle O(2\log n)}$ ( ${\textstyle O(2\log n)}$ ${\textstyle O(2\log n)}$ ${\textstyle O(2\log n)}$ ) ${\textstyle O (2\log$ n $)$ 로 제한됨) ${\textstyle O(2\log n)}$ 와 비교할 때 동일한 주파수 분포에 대해 실질적으로 더 나쁜 성능을 발휘한다.^[6]

또 멜혼은 크누스의 작품을 개량하고 규칙 II를 사용하는 훨씬 간단한 알고리즘을 도입해 $O(n)$ (n $O(n)$ ) {\ $displaystyle O(n)}$ 시간 $O(n)$ 만에 정적 최적 트리의 성능을 근사하게 비교했다.^[6]알고리즘은 왼쪽과 오른쪽 하위 트리의 총 무게(확률에 의한) 균형을 가장 가깝게 맞추기 위해 나무의 뿌리를 선택함으로써 이분법 규칙의 같은 생각을 따른다.그리고 그 전략은 각 하위 트리에 반복적으로 적용된다.

이 전략이 좋은 근사치를 산출한다는 것은 어떤 경로를 따라가는 하위 트리의 무게가 기하학적으로 감소하는 수열에 매우 가까운 것을 형성한다는 것을 직관적으로 알 수 있다.실제로 이 전략은 가중 경로 길이가 최대인 트리를 생성한다.

2+(1-\log({\sqrt{5}-1)^{-1}H=2+{\frac {H}{1-\log({\sqrt{5}-1)}

여기서 H는 확률 분포의 엔트로피이다.최적의 이진 검색 트리는 다음의 가중 경로 길이보다 더 잘 수행될 수 없기 때문에

[\displaystyle(1/\log 3)H={\frac {H}{\log 3}}

이 근사치는 매우 가깝다.^[6]

후-터커-가르시아-와크스 알고리즘

모든 $A_{i}$ $A_{i}$ {\ $displaystyle A_{i}$ 값이 $A_{i}$ 0인 특별한 경우, 최적 트리는 시간 $O(n\log n)$ ( $O(n\log n)$ $O(n\log n)$ $){\displaystyle O(n\log n)}$ 에서 찾을 수 있다 $O(n\log n)$ 이것은 T. C. Hu와 Alan Tucker에 의해 1971년에 발표된 논문에서 처음 증명되었다.나중에 가시아와 와흐스의 단순화, 가시아-Wachs 알고리즘은 동일한 순서로 동일한 비교를 수행한다.알고리즘은 탐욕스러운 알고리즘을 이용해 잎마다 최적의 높이를 갖지만 순서가 뒤바뀐 트리를 만든 뒤 같은 높이로 또 다른 바이너리 검색 트리를 만드는 방식으로 작동한다.^[7]

동적 최적성

컴퓨터 과학의 미해결 문제:

splay 트리는 다른 바이너리 검색 트리 알고리즘만큼 잘 수행되나?

(컴퓨터 과학에서 더 풀리지 않은 문제)

정의

동적 최적성에 대한 몇 가지 다른 정의가 있는데, 이 모든 정의는 런타임 측면에서 사실상 일정한 요인 내에서와 동등하다.^[8]이 문제는 슬레이터와 타르잔에 의해 splay tree에 관한 그들의 논문에서 암묵적으로 소개되었지만, 데메인 등은 그것에 대해 매우 훌륭한 공식적 진술을 하고 있다.^[9]^[8]

동적 최적성 문제에서는 키 1, ..., n에 대한 일련의₁ 액세스 x, ..., x가_m 주어진다. 각 액세스에 대해 BST의 루트에 대한 포인터가 주어지며 포인터를 사용하여 다음 작업을 수행할 수 있다.

포인터를 현재 노드의 왼쪽 하위 노드로 이동하십시오.
포인터를 현재 노드의 오른쪽 하위 노드로 이동하십시오.
포인터를 현재 노드의 상위 노드로 이동하십시오.
현재 노드와 해당 상위 노드에서 단일 회전을 수행하십시오.

(접근 중 트리를 다시 배열하는 네 번째 조작의 존재로, 이것이 동적 광선성 문제가 된다.)

각 액세스에 대해, 우리의 BST 알고리즘은 포인터가 결국 목표값_i x를 포함하는 노드에 도달하는 한 위의 연산 시퀀스를 수행할 수 있다.일련의 접속을 수행하는 데 주어진 동적 BST 알고리즘이 걸리는 시간은 그 시퀀스 동안 수행된 그러한 동작의 총 수와 동일하다.모든 요소 집합에 대한 액세스 순서를 고려할 때, 이러한 액세스를 수행하는 데 필요한 최소 총 작업 수가 있다.우리는 이 최소치에 근접하고 싶다.

접속 순서가 정확히 어떤 것이 될 것인지 미리 파악하지 않고서는 이 "신의 알고리즘"을 구현하는 것은 불가능하지만, 우리는 OPT(X)를 접속 순서 X에 대해 수행할 작업 수로 정의할 수 있으며, 어떤 X에 대해서도 시간 O(OPT(X)로 X를 수행하면 알고리즘이 동적으로 최적이라고 말할 수 있다(즉, 일정한 c)을 가지고 있다).ompetitive ratio).^[8]

이 속성을 가지고 있는 것으로 추측되는 몇 가지 데이터 구조가 있지만 입증된 것은 없다.이 모델에 동적으로 최적화된 데이터 구조가 존재하는지는 개방적인 문제다.

스플레이 트리

splay 트리는 Daniel Sleator와 Robert Tarjan이 1985년 발명한 바이너리 검색 트리의 일종으로, 표준 검색 트리 연산은 $O(\log(n))$ $O(\log(n))$ $O(\log(n))$ ( $O(\log(n))$ ) ${\displaystyle O(\log$ (n $)}$ 상각 $O(\log(n))$ 시간으로 실행된다.^[10]필요한 의미에서는 동적으로 최적인 것으로 추측된다.즉, splay 트리는 시간 O(OPT(X))에서 충분히 긴 액세스 시퀀스 X를 수행하는 것으로 간주된다.^[9]

탱고나무

The tango tree is a data structure proposed in 2004 by Erik Demaine and others which has been proven to perform any sufficiently-long access sequence X in time $O(\log \log n\operatorname {OPT} (X))$ . While this is not dynamically optimal, the competitive ratio of ${\displayst$ $yle \log \log n}$ 은(는) n의 합리적인 값에 대해 여전히 매우 작다 $\log \log n$ .^[8]

기타 결과

2013년에 John Iacono는 바이너리 검색 트리의 지오메트리를 사용하여 바이너리 검색 트리 알고리즘이 동적으로 최적인 알고리즘을 제공하는 논문을 발표했다.^[11]노드는 2차원의 점으로 해석되며, 최적 접근 순서는 그러한 점들 중 수목적으로 만족하는 가장 작은 상위 집합이다.splay 트리와 탱고 트리와 달리 Iacono의 데이터 구조는 액세스 시퀀스 단계당 일정한 시간 내에 구현될 수 있는 것으로 알려져 있지 않기 때문에 동적으로 최적화된다고 해도 비정규적인 요소에 의한 다른 검색 트리 데이터 구조보다 여전히 느릴 수 있다.

인터리브 하한은 동적 최적성에 대한 점증상 하한이다.

참고 항목

메모들

^ Tremblay, Jean-Paul; Cheston, Grant A. (2001). Data Structures and Software Development in an object-oriented domain. Eiffel Edition/Prentice Hall. ISBN 978-0-13-787946-5.
^ ^a ^b ^c Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica, 1 (1): 14–25, doi:10.1007/BF00264289, S2CID 62777263
^ ^a ^b Nagaraj, S. V. (1997-11-30). "Optimal binary search trees". Theoretical Computer Science. 188 (1): 1–44. doi:10.1016/S0304-3975(96)00320-9. ISSN 0304-3975.
^ Gilbert, E. N.; Moore, E. F. (July 1959). "Variable-Length Binary Encodings". Bell System Technical Journal. 38 (4): 933–967. doi:10.1002/j.1538-7305.1959.tb01583.x.
^ Hu, T. C.; Tucker, A. C. (December 1971). "Optimal Computer Search Trees and Variable-Length Alphabetical Codes". SIAM Journal on Applied Mathematics. 21 (4): 514–532. doi:10.1137/0121057. ISSN 0036-1399.
^ ^a ^b ^c ^d ^e ^f Mehlhorn, Kurt (1975), "Nearly optimal binary search trees", Acta Informatica, 5 (4): 287–295, doi:10.1007/BF00264563, S2CID 17188103
^ 453–454페이지의 "역사 및 참고 문헌 목록Knuth, Donald E. (1998), "Algorithm G (Garsia–Wachs algorithm for optimum binary trees)", The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.), Addison–Wesley, pp. 451–453"을 참조하십시오.
^ ^a ^b ^c ^d Demaine, Erik D.; Harmon, Dion; Iacono, John; Patrascu, Mihai (2004), "Dynamic optimality—almost" (PDF), Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 484–490, CiteSeerX 10.1.1.99.4964, doi:10.1109/FOCS.2004.23, ISBN 978-0-7695-2228-9
^ ^a ^b Sleator, Daniel; Tarjan, Robert (1985), "Self-adjusting binary search trees", Journal of the ACM, 32 (3): 652–686, doi:10.1145/3828.3835, S2CID 1165848
^ Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald; Stein, Clifford (2009). Introduction to algorithms (PDF) (Third ed.). The MIT Press. p. 503. ISBN 978-0-262-03384-8. Retrieved 31 October 2017.
^ Iacono, John (2013), "In pursuit of the dynamic optimality conjecture", arXiv:1306.0207 [cs.DS]

[1] Tremblay, Jean-Paul; Cheston, Grant A. (2001). Data Structures and Software Development in an object-oriented domain. Eiffel Edition/Prentice Hall. ISBN 978-0-13-787946-5.

[Knuth1971-2] Knuth, Donald E. (1971), "Optimum binary search trees", Acta Informatica, 1 (1): 14–25, doi:10.1007/BF00264289, S2CID 62777263

[:0-3] Nagaraj, S. V. (1997-11-30). "Optimal binary search trees". Theoretical Computer Science. 188 (1): 1–44. doi:10.1016/S0304-3975(96)00320-9. ISSN 0304-3975.

[4] Gilbert, E. N.; Moore, E. F. (July 1959). "Variable-Length Binary Encodings". Bell System Technical Journal. 38 (4): 933–967. doi:10.1002/j.1538-7305.1959.tb01583.x.

[5] Hu, T. C.; Tucker, A. C. (December 1971). "Optimal Computer Search Trees and Variable-Length Alphabetical Codes". SIAM Journal on Applied Mathematics. 21 (4): 514–532. doi:10.1137/0121057. ISSN 0036-1399.

[Mehlhorm1975-6] ^ ^a ^b ^c ^d ^e ^f Mehlhorn, Kurt (1975), "Nearly optimal binary search trees", Acta Informatica, 5 (4): 287–295, doi:10.1007/BF00264563, S2CID 17188103

[7] 453–454페이지의 "역사 및 참고 문헌 목록Knuth, Donald E. (1998), "Algorithm G (Garsia–Wachs algorithm for optimum binary trees)", The Art of Computer Programming, Vol. 3: Sorting and Searching (2nd ed.), Addison–Wesley, pp. 451–453"을 참조하십시오.

[Demaine2004-8] Demaine, Erik D.; Harmon, Dion; Iacono, John; Patrascu, Mihai (2004), "Dynamic optimality—almost" (PDF), Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, pp. 484–490, CiteSeerX 10.1.1.99.4964, doi:10.1109/FOCS.2004.23, ISBN 978-0-7695-2228-9

[SplayTrees-9] Sleator, Daniel; Tarjan, Robert (1985), "Self-adjusting binary search trees", Journal of the ACM, 32 (3): 652–686, doi:10.1145/3828.3835, S2CID 1165848

[10] Cormen, Thomas H.; Leiserson, Charles E.; Rivest, Ronald; Stein, Clifford (2009). Introduction to algorithms (PDF) (Third ed.). The MIT Press. p. 503. ISBN 978-0-262-03384-8. Retrieved 31 October 2017.

[Iacono2013-11] Iacono, John (2013), "In pursuit of the dynamic optimality conjecture", arXiv:1306.0207 [cs.DS]

[1]

[2]

[3]

[4]

[6]

[7]

[8]

[9]

[10]

[11]

v t 트리 데이터 구조
나무 검색 (이중 세트/관련 배열)	2–3 2–3–4 AA (a,b) AVL B B+ B* B^x (최적) 이진 검색 춤 HTree 간격 오더통계 (좌편향) 빨강-검은색 희생양 스플레이 T 트레프 UB 무게균형
힙스	이진수 이항체 브로달 피보나치 좌익 페어링 스큐 판 엠드 보아스 약한
시도하다	씨트리 C-트리(압축 ADT) 해시 라딕스 접미사 3차 검색 X-fast Y-fast
공간 데이터 분할 트리	볼 BK BSP 카르테시안 힐베르트 R k-d(일반적으로 k-d) M 미터법 MVP 옥트리 PH 우선 순위 R 쿼드 R R+ R* 세그먼트 부사장 X
다른 나무들	커버 지수적 펜윅 손가락 프랙탈 트리 지수 퓨전 해시 캘린더 아이 디스턴스 케이애리 왼손잡이 우시블링 링크/컷 로그 구조 병합 머클 p q. 범위 SPQR 톱

v t 잘 알려진 데이터 구조
종류들	컬렉션 컨테이너
추상적	연관 배열 멀티맵 검색 데이터 구조 리스트 쌓다 큐 더블엔드 큐 우선 순위 대기열 이중 종료 우선 순위 대기열 세트 멀티셋 디스조인트
배열	비트 배열 원형완충기 동적 배열 해시 테이블 해시드 배열 트리 희소 행렬
연결됨	연관 리스트 링크 리스트 목록 건너뛰기 연결 해제 목록 XOR 연결 목록
나무들	B-트리 이진 검색 트리 AA 나무 AVL 트리 붉은-검은 나무 자기균형나무 스플레이 트리 힙 이진 힙 이항 힙 피보나치 더미 R-트리 R* 트리 R+ 트리 힐베르트 R 트리 트라이 해시 트리
그래프	이진결정도 방향 아세클릭 그래프 지시된 반복 단어 그래프
데이터 구조 목록

Search