랜덤 이진 트리

무작위 이진 트리(random binary tree)는 컴퓨터 과학과 확률 이론에서 이진 트리의 어떤 확률 분포에서 임의로 선택된 이진 트리입니다. 서로 다른 분포가 사용되어 이러한 트리에 대한 다른 속성이 생성되었습니다.

랜덤 이진 트리는 이진 검색 트리를 기반으로 데이터 구조의 평균-경우 복잡성을 분석하는 데 사용되었습니다. 이 애플리케이션의 경우 랜덤 순열에 따라 노드를 한 번에 하나씩 삽입하여 형성된 랜덤 트리를 사용하는 것이 일반적입니다.^[1] 트랩 및 관련 균형 이진 검색 트리는 업데이트 시퀀스가 랜덤하지 않은 경우에도 이 랜덤 구조를 유지하는 업데이트 작업을 사용합니다.

랜덤 이진 트리에 대한 다른 분포로는 모든 구별되는 트리가 동일할 가능성이 있는 균일한 이산 분포, 반복 분할에 의해 얻은 주어진 수의 노드에 대한 분포, 랜덤 데이터에 대한 이진 시도 및 래딕스 트리, 분기 프로세스에 의해 생성된 가변 크기의 트리가 있습니다.

반드시 이항이 아닌 랜덤 트리의 경우 랜덤 트리를 참조하십시오.

배경

이진 트리는 각 노드가 최대 2개의 자식(트리의 바로 아래 노드)을 가질 수 있는 루트 트리이며, 이러한 자식은 왼쪽 또는 오른쪽으로 지정됩니다. 대신 각 노드가 자식이 0인 외부 노드이거나 정확히 두 개의 자식이 있는 내부 노드인 확장 이진 트리를 고려하는 것이 편리합니다. 확장된 형태가 아닌 이진 트리는 모든 노드를 내부로 취급하고, 내부 노드의 누락된 자식 각각에 대해 외부 노드를 추가함으로써 확장된 이진 트리로 변환될 수 있습니다. 다른 방향으로, 적어도 하나의 내부 노드를 갖는 확장 이진 트리는 그것의 외부 노드들을 모두 제거함으로써 비 확장 이진 트리로 다시 변환될 수 있습니다. 이와 같이, 이 두 형태는 확장된 형태가 하나의 외부 노드로 구성된 트리를 허용한다는 점을 제외하고는 수학적 분석의 목적상 거의 전적으로 동등합니다. 컴퓨터 데이터 구조의 목적상, 첫 번째 형태의 외부 노드가 데이터 구조의 객체로 명시적으로 표현될 수 있기 때문에 두 형태는 다릅니다.^[2]

이진 검색 트리에서 내부 노드는 숫자 또는 기타 순서 값(키)으로 레이블이 지정되어 트리의 순서대로 키가 나열되도록 정렬됩니다. 외부 노드는 레이블이 지정되지 않은 상태로 남아 있습니다.^[3] 이진 트리는 레이블이 지정되지 않은 모든 노드를 사용하거나 정렬된 순서로 지정되지 않은 레이블을 사용하여 연구할 수도 있습니다. 예를 들어, 데카르트 트리 데이터 구조는 반드시 이진 검색 트리가 아닌 레이블이 지정된 이진 트리를 사용합니다.^[4]

랜덤 이진 트리는 이진 트리의 특정 확률 분포에서 추출한 랜덤 트리입니다. 많은 경우 이러한 확률 분포는 주어진 키 집합을 사용하여 정의되며 이진 검색 트리가 이러한 키를 가질 확률을 설명합니다. 그러나 반드시 이진 검색 트리를 생성할 필요는 없으며 반드시 고정된 수의 노드를 제공할 필요는 없으며 다른 배포도 가능합니다.^[5]

랜덤 순열로부터

100요소 랜덤 순열로부터 생성된 이진 트리

구별되는 순서 키들의 임의의 시퀀스에 대해, 이전에 삽입된 키들의 구조를 변경하지 않고, 각각의 키가 트리의 리프로서 순차적으로 삽입되는 이진 검색 트리를 형성할 수 있습니다. 각 삽입 위치는 이전 트리에서 이진 검색을 통해 찾을 수 있습니다. 주어진 키 집합에 대한 랜덤 순열 모델은 집합의 순열에서 시퀀스를 무작위로 선택하여 정의되며, 각 순열은 동일한 확률을 갖습니다.^[6]

예를 들어, 세 개의 키 1,3,2가 그 순서대로 이진 검색 트리에 삽입되면 숫자 1은 트리의 뿌리에 위치하고 숫자 3은 오른쪽 자식으로, 숫자 2는 숫자 3의 왼쪽 자식으로 배치됩니다. 키 1, 2, 3의 서로 다른 순열은 6개가 있지만 트리는 5개만 구성할 수 있습니다. 그 이유는 순열 2,1,3과 2,3,1이 동일한 트리를 형성하기 때문입니다. 따라서 이 트리는 생성될 확률이 ${\tfrac {2}{6}}={\tfrac {1}{3}}$ = ${\tfrac {2}{6}}={\tfrac {1}{3}}$ ${\displaystyle {\tfrac {2}{6$ }}={\ $tfrac {1}{3}}$ 인 반면, 다른 네 트리는 각각 ${\tfrac {1}{6}}$ ${\tfrac {1}{6}$ 입니다 ${\tfrac {1}{6}}$

노드의 예상 깊이

$n$ n개의 $n$ 개의 키 집합에 있는 $x$ 의 키 x $x$ 에 대해 랜덤 이진 검색 트리에서 루트에서 $({\displaystyle x})$ 까지의 경로 길이의 예상 값은 $2\log n+O(1)$ 2 $2\log n+O(1)$ ⁡ $2\log n+O(1)$ + O $(1$ ) ${\displaystyle 2\log$ n+O(1)}, 여기서 " $\log$ ${\displaystyle \log$ 는 자연 로그 함수를 나타내고 $O$ $O$ 는 큰 O 표기법을 도입합니다 $O$ . $기대$ 선형성에 의해 x ${\displaystyle$ x $}$ 의 예상 조상 수는 $y$ $y$ 가 $y$ x $x$ 의 조상일 확률의 $y$ 과 같습니다 $x$ $x$ $y$ $y$ 키는 y $y$ 가 간격 $[x,y]$ [ $[x,y]$ $[x,y]$ ${\displaystyle [x, y]$ {\displaystyle [x, y]}에서 삽입되는 첫 번째 키일 $y$ 때 $x$ $x$ $x$ 의 조상입니다 $y$ $[x,y]$ 간격의 각 키가 첫 번째일 가능성이 동일하기 때문에 간격의 길이에 반대되는 확률로 발생합니다. 따라서 정렬된 키 시퀀스에서 $x$ x ${\displaystyle$ x $}$ 에 인접한 키는 $x$ $x$ 의 조상일 ${\tfrac {1}{2}}$ 확률이 ${\tfrac {1}{2}}$ ${\$ 이고 $x$ 한 걸음 떨어진 키는 확률이 ${\tfrac {1}{3}}$ ${\$ 등입니다. 이 확률의 합은 정렬된 시퀀스에서 $x$ ${\displaystyle$ x $}$ 에서 양방향으로 확장되는 고조파 시리즈의 두 복사본을 형성하여 $2\log n+O(1)$ $2\log n+O(1)$ ⁡ n $2\log n+O(1)$ + O $2\log n+O(1)$ (1) ${\displaystyle 2\log$ n+O(1)}의 바운드를 제공합니다. 이 바운드는 지정된 키 중 하나인 $x$ 값 $x$ ${\displaystyle$ x $}$ 에 대한 예상 검색 경로 길이에도 적용됩니다.^[7]

가장 긴 길

랜덤 이진 검색 트리에서 가장 긴 루트 투 리프 경로는 예상 경로 길이보다 길지만 상수 요인에 의해서만 길어집니다. 노드가 $n$ $({\displaystyle$ n $}$ 개)인 트리의 경우 길이가 거의 확실합니다.

\displaystyle {\frac {1}{\beta }}\log n\approx 4.311\log n,

여기서 $\beta$ ${\displaystyle$ \beta }은 $0<\beta <1$ 는) $0<\beta <1$ < $0<\beta <1$ < $0<\beta <1$ 1 {\ $displaystyle 0$ <\beta < 1} $0<\beta <1$ 의 고유 번호로, 방정식을 만족합니다.

\displaystyle 2\beta e^{1-\beta }=1.

^[8]

예상잎수

랜덤 순열 모델에서 가장 작은 키와 가장 큰 키를 제외한 각 키는 트리의 리프일 확률이 ${\tfrac {1}{3}}$ ${\tfrac {1}{3}}$ ${\$ 입니다. 두 이웃의 뒤를 이어 삽입했을 때 잎사귀이기 때문인데, 이는 6개의 순열 중 2개와 두 이웃의 순열에 대해 발생하며, 모두 동등한 가능성을 가지고 있습니다. 비슷한 추론으로, 가장 작은 키와 가장 큰 키는 리프일 ${\tfrac {1}{2}}$ 확률이 ${\tfrac {1}{2}}$ ${\$ 입니다. 따라서 예상되는 잎 수는 $n\geq 2$ 확률의 합이며, $n$ ≥ 2 ${\displaystyle$ n\geq 2}의 경우 $(n+1)/3$ + 1 $)$ / 3 ${\displaystyle ($ n $(n+1)/3$ 1)/3}입니다.

스트롤러 번호

모든 트리의 Strahler 정점 수는 해당 정점 아래 부분 트리의 복잡성을 나타내는 척도입니다. 리프(외부 노드)는 Strahler 번호가 1번입니다. 다른 노드의 경우 Strahler 번호는 하위 노드의 Strahler 번호에서 재귀적으로 정의됩니다. 이진 트리에서 두 자녀가 서로 다른 Strahler 번호를 가지면 부모의 Strahler 번호가 두 자녀 번호 중 더 큽니다. 그러나 두 자녀가 동일한 스트랄러 번호를 가지고 있다면, 그들의 부모는 하나 더 큰 번호를 가지고 있습니다. 전체 트리의 Strahler 번호는 루트 노드의 번호입니다. $n$ 의 ${\displaystyle$ n $}$ 노드 무작위 이진 검색 트리에 대해 시뮬레이션을 통해 예상되는 Strahler $\log _{3}n+O(1)$ 는 $\log _{3}n+O(1)$ $\log _{3}n+O(1)$ ⁡ n $\log _{3}n+O(1)$ + O $\log _{3}n+O(1)$ (1) ${\displaystyle \log _{3$ }n $\log _{3}n+O(1)$ O(1)} 인 것으로 나타났습니다. 그러나 더 약한 $\log _{3}n+o(\log n)$ $\log _{3}n+o(\log n)$ ⁡ $n +$ no ( $log$ ⁡ $n) {\displaystyle \$ log _{3}n+o(\log n)}만 실제로 입증되었습니다.

트랩 및 랜덤 이진 검색 트리

이진 탐색 트리 데이터 구조의 적용에서는 임의의 순서로 삭제 없이 키가 삽입되는 경우가 드물어 임의의 이진 트리의 직접 적용이 제한됩니다. 그러나 알고리즘 설계자들은 임의로 키를 삽입한 것처럼 트리의 모양이 임의라는 속성을 보존하기 위해 임의의 삽입과 삭제가 가능한 데이터 구조를 고안했습니다.^[11]

주어진 키 집합에 숫자 우선 순위가 할당된 경우(값과 무관함), 이러한 우선 순위를 사용하여 숫자에 대한 데카르트 트리, 즉 키를 우선 순위 순서로 삽입한 결과로 생성되는 이진 검색 트리를 구성할 수 있습니다. 단위 구간에서 독립적인 난수가 될 우선순위를 선택하고, 노드의 삽입 또는 삭제 후 트리 회전을 사용하여 데카르트 트리 구조를 유지함으로써, 난수 이진 탐색 트리처럼 행동하는 데이터 구조를 유지할 수 있습니다. 이러한 데이터 구조를 트랩(trap) 또는 무작위 이진 검색 트리(randomized binary search tree)라고 합니다.^[11]

zip 트리 및 zip-zip 트리를 포함한 트랩의 변형은 트리를 분할하고 병합하는 "ziping" 작업으로 트리 회전을 대체하며, 이로 인해 키와 함께 생성 및 저장해야 하는 임의의 비트 수가 제한됩니다. 이러한 최적화의 결과는 여전히 무작위 구조를 가진 트리이지만 무작위 순열 모델과 정확히 일치하지 않는 트리입니다.^[12]

균등 랜덤 이진 트리

$n$ 의 ${\displaystyle$ $n$ $}$ 개의 $n$ 노드(또는 $n$ 의 ${\displaystyle$ n $}$ 개의 내부 $n$ 노드와 $n+1$ + $n+1$ 의 ${\displaystyle$ n $+1}$ 개의 외부 $n+1$ 노드를 포함하는 확장된 이진 트리의 수는 카탈루냐 숫자입니다.^[13] $n=1,2,3,\dots$ = $n=1,2,3,\dots$ $n=1,2,3,\dots$ 3 $n=1,2,3,\dots$ … ${\displaystyle$ n= $1, 2, 3,\$ dots }의 경우 이 트리 수는 다음과 같습니다.

1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...(OEIS의 시퀀스 A000108).

따라서, 이 트리들 중 하나가 임의로 균일하게 선택된다면, 그 확률은 카탈루냐 숫자의 역수입니다. 이 분포의 모형에서 생성된 트리를 랜덤 이진 카탈란 트리라고 부르기도 합니다.^[14] 로그가 $n$ 아닌 $n$ ${\displaystyle$ n $}$ 의 제곱근에 비례하는 깊이가 기대됩니다.^[15] 보다 정확하게는 이 $n$ 의 ${\displaystyle$ n $}-$ 노드 $n$ 트리에서 임의로 선택된 노드의 예상 깊이는

{\sqrt {\pi n}}-3+O\left({\frac {1}{\sqrt {n}}}\right)

-

{\sqrt {\pi n}}-3+O\left({\frac {1}{\sqrt {n}}}\right)

+

{\sqrt {\pi n}}-3+O\left({\frac {1}{\sqrt {n}}}\right)

(1n

)

{\displaystyle {\sqrt {\pin}}-3

+O

\left({\frac {1}{\sqrt {n}}}\

right

{\sqrt {\pi n}}-3+O\left({\frac {1}{\sqrt {n}}}\right)

균등 $n$ n ${\displaystyle n}-$ 노드 이진 트리의 예상 Strahler 수는 $\log _{4}n+O(1)$ $\log _{4}n+O(1)$ ⁡ $\log _{4}n+O(1)$ + O $\log _{4}n+O(1)$ (1) ${\displaystyle \log _{4$ }n $\log _{4}n+O(1)$ O(1)}로, 랜덤 이진 검색 트리의 예상 Strahler 수보다 낮습니다.

높이가 크기 때문에 이 등각 확률 랜덤 트리 모델은 일반적으로 이진 검색 트리에 사용되지 않습니다. 그러나 다음과 같은 다른 응용 프로그램이 있습니다.

컴파일러 설계에서 대수식의 구문 분석 트리를 모델링합니다.^[18] 여기서 트리의 내부 노드는 식으로 이진 연산을 나타내고 외부 노드는 식이 연산되는 변수 또는 상수를 나타냅니다. Strahler 수에 대한 경계는 식을 평가하는 데 필요한 레지스터의 수로 변환됩니다.^[19]
Strahler 번호가 개발된 원래 응용 프로그램인 하천 네트워크 모델링.^[20]
고정된 수의 종에 대해 가능한 진화 트리를 모델링합니다. 이 응용 프로그램에서는 확장된 이진 트리가 사용되며, 종은 외부 노드에 있습니다.^[21]

Jean-Luc Rémy의 알고리즘은 다음과 같은 과정을 통해 지정된 크기의 시간 선형의 균일한 무작위 이진 트리를 생성합니다. 단일 외부 노드로 구성된 트리로 시작합니다. 그런 다음 현재 트리가 목표 크기에 도달하지 않은 상태에서 노드 중 하나(내부 또는 외부)를 무작위로 균일하게 선택하는 것을 반복합니다. 선택한 노드를 새 내부 노드로 대체하고, 선택한 노드를 하위 노드(동일하게 왼쪽 또는 오른쪽) 중 하나로 설정하고, 새 외부 노드를 다른 하위 노드로 설정합니다. 목표 크기에 도달하면 중지합니다.^[22]

갈턴-왓슨 공정

Galton-Watson 프로세스는 각 노드의 자녀 수가 다른 노드와 독립적으로 무작위로 선택되는 트리에 대한 분포군을 설명합니다. 이진 트리의 경우 두 가지 버전의 Galton-Watson 프로세스가 사용되고 있으며, 오직 하나의 노드, 외부 루트 노드가 있는 확장 이진 트리가 허용되는지 여부만 다릅니다.

루트 노드가 외부일 수 있는 버전에서는 지정된 $확률$ p ${\displaystyle$ p $}$ 인 $p$ 내부 또는 $1-p$ 1 $1-p$ - $1-p$ $1-p$ 인 외부로 선택됩니다 $1-p$ 내부인 경우 두 자식은 동일한 프로세스에 의해 재귀적으로 생성된 트리입니다.
루트 노드가 내부에 있어야 하는 버전에서 왼쪽 및 오른쪽 하위 노드는 서로 독립적으로 $1-p$ 확률 $p$ ${\displaystyle$ p $}$ 인 $p$ 내부 또는 $1-p$ 1 $1-p$ - $1-p$ $1-p$ 인 외부로 결정됩니다. 내부에 있는 경우에는 동일한 과정에 의해 재귀적으로 생성되는 나무의 뿌리입니다.

이렇게 생성된 나무를 쌍성 갈턴-왓슨 나무라고 합니다. $p={\tfrac {1}{2}}$ = $p={\tfrac {1}{2}}$ ${\displaystyle$ p = {\ $tfrac {1}{2}}$ 인 특수한 경우에는 중요 이진 Galton-Watson 트리라고 합니다. 이 확률은 이진 Galton-Watson 프로세스의 위상 전이를 나타냅니다. $p\leq {\tfrac {1}{2}}$ $p\leq {\tfrac {1}{2}}$ $p\leq {\tfrac {1}{2}}$ ${\$ 의 경우 결과 트리는 $p\leq {\tfrac {1}{2}}$ 거의 확실하게 유한한 반면, $p>{\tfrac {1}{2}}$ > $p>{\tfrac {1}{2}}$ ${\$ 의 경우 양의 확률로 무한합니다 $p>{\tfrac {1}{2}}$ . 보다 정확하게는, $p$ 의 p $p$ 에 대하여 $p$ 트리가 유한하게 유지될 확률은

\displaystyle \min \left\{1,{\frac {1-p}{p}}\right\}

{

\displaystyle \min \left\{1,{\frac {1-p}{p}}\right\}

\displaystyle \min \left\{1,{\frac {1-p}{p}}\right\}

- p

\displaystyle \min \left\{1,{\frac {1-p}{p}}\right\}

{\

,

{\frac {1-p}{p}}\right

^[24]

동일한 트리를 생성하는 또 다른 방법은 앞면의 확률 $p$ $p$ ${\displaystyle$ p $}$ 와 $1-p$ 의 $1-p$ 확률 p $1-p$ - $1-p$ $1-p$ 인 일련의 코인 플립을 만드는 것입니다. 꼬리 수가 (외부 뿌리가 허용되는 모델의 경우) 머리 수를 초과하거나 (뿌리가 내부에 있어야 하는 경우) 머리 수에 1을 더한 값을 초과할 때까지 첫 번째 플립을 수행한 다음 이 코인 플립 순서를 사용하여 재귀 생성 프로세스에 의해 수행된 선택 사항을 깊이 우선 순위로 결정합니다.^[25]

내부 노드의 수는 이 코인 플립 시퀀스의 헤드의 수와 동일하기 때문에, 노드의 $n$ $n$ 가 n ${\displaystyle$ $n$ $}$ 인 모든 트리는 동일한 길이의 (고유의) 코인 플립 시퀀스에서 생성되며, $p$ ${\displaystyle$ p $}$ 에 관계없이 동일할 가능성이 높습니다 $p$ 즉, $p$ $p$ 의 선택은 이 프로세스에 의해 생성되는 트리 크기의 변화에 영향을 $p$ 미치지만, 주어진 크기에 대해 트리는 무작위로 균일하게 생성됩니다.^[26] $p$ 확률 $p={\tfrac {1}{2}}$ = $p={\tfrac {1}{2}}$ ${\displaystyle$ p={\ $tfrac {1}{2}}$ 보다 $p$ p $p$ 값의 경우 $p={\tfrac {1}{2}}$ p $p$ 값이 작으면 예상 크기가 작은 트리가 생성되고 $p$ $p$ 값이 클수록 예상 크기가 큰 트리가 생성됩니다. 임계 확률 $p={\tfrac {1}{2}}$ = $p={\tfrac {1}{2}}$ ${\displaystyle$ p = {\ $tfrac {1}{2}}$ 에서는 이 프로세스에 의해 생성된 트리의 예상 크기에 대한 유한한 제한이 없습니다. 보다 정확하게는, 임의의 $p$ ${\displaystyle$ $p$ $}$ 에 대해 $p$ 트리의 $i$ $깊이$ i ${\displaystyle$ i $}$ 의 예상 노드 수는 $(2p)^{i}$ ( $(2p)^{i}$ $(2p)^{i}$ ${\$ 이며 $(2p)^{i}$ 트리의 예상 크기는 각 깊이의 예상 노드 수를 합산하여 얻을 수 있습니다. $p<{\tfrac {1}{2}}$ < $p<{\tfrac {1}{2}}$ ${\$ 의 경우 기하급수를 $p<{\tfrac {1}{2}}$ 제공합니다.

\displaystyle 1+(2p)+(2p)^{2}+\cdots ={\frac {1}{1-2p}}

+

\displaystyle 1+(2p)+(2p)^{2}+\cdots ={\frac {1}{1-2p}}

(

\displaystyle 1+(2p)+(2p)^{2}+\cdots ={\frac {1}{1-2p}}

+

\displaystyle 1+(2p)+(2p)^{2}+\cdots ={\frac {1}{1-2p}}

(

\displaystyle 1+(2p)+(2p)^{2}+\cdots ={\frac {1}{1-2p}}

⋯

\displaystyle 1+(2p)+(2p)^{2}+\cdots ={\frac {1}{1-2p}}

\displaystyle 1+(2p)+(2p)^{2}+\cdots ={\frac {1}{1-2p}}

1

\displaystyle 1+(2p)+(2p)^{2}+\cdots ={\frac {1}{1-2p}}

-

2p {\displaystyle

\

displaystyle 1

+ (

2p)+

(2p)^{2}+\

c

=

{\frac

{1

\displaystyle 1+(2p)+(2p)^{2}+\cdots ={\frac {1}{1-2p}}

{1-2p}},

예상되는 트리 크기의 경우 $p={\tfrac {1}{2}}$ = $p={\tfrac {1}{2}}$ ${\displaystyle$ p={\ $tfrac {1}{2}}$ 의 경우 1 + 1 + 1 + 1 ⋯, 발산 급수를 제공합니다. $p={\tfrac {1}{2}}$ = $p={\tfrac {1}{2}}$ ${\displaystyle$ p={\ $tfrac {1}{2}}$ 의 경우 $,$ $n$ 의 $내부$ $노드$ 를 갖는 특정 트리는 $1/2^{2n+1}$ $1/2^{2n+1}$ + 1 $1/2^{2n+1}$ 의 확률로 생성되며 $1/2^{2n+1}$ 랜덤 트리가 이 크기를 가질 확률은 카탈루냐 숫자에 곱한 것입니다.

{\frac {C_{n}}{2^{2n+1}}}={\frac {1}{2n+1}}{\binom {2n+1}{n}}{\frac {1}{2^{2n+1}}}\approx {\frac {1}{{\sqrt {4\pi }}\,n^{3/2}}}\displaystyle

.^[28]

Galton-Watson 프로세스는 원래 인간 성의 확산과 멸종을 연구하기 위해 개발되었으며, 인간 또는 동물 개체군의 역학에 더 일반적으로 적용되었습니다. 주어진 트리 수준에서 내부 또는 외부 노드일 확률이 고정되지 않고 이전 수준의 노드 수에 따라 달라지는 모델로 일반화되었습니다.^[29] 임계 확률이 ${\tfrac {1}{2}}$ ${\$ 인 ${\tfrac {1}{2}}$ 이 프로세스의 버전은 임계 분기 프로세스로 알려진 사양화 모델로 연구되었습니다. 이 과정에서 각 종은 기하급수적으로 분포하는 수명을 가지며, 수명이 지남에 따라 수명과 동일한 속도로 어린 종을 생성합니다. 자녀가 생산되면 부모는 진화나무의 왼쪽 가지로 계속되고, 자녀는 오른쪽 가지가 됩니다.^[30] 그래프에서 최소 절단을 찾기 위한 Karger-Stein 알고리즘에서 재귀적 에지 수축 프로세스를 사용하여 중요한 Galton-Watson 트리의 또 다른 적용이 발생합니다. 이 알고리즘은 재귀적으로 두 번 호출하며, 각 호출은 정확한 솔루션 값을 보존할 ${\tfrac {1}{2}}$ 확률이 최소 ${\tfrac {1}{2}}$ ${\$ 입니다. 랜덤 트리는 올바른 재귀 호출의 하위 트리를 모델링합니다. 알고리즘은 올바른 재귀 호출의 이 랜덤 트리가 $적어도$ $2\log _{2}n$ $2\log _{2}n$ $2\log _{2}n$ ⁡ $2\log _{2}n$ ${\displaystyle 2\log$ _{2}n} 깊이의 분기를 가질 때마다 $n개$ 의 정점 $그래프$ 에서 성공하여 재귀의 기본 사례에 도달합니다. $O(n^{2}\log ^{3}n)$ 확률은 $O(n^{2}\log ^{3}n)$ ω(1 $\Omega (1/\log n)$ ⁡ n) ${\displaystyle \Omega$ 1 /\log n)} ${\displaystyle O($ n $^{$ 2}\log ^{3}n $O(n^{2}\log ^{3}n)$ $O(n^{2}\log ^{3}n)$ 에 로그 인자 중 하나를 생성합니다 $O(n^{2}\log ^{3}n)$

Devroye와 Robson은 각 외부 노드가 외부 노드로 처음 등장한 후 기하급수적으로 분산된 시간에 결국 두 개의 외부 자식이 있는 내부 노드로 대체되는 관련 연속 시간 랜덤 프로세스를 고려합니다. 나무의 외부 노드 수는 언제든지 모집단의 구성원이 일정한 비율로 출산하는 단순 출산 과정 또는 율 과정으로 모델링됩니다. 율 과정에서 한 명의 아이를 출산하는 것은 Devroye와 Robson의 모델에서 두 명의 아이로 대체되는 것에 해당합니다. 이 프로세스가 임의의 고정된 시간에 중지되면 결과는 임의 크기(중지 시간에 따라 다름)의 이진 트리로, 해당 크기에 대한 랜덤 순열 모델에 따라 분포됩니다. Devroye와 Robson은 이 모델을 알고리즘의 일부로 사용하여 랜덤 순열 모델에서 트리를 빠르게 생성하고, 정확한 구조가 아닌 각 깊이에서 노드 수로 설명합니다.^[32] 이 프로세스의 이산 변형은 단일 외부 노드로 구성된 트리에서 시작하여 무작위로 선택된 외부 노드를 두 개의 외부 자식이 있는 내부 노드로 반복적으로 대체합니다. 다시 말하지만, 이것이 고정된 시간(고정된 크기로)에 중단되면 결과 트리는 해당 크기에 대한 랜덤 순열 모델에 따라 분포됩니다.^[1]

이진 시도

이진 트리의 또 다른 형태인 이진 트리 또는 디지털 검색 트리에는 외부 노드 중 일부를 레이블로 지정하는 이진 번호 모음이 있습니다. 트리의 내부 노드는 둘 이상의 숫자가 공유하는 이진 표현의 접두사를 나타냅니다. 내부 노드의 왼쪽 및 오른쪽 자식은 해당 접두사를 각각 0 또는 1비트 더 확장하여 얻습니다. 이 확장명이 지정된 숫자 중 어느 것과도 일치하지 않거나 둘 중 하나만 일치하면 결과는 외부 노드이고, 그렇지 않으면 다른 내부 노드입니다. 예를 들어, 단위 간격에서 독립적으로 생성된 무작위 실수 집합에 대해 무작위 이진 시도가 연구되었습니다. 이러한 트리에는 일부 빈 외부 노드가 있을 수 있지만 무작위 이진 검색 트리보다 균형이 잘 맞는 경향이 있습니다. 단위 구간에서 $n개$ 의 균등 난수 $, 또는$ 보다 일반적으로 단위 구간에서 제곱 적분 가능한 확률 분포에 대해, 노드의 평균 깊이는 점근적으로 $\log _{2}n$ $\log _{2}n$ ⁡ n ${\displaystyle \log$ _{2}n}, 그리고 전체 트리의 평균 높이는 점근적으로 $2\log _{2}n$ $2\log _{2}n$ $2\log _{2}n$ ⁡ n ${\displaystyle 2\log$ _{2}n}입니다. 이러한 트리의 분석은 트리 기반 정렬 알고리즘의 계산 복잡성에 적용할 수 있습니다.^[33]

트리의 변형인 래딕스 트리 또는 압축 트리는 빈 외부 노드와 해당 부모 내부 노드를 제거합니다. 나머지 내부 노드는 임의로 선택된 숫자 중 적어도 하나에 의해 0 또는 1비트씩 가능한 두 확장이 모두 사용되는 접두사에 해당합니다. $n$ 의 $n$ 개의 $n$ 균등 분포 이진수에 대한 래딕스 트리의 경우 가장 짧은 리프-루트 경로의 길이는

\log _{2}n-\log _{2}\log n+o(\log \log n)

그리고 가장 긴 잎 뿌리 경로는 길이가 있습니다.

\log _{2}n+{\sqrt {2\log _{2}n}}+o ({\sqrt {\log n},

둘 ^[34]다 높은 확률로

랜덤 분할 트리

Luc Devroye와 Paul Kruszewski는 $n$ 의 ${\displaystyle$ n $}$ 개의 $n$ 노드로 랜덤 이진 트리를 구성하는 재귀적 프로세스를 설명합니다. 단위 간격 $(0,1)$ 1 $(0,1)$ ${\displaystyle(0, 1)}$ 에서 $x$ 실수 값 랜덤 변수 x $x$ 를 생성하고 $(0,1)$ 처음 $x$ $n$ $xn$ 개 $xn$ 노드(정수 노드로 반올림)를 왼쪽 하위 트리에, 다음 노드를 루트에, 나머지 노드를 오른쪽 하위 트리에 할당합니다. 그런 다음 왼쪽 및 오른쪽 하위 트리에서 동일한 프로세스를 사용하여 재귀적으로 계속됩니다. 구간에서 $x$ ${\displaystyle$ x $}$ 을(를) 무작위로 균일하게 선택하면 $x$ , 어떤 노드도 루트로 선택될 가능성이 동일하기 때문에 노드의 무작위 순열에 의해 생성된 무작위 이진 검색 트리와 결과가 동일합니다. 그러나 이 공식을 사용하면 다른 배포판을 대신 사용할 수 있습니다. 예를 들어, 균등 랜덤 이진 트리 모델에서 루트가 고정되면 두 부분 트리 각각도 균등 랜덤이어야 하므로, 균등 랜덤 모델은 $x$ $x$ 에 대해 다른 분포 선택 $n$ $n$ 에 따라 다름)에 의해 생성될 수도 있습니다 $x$ 이들이 보여주는 바와 같이, $x$ $x$ 에서 베타 분포를 선택하고 $x$ 각 가지를 그리기 위해 적절한 모양의 선택을 사용하여 이 과정에서 생성된 수학 트리를 사용하여 사실적으로 보이는 식물 트리를 만들 수 있습니다.^[35]

메모들

^ ^a ^b Drmota (2009), p. 19.
^ 크누스 (1997).
^ 크누스 (1973).
^ Vuillemin (1980).
^ ^a ^b Sedgewick & Flajolet (2013), 페이지 286.
^ 모린이 (2014).
^ 히바드(1962); 크누스(1973); 마흐무드(1992), 페이지 75.
^ Robson(1979); Pittel(1985); Devroye(1986); Mahmud(1992), pp. 91-99; Reed(2003).
^ 브라운 & 슈베르트 (1984).
^ 크루스제프스키 (1999).
^ ^a ^b Martínez & Roura (1998); Seidel & Aragon (1996); Morin (2014).
^ Tarjan, Levy & Timmel (2021); Gila, Goodrich & Tarjan (2023).
^ Drmota (2009), 페이지 26.
^ Sedgewick & Flajolet (2013), 페이지 287.
^ 크누스(2005), 페이지 15.
^ Sedgewick & Flajolet (2013), 페이지 288.
^ 데브로예 & 크루스제프스키 (1995).
^ 마흐무드(1992), 페이지 63.
^ Flajolet, Raoult & Vuillemin (1979).
^ Shreve (1966).
^ 알두스 (1996).
^ 레미(1985); Mäkinen & Siltaneva(2003); Knuth(2005), 페이지 16-17.
^ 버드, 웨이미어 & 윈 (2000).
^ 이는 Galton-Watson 프로세스에서 임계 및 소멸 확률에 대한 일반적인 정리의 특별한 경우이며, 이에 따라 소멸 확률은 공식 $g(r)=r$ = $g(r)=r$ ${\display g(r$ ) = $r}$ 의 가장 작은 양의 근이 됩니다 $g(r)=r$ 여기서 $g$ $g$ 는 자녀 수에 대한 분포의 확률 생성 함수이며, 여기서 $g(x)=(1-p)+px^{2}$ $g(x)=(1-p)+px^{2}$ = $g(x)=(1-p)+px^{2}$ ( $g(x)=(1-p)+px^{2}$ - $g(x)=(1-p)+px^{2}$ + $g(x)=(1-p)+px^{2}$ $g(x)=(1-p)+px^{2}$ 2 ${\displaystyle g(x$ ) = ( $1-p)$ + $g(x)=(1-p)+px^{2}$ px^{2}}를 참조하십시오. 예: Jagers(2011), 정리 2.1, p. 92 참조. Jagers는 페이지 97에서 이진 사례에 대한 이 근의 계산을 수행합니다.
^ 트리와 랜덤 워크(랜덤 코인 플립에 의해 생성됨) 간의 연결은 예를 참조하십시오. 섹션 6, "산책과 나무" pp. 483–486, Harris (1952).
^ Broutin, Devroye & Fraiman (2020). 보다 일반적으로, 특정 크기의 나무를 생산하는 것을 조건으로 하는 모든 Galton-Watson 프로세스는 중요한 Galton-Watson 프로세스와 동일한 확률 분포를 생성합니다: Kennedy(1975) 섹션 2 참조.
^ 트리의 각 레벨에서 예상되는 노드 수는 예를 참조하십시오. Athreya & Ney (1972), 섹션 I.A.2: Moments, p. 4.
^ 트리와 랜덤 워크 간의 동등성에 의해, 이는 단순 랜덤 워크에서 $2n+2$ + 2 $2n+2$ 단계 $2n+2$ 후에 처음으로 0으로 돌아올 확률과 같습니다. 예를 들어, 다음을 참조하십시오. Bertin(2021), 2.5.1 랜덤 워크의 기원으로 처음 돌아오는 시간의 통계, 페이지 70-72.
^ 재거즈 (2011).
^ 포포비치 (2004).
^ Karger & Stein (1996).
^ 데브로이 & 롭슨 (1995).
^ Devroye (1984).
^ 데브로이 (1992).
^ Devroye & Kruszewski (1996).

참고문헌

Aldous, David (1996), "Probability distributions on cladograms", in Aldous, David; Pemantle, Robin (eds.), Random Discrete Structures, The IMA Volumes in Mathematics and its Applications, vol. 76, Springer-Verlag, pp. 1–18, doi:10.1007/978-1-4612-0719-1_1
Athreya, Krishna B.; Ney, Peter E. (1972), Branching Processes, Berlin: Springer-Verlag, pp. 199–206, doi:10.1007/978-3-642-65371-1, ISBN 978-3-642-65371-1
Bertin, Eric (2021), Statistical Physics of Complex Systems: A Concise Introduction, Springer Series in Synergetics (3rd ed.), Springer International Publishing, doi:10.1007/978-3-030-79949-6, ISBN 9783030799496
Brown, Gerald G.; Shubert, Bruno O. (1984), "On random binary trees", Mathematics of Operations Research, 9: 43–65, doi:10.1287/moor.9.1.43
Broutin, Nicolas; Devroye, Luc; Fraiman, Nicolas (April 2020), "Recursive functions on conditional Galton–Watson trees" (PDF), Random Structures & Algorithms, Wiley, 57 (2): 304–316, doi:10.1002/rsa.20921
Burd, Gregory A.; Waymire, Edward C.; Winn, Ronald D. (February 2000), "A self-similar invariance of critical binary Galton–Watson trees", Bernoulli, 6 (1): 1–21, JSTOR 3318630
Devroye, Luc (1984), "A probabilistic analysis of the height of tries and of the complexity of triesort" (PDF), Acta Informatica, 21: 229–237, doi:10.1007/BF00264248
Devroye, Luc (1986), "A note on the height of binary search trees" (PDF), Journal of the ACM, 33 (3): 489–498, doi:10.1145/5925.5930
Devroye, Luc (January 1992), "A note on the probabilistic analysis of patricia trees" (PDF), Random Structures & Algorithms, 3 (2): 203–214, doi:10.1002/rsa.3240030209
Devroye, Luc; Kruszewski, Paul (1995), "A note on the Horton–Strahler number for random trees" (PDF), Information Processing Letters, 56 (2): 95–99, doi:10.1016/0020-0190(95)00114-R
Devroye, Luc; Kruszewski, Paul (1996), "The botanical beauty of random binary trees" (PDF), in Brandenburg, Franz J. (ed.), Graph Drawing: 3rd Int. Symp., GD'95, Passau, Germany, September 20–22, 1995, Lecture Notes in Computer Science, vol. 1027, Springer-Verlag, pp. 166–177, doi:10.1007/BFb0021801, ISBN 978-3-540-60723-6
Devroye, Luc; Robson, John Michael (December 1995), "On the generation of random binary aearch trees" (PDF), SIAM Journal on Computing, 24 (6): 1141–1156, doi:10.1137/s0097539792224954
Drmota, Michael (2009), Random Trees: An Interplay between Combinatorics and Probability, Springer-Verlag, doi:10.1007/978-3-211-75357-6, ISBN 978-3-211-75355-2
Flajolet, P.; Raoult, J. C.; Vuillemin, J. (1979), "The number of registers required for evaluating arithmetic expressions" (PDF), Theoretical Computer Science, 9 (1): 99–125, doi:10.1016/0304-3975(79)90009-4
Gila, Ofek; Goodrich, Michael T.; Tarjan, Robert E. (2023), "Zip-zip trees: making zip trees more balanced, biased, compact, or persistent", in Morin, Pat; Suri, Subhash (eds.), Algorithms and Data Structures – 18th International Symposium, WADS 2023, Montreal, QC, Canada, July 31 – August 2, 2023, Proceedings, Lecture Notes in Computer Science, vol. 14079, Springer, pp. 474–492, arXiv:2307.07660, doi:10.1007/978-3-031-38906-1_31
Harris, T. E. (1952), "First passage and recurrence distributions", Transactions of the American Mathematical Society, 73 (3): 471–486, doi:10.1090/s0002-9947-1952-0052057-2
Hibbard, Thomas N. (1962), "Some combinatorial properties of certain trees with applications to searching and sorting", Journal of the ACM, 9 (1): 13–28, doi:10.1145/321105.321108
Jagers, Peter (2011), "Extinction, persistence, and evolution", in Chalub, Fabio A. C. C.; Rodrigues, José Francisco (eds.), The Mathematics of Darwin's Legacy, Mathematics and Biosciences in Interaction, Basel: Birkhäuser, pp. 91–104, doi:10.1007/978-3-0348-0122-5_5, ISBN 9783034801225
Karger, David R.; Stein, Clifford (1996), "A new approach to the minimum cut problem" (PDF), Journal of the ACM, 43 (4): 601, doi:10.1145/234533.234534
Kennedy, Douglas P. (1975), "The Galton–Watson process conditioned on the total progeny", Journal of Applied Probability, 12: 800–806, doi:10.2307/3212730
Knuth, Donald E. (1973), "6.2.2 Binary Tree Searching", The Art of Computer Programming, Vol. III: Sorting and Searching, Addison-Wesley, pp. 422–451
Knuth, Donald E. (1997), "2.3.4.5 Path Length", The Art of Computer Programming, Vol. I: Seminumerical Algorithms (3rd ed.), Addison-Wesley, pp. 399–406
Knuth, Donald E. (2005), "Draft of Section 7.2.1.6: Generating All Trees", The Art of Computer Programming, vol. IV
Kruszewski, Paul (1999), "A note on the Horton–Strahler number for random binary search trees", Information Processing Letters, 69 (1): 47–51, doi:10.1016/S0020-0190(98)00192-6
Mäkinen, Erkki; Siltaneva, Jarmo (2003), "A note on Rémy's algorithm for generating random binary trees", Missouri Journal of Mathematical Sciences, 15 (2): 103–109, doi:10.35834/2003/1502103
Mahmoud, Hosam M. (1992), Evolution of Random Search Trees, John Wiley & Sons
Martínez, Conrado; Roura, Salvador (1998), "Randomized binary search trees", Journal of the ACM, 45 (2): 288–323, CiteSeerX 10.1.1.17.243, doi:10.1145/274787.274812
Morin, Pat (March 22, 2014), "Chapter 7: Random Binary Search Trees", Open Data Structures (in pseudocode) (PDF) (0.1Gβ ed.), pp. 145–164
Pittel, B. (1985), "Asymptotical growth of a class of random trees", Annals of Probability, 13 (2): 414–427, doi:10.1214/aop/1176993000
Popovic, Lea (November 2004), "Asymptotic genealogy of a critical branching process", Annals of Applied Probability, 14 (4), arXiv:math/0503577, doi:10.1214/105051604000000486
Reed, Bruce (2003), "The height of a random binary search tree", Journal of the ACM, 50 (3): 306–332, doi:10.1145/765568.765571
Rémy, Jean-Luc (1985), "Un procédé itératif de dénombrement d'arbres binaires et son application à leur génération aléatoire", RAIRO Informatique théorique (in French), 19: 179–195
Robson, J. M. (1979), "The height of binary search trees", Australian Computer Journal, 11: 151–153
Seidel, Raimund; Aragon, Cecilia R. (1996), "Randomized search trees", Algorithmica, 16 (4–5): 464–497, doi:10.1007/s004539900061
Sedgewick, Robert; Flajolet, Philippe (2013), "Chapter 6: Trees", An Introduction to the Analysis of Algorithms (2nd ed.), Addison-Wesley, ISBN 9780133373486
Shreve, Ronald L. (January 1966), "Statistical law of stream numbers", The Journal of Geology, 74 (1): 17–37, JSTOR 30075174
Tarjan, Robert E.; Levy, Caleb C.; Timmel, Stephen (2021), "Zip trees", ACM Transactions on Algorithms, 17 (4): 34:1–34:12, arXiv:1806.06726, doi:10.1145/3476830
Vuillemin, Jean (1980), "A unifying look at data structures", Communications of the ACM, 23 (4): 229–239, doi:10.1145/358841.358852

[FOOTNOTEDrmota200919-1] Drmota (2009), p. 19.

[FOOTNOTEKnuth1997-2] 크누스 (1997).

[FOOTNOTEKnuth1973-3] 크누스 (1973).

[FOOTNOTEVuillemin1980-4] Vuillemin (1980).

[FOOTNOTESedgewickFlajolet2013286-5] Sedgewick & Flajolet (2013), 페이지 286.

[FOOTNOTEMorin2014-6] 모린이 (2014).

[7] 히바드(1962); 크누스(1973); 마흐무드(1992), 페이지 75.

[8] Robson(1979); Pittel(1985); Devroye(1986); Mahmud(1992), pp. 91-99; Reed(2003).

[FOOTNOTEBrownShubert1984-9] 브라운 & 슈베르트 (1984).

[FOOTNOTEKruszewski1999-10] 크루스제프스키 (1999).

[treap-11] Martínez & Roura (1998); Seidel & Aragon (1996); Morin (2014).

[12] Tarjan, Levy & Timmel (2021); Gila, Goodrich & Tarjan (2023).

[FOOTNOTEDrmota200926-13] Drmota (2009), 페이지 26.

[FOOTNOTESedgewickFlajolet2013287-14] Sedgewick & Flajolet (2013), 페이지 287.

[FOOTNOTEKnuth200515-15] 크누스(2005), 페이지 15.

[FOOTNOTESedgewickFlajolet2013288-16] Sedgewick & Flajolet (2013), 페이지 288.

[FOOTNOTEDevroyeKruszewski1995-17] 데브로예 & 크루스제프스키 (1995).

[FOOTNOTEMahmoud199263-18] 마흐무드(1992), 페이지 63.

[FOOTNOTEFlajoletRaoultVuillemin1979-19] Flajolet, Raoult & Vuillemin (1979).

[FOOTNOTEShreve1966-20] Shreve (1966).

[FOOTNOTEAldous1996-21] 알두스 (1996).

[22] 레미(1985); Mäkinen & Siltaneva(2003); Knuth(2005), 페이지 16-17.

[FOOTNOTEBurdWaymireWinn2000-23] 버드, 웨이미어 & 윈 (2000).

[extinction-24] 이는 Galton-Watson 프로세스에서 임계 및 소멸 확률에 대한 일반적인 정리의 특별한 경우이며, 이에 따라 소멸 확률은 공식 $g(r)=r$ = $g(r)=r$ ${\display g(r$ ) = $r}$ 의 가장 작은 양의 근이 됩니다 $g(r)=r$ 여기서 $g$ $g$ 는 자녀 수에 대한 분포의 확률 생성 함수이며, 여기서 $g(x)=(1-p)+px^{2}$ $g(x)=(1-p)+px^{2}$ = $g(x)=(1-p)+px^{2}$ ( $g(x)=(1-p)+px^{2}$ - $g(x)=(1-p)+px^{2}$ + $g(x)=(1-p)+px^{2}$ $g(x)=(1-p)+px^{2}$ 2 ${\displaystyle g(x$ ) = ( $1-p)$ + $g(x)=(1-p)+px^{2}$ px^{2}}를 참조하십시오. 예: Jagers(2011), 정리 2.1, p. 92 참조. Jagers는 페이지 97에서 이진 사례에 대한 이 근의 계산을 수행합니다.

[25] 트리와 랜덤 워크(랜덤 코인 플립에 의해 생성됨) 간의 연결은 예를 참조하십시오. 섹션 6, "산책과 나무" pp. 483–486, Harris (1952).

[26] Broutin, Devroye & Fraiman (2020). 보다 일반적으로, 특정 크기의 나무를 생산하는 것을 조건으로 하는 모든 Galton-Watson 프로세스는 중요한 Galton-Watson 프로세스와 동일한 확률 분포를 생성합니다: Kennedy(1975) 섹션 2 참조.

[27] 트리의 각 레벨에서 예상되는 노드 수는 예를 참조하십시오. Athreya & Ney (1972), 섹션 I.A.2: Moments, p. 4.

[28] 트리와 랜덤 워크 간의 동등성에 의해, 이는 단순 랜덤 워크에서 $2n+2$ + 2 $2n+2$ 단계 $2n+2$ 후에 처음으로 0으로 돌아올 확률과 같습니다. 예를 들어, 다음을 참조하십시오. Bertin(2021), 2.5.1 랜덤 워크의 기원으로 처음 돌아오는 시간의 통계, 페이지 70-72.

[FOOTNOTEJagers2011-29] 재거즈 (2011).

[FOOTNOTEPopovic2004-30] 포포비치 (2004).

[FOOTNOTEKargerStein1996-31] Karger & Stein (1996).

[FOOTNOTEDevroyeRobson1995-32] 데브로이 & 롭슨 (1995).

[FOOTNOTEDevroye1984-33] Devroye (1984).

[FOOTNOTEDevroye1992-34] 데브로이 (1992).

[FOOTNOTEDevroyeKruszewski1996-35] Devroye & Kruszewski (1996).

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[11]

[12]

[13]

[14]

[15]

[18]

[19]

[20]

[21]

[22]

[24]

[25]

[26]

[28]

[29]

[30]

[32]

[33]

[34]

[35]

Search