이진 트리

크기 9와 높이 3의 라벨이 붙은 바이너리 트리. 값이 1인 루트 노드.위의 트리는 불균형하여 정렬되지 않았습니다.

컴퓨터 과학에서 바이너리 트리는 각 노드가 최대 2개의 자식(왼쪽 자식과 오른쪽 자식)을 갖는 트리 데이터 구조입니다.단순한 집합론 개념을 사용한 재귀적 정의는 (공백이 아닌) 이진 트리는 태플(L, S, R)이며, 여기서 L과 R은 이진 트리 또는 빈 집합이고, S는 ^[1]루트를 포함하는 싱글톤 집합입니다.일부 작성자는 이진 트리를 빈 집합으로 만들 수도 있습니다.^[2]

그래프 이론의 관점에서 볼 때, 여기서 정의한 이진(및 K-ary) 트리는 수목입니다.^[3]따라서 바이너시 트리는 분절수목이라고도^[3] 불리는데, 이는 현대 컴퓨터 과학 용어가 유행하기 이전의 매우 오래된 프로그래밍 ^[4]서적에서 나타난 용어입니다.이진 트리는 지시된 그래프가 아닌 무방향으로 해석할 수도 있습니다. 이 경우 이진 트리는 순서가 지정된 루트 ^[5]트리입니다.일부 저자는 이진 트리 대신 루트 이진 트리를 사용하여 트리가 루트라는 사실을 강조하지만 위에서 정의한 바와 같이 이진 트리는 항상 ^[6]루트입니다.이진 트리는 순서가 매겨진 K-ary 트리의 특수한 경우이며, 여기서 K는 2입니다.

수학에서 이진수라고 불리는 것은 저자에 따라 크게 다를 수 있다.컴퓨터 ^[7]공학에서 일반적으로 사용되는 정의를 사용하는 사람도 있지만, 정확히 두 아이를 가진 모든 잎이 아닌 것으로 정의하며 반드시 왼쪽/오른쪽이라고 정렬할 필요는 없습니다.^[8]

컴퓨팅에서 바이너리 트리는 두 가지 매우 다른 방법으로 사용됩니다.

첫째, 각 ^[9]노드와 관련된 값 또는 라벨을 기반으로 노드에 액세스하는 수단입니다.이렇게 라벨이 지정된 바이너리 트리는 바이너리 검색 트리 및 바이너리 힙을 구현하는 데 사용되며 효율적인 검색 및 정렬에 사용됩니다.비루트 노드를 왼쪽 또는 오른쪽 자식으로 지정하는 것은 이러한 애플리케이션 중 일부에서 특히 바이너리 ^[10]검색 트리에서 중요합니다.그러나 트리에 특정 노드를 배치하는 것은 개념 정보의 일부가 아닙니다.예를 들어 일반 바이너리 검색 트리에서 노드의 배치는 추가된 순서에 따라 거의 전적으로 달라지며 의미를 변경하지 않고 (예를 들어 밸런싱을 통해) 재배치할 수 있습니다.
둘째, 관련된 분기 구조를 가진 데이터의 표현이다.이러한 경우, 다른 노드의 왼쪽 또는 오른쪽 아래 또는 왼쪽 노드의 특정 배열은 정보의 일부입니다(즉, 의미를 변경하면 의미가 변경됩니다).일반적인 예는 Huffman 코딩 및 클래드 그래프에서 발생합니다.매일 문서를 장, 섹션, 단락 등으로 나누는 것은 이진 트리가 아닌 n-ary와 유사한 예입니다.

정의들

재귀적 정의

실제로 바이너리 트리를 정의하기 위해서는 자녀 중 한 명만 비어 있을 가능성을 고려해야 합니다.일부 교과서에서는 확장 이진 트리라고 불리는 아티팩트가 이러한 목적을 위해 필요합니다.따라서 확장 바이너리 트리는 다음과 같이 ^[11]재귀적으로 정의됩니다.

빈 집합은 확장된 이진 트리입니다.
T와₂ T가 확장 이진수 트리인 경우₁, T에₁ 왼쪽₂, T에 오른쪽에₂^{[clarification needed where did the 'r' go in the 'T₁ • T₂' symbol]} 연결된 루트 r을 추가하여 얻은 확장 이진수 트리를 T • T로 나타냅니다₁. 이러한 하위 트리가 비어 있지 않을 때 에지를 추가합니다.

이 구조를 상상하는 또 다른 방법(및 용어 이해)은 빈 집합 대신 다른 유형의 노드(일반 노드가 ^[12]원일 경우 사각 노드 등)를 고려하는 것입니다.

그래프 이론 개념 사용

바이너리 트리는 루트 트리이며, 모든 노드가 최대 2개의 하위 노드를 갖는 순서 트리(플레인 트리라고도 함)이기도 합니다.루트 트리는 자연스럽게 레벨의 개념(루트로부터의 거리)을 부여하기 때문에 모든 노드에 대해 하위의 개념은 하위 레벨에 연결된 노드로 정의될 수 있습니다.이러한 아이들의 순서(예: 평면에 그려짐)를 지정하면 왼쪽 ^[13]아이와 오른쪽 아이를 구별할 수 있다.그러나 이것은 여전히 왼쪽은 있지만 오른쪽은 아닌 노드와 오른쪽은 있지만 왼쪽은 없는 노드를 구분하지 못합니다.

필요한 구별은 먼저 에지를 분할함으로써 할 수 있습니다.즉, 이진 트리를 트리플트(V, E₁, E₂)로 정의합니다.여기서 (V₁, E₂ e E)는 루트 트리(등가적인 수목)이고₁ E₂ is E는 비어 있으며, 또한 모든 j ^[14]most { 1, 2 } 노드에 대해 최대 1개의_j 자식 노드가 있어야 합니다.수학 백과사전을 인용하여 "모든 노드에는 왼쪽 자식, 오른쪽 자식, 또는 둘 다 없습니다"라고 말하고 "모두 다른" 이진 ^[7]트리를 지정하면 됩니다.

바이너리 트리

트리 용어는 제대로 표준화되지 않았기 때문에 문헌에 따라 다릅니다.

루트 바이너리 트리는 루트노드를 가지며 각 노드에는 최대 2개의 서브노드가 있습니다.

풀 바이너리 트리

완벽한 4단계 이진 트리에 매핑할 수 있는 조상 차트입니다.

풀 바이너리 트리(적절한^[15] 바이너리 트리, 평면 트리, ^[16]^[17]엄밀한 바이너리 트리라고도 함)는 모든 노드에 0 또는 2의 자식이 있는 트리입니다.전체 이진 트리를 정의하는 또 다른 방법은 재귀 정의입니다.완전한 바이너리 트리는 ^[11]다음 중 하나입니다.
- 단일 정점
- 루트 노드가 2개의 서브트리를 가지며 둘 다 완전한 바이너리 트리입니다.
완벽한 이진 트리는 모든 내부 노드가 두 개의 하위 노드를 가지며 모든 잎이 동일한 깊이 또는 ^[18]수준을 갖는 이진 트리입니다.완벽한 이진 트리의 예는 한 사람의 (비근친적) 조상의 도표입니다. 각 사람은 정확히 두 명의 생물학적 부모(한 명의 어머니와 한 명의 아버지)를 가지고 있기 때문입니다.만약 조상이 항상 엄마와 아빠가 주어진 노드에 대해 같은 쪽에 표시된다면, 그들의 성은 왼쪽과 오른쪽의 자녀들의 유추로 볼 수 있고, 여기서 아이들은 알고리즘 용어로 이해된다.
완전한 바이너리 트리는 마지막을 제외한 모든 레벨이 완전히 채워지고 마지막 레벨의 모든 노드가 가능한 한 멀리 남겨지는 바이너리 트리입니다.마지막 레벨 ^[19]h에 1 ~2개의^h 노드를 포함할 수 있습니다.따라서 완전한 트리는 항상 완전하지만 완전한 트리는 반드시 완벽하지는 않습니다.다른 정의로는 가장 오른쪽 잎(아마도 모두)이 제거된 완벽한 트리가 있습니다.일부 저자는 위에서 정의한 완벽한 바이너리 트리를 대신 지칭하기 위해 complete라는 용어를 사용합니다.이 경우 이 트리를 거의 완전한 바이너리 트리 또는 거의 완전한 바이너리 ^[20]^[21]트리라고 부릅니다.완전한 ^[19]바이너리 트리는 어레이를 사용하여 효율적으로 나타낼 수 있습니다.

완전한 바이너리 트리(풀하지 않음)

무한 완전 바이너리 트리에서는 모든 노드에 두 개의 하위 항목이 있습니다(따라서 레벨 집합은 무한대로 계산됩니다).모든 노드의 집합은 셀 수 있을 정도로 무한하지만 루트로부터의 모든 무한 경로 집합은 셀 수 없으며 연속체의 카디널리티를 가집니다.이는 이러한 경로가 칸토어 집합의 점이나 (스턴-브로코트 트리의 예를 사용하여) 양의 비이성 수 집합에 대한 순서 보존 분사에 대응하기 때문이다.
밸런스 바이너리 트리는 각 노드의 좌우 서브트리의 높이가 ^[22]1 이하인 바이너리 트리 구조입니다.또한 다른 어떤 리프보다 루트에서 훨씬 멀리 떨어져 있지 않은 바이너리 트리를 고려할 수도 있습니다.(밸런싱 스킴이 다르면 '훨씬 더 멀리'^[23]에 대한 정의를 달리할 수 있습니다.)
퇴화(또는 병리학적) 트리는 각 부모 노드에 연관된 자식 ^[24]노드가 하나만 있는 경우입니다.즉, 트리가 연결된 목록 데이터 구조처럼 작동합니다.

이진 트리의 속성

풀 바이너리 트리의 $노드$ 수n(\ $displaystyle$ n $)$ 은 $n$ $2h+1$ 최소 $2^{h+1}-1$ + $2h+1$ $(\$ $displaystyle 2h+1}-$ 1 $(\displaystyle$ 2 $^{h+$ 1}- $1$ 입니다. 여기서 $h(\$ $displaystyle$ h $)$ 는 $h$ 트리의 높이입니다.루트 노드만으로 구성된 트리의 높이는 0입니다.
완전한 이진 트리의 $l=(n+1)/2$ $노드$ $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ l $l=(n+1)/2$ ( $l=(n+1)/2$ + $l=(n+1)/2$ ) / $2$ { $l=(n+1)/2$ { $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ $style$ l $=$ ( $n$ + 1 ) / 2 { display style l = ( n + $1$ ) / 2 { display $l=(n+1)/2$ style l $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ ( $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ + 1 ) / 2 $}$ = n $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ - $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ - $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ ） = $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ . $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ - l - l = ( ( ( ( ( ( (= $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ 1 $n-l=\sum _{k=0}^{\log _{2}(l)-1}2^{k}=2^{\log _{2}(l)}-1=l-1$ = $2)(l)}-1=l-1$
즉, l $(\displaystyle$ l $)$ 의 $l$ $전체$ 이진 트리는 $n=2l-1$ $n=2l-1$ $n=2l-1$ - $n=2l-1$ (\ $displaystyle$ n $=2l-1)$ 노드를 $n=2l-1$ 가집니다.
$h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ 잡힌 완전 이진 트리에서 h $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ 2 $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ ( $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ l ) $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ + 1 $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ 2 $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ ( $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ + $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ ) $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ + $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ $2$ ( $n$ + $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ ) $h=\lceil \log _{2}(l)\rceil +1=\lceil \log _{2}((n+1)/2)\rceil +1=\lceil \log _{2}(n+1)\rceil$ \ $display$ h = \ $lceil$ + $1$ （ $n ） _ log$ + 1 ( n )
완전 2진수 트리에서는 l $l=2^{h}$ $({$ l $=2^{h})$ 이므로 $l=2^{h}$ n $n=2^{h+1}-1$ $n=2^{h+1}-1$ $n=2^{h+1}-1$ - $({displaystyle$ n $=2^{h+1}-1$ 입니다.
n개의 노드의 바이너리 트리에서 null 링크(즉, 노드의 부재 자녀)의 수는 (n+1)입니다.
n개의 노드의 완전한 바이너리 트리의 내부 노드 수는 $\lfloor n/2\rfloor$ " $\lfloor n/2\rfloor$ $\lfloor n/2\rfloor$ $"$ ({ $displaystyle \lfloor$ n/2 $\rfloor$ 입니다.
n개의 리프 노드와₂ n개의 노드가 2인 이진₀ 트리의 경우₀ n = n₂ + ^[25]1입니다.

조합

조합론에서는 주어진 크기의 완전한 이진수 트리의 수를 세는 문제를 고려합니다.여기서 트리는 노드에 값이 부가되지 않고(이는 가능한 트리의 수에 쉽게 결정되는 계수를 곱할 뿐), 트리는 구조만으로 구별됩니다.단, 임의의 노드의 왼쪽과 오른쪽 아이는 구별됩니다(다른 트리의 경우, 그것들을 교환하면 t와 다른 트리가 생성됩니다).그는 오리지널이다.)트리의 크기는 내부 노드(자녀가 2개인 노드)의 수 n으로 간주됩니다.다른 노드는 리프 노드이며 n $+1$ 이 $있습니다$ .크기 n의 이러한 바이너리 트리의 수는 n개의 바이너리 연산자(내부 노드를 나타냄)로 구분된 n $+1$ 기호(잎을 나타냄)의 문자열을 완전히 괄호화하는 방법의 수와 동일하며, 각 연산자의 인수 하위식을 결정합니다.예를 들어 n = $3$ 의 $경우$ X $X*X*X*X$ X $X*X*X*X$ X $X*X*X*X$ X x X $X*X*X*X$ x X { $displaystyle$ X* $X*X$ 와 같은 문자열을 괄호 안에 넣어야 합니다. 이 문자열은 다음과 같은 다섯 가지 방법으로 가능합니다.

({displaystyle(X*X)*X,\qquad(X*X)*X,\qquad(X*X)*,\qquad X*(X*X),\qquad X*(X*X)*,\qquad X*(X*)*)*,\qquad X*(X*)*.}

바이너리 트리에 대한 대응은 명확해야 합니다.또한 다중 괄호(이미 괄호로 둘러싸인 식 주위 또는 완전한 식 주위)의 추가는 허용되지 않습니다(또는 적어도 새로운 가능성을 생성하는 것으로 간주되지 않습니다).

크기가 0(단일 잎으로 구성됨)인 고유한 이진 트리가 있으며, 다른 이진 트리는 왼쪽과 오른쪽의 자식 쌍으로 특징지어집니다. 이 쌍이 각각 크기 i와 j를 가질 경우 풀 $트리$ 의 $크기$ 는i + $j$ + 1입니다.따라서 크기 n의 이진 트리의 $C_{n}$ $C_{0}=1$ $(\$ $style$ $C_{$ n $C_{n}$ })은 C $C_{0}=1$ 1(\ $style$ C_ $C_{0}=1$ $\textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}$ }=1 $},$ C $\textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}$ $\textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}$ $\textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}$ i $=$ $\textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}$ n - $\textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}$ $\textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}$ - $\textstyle C_{n}=\sum _{i=0}^{n-1}C_{i}C_{n-1-i}$ - $(\$ }^{ $1})$ 의 재귀적 $C_{0}=1$ 입니다. $C_{n}$ Cn $(\$ 은 $C_{n}$ 색인 n의 카탈로니아 번호입니다.

위의 괄호 안의 문자열은 Dyck 언어의 길이 2n의 단어 집합과 혼동해서는 안 됩니다.이 단어 집합은 적절한 균형을 이루도록 괄호로만 구성되어 있습니다.이러한 문자열의 수는 동일한 재귀적 기술을 충족한다(길이가 2n인 각 다이크 워드는 첫 번째 '('와 일치하는 ')'로 둘러싸인 다이크 서브 워드와 그 닫힘 괄호 뒤에 남은 다이크 서브 워드에 의해 결정되며, 길이 2i와 2j는i + $j$ + 1= $n$ 을 $만족$ 한다). 따라서 이 숫자 역시 카탈로니아 수이다. $(\$ 길이 6의 Dick 단어도 5개 $C_{n}$ .

()()(), ()(()), (())(), (()()), ((()))

이 Dick 단어들은 같은 방식으로 이진 트리에 대응하지 않습니다.대신, 이 두 단어는 반복적으로 정의된 다음 분사에 의해 관련됩니다. 빈 문자열과 동일한 Dyck 단어는 크기가 0인 이진 트리에 해당하며 잎은 1개뿐입니다.기타 Dick 워드는 ( $w_{2}$ $w_{1}$ 1 \ $displaystyle w$ _ { $w_{1}$ $w_{2}$ } ) w $w_{2}$ 2 \ $displaystyle w$ _ { $}$ 、 $w_{2}$ $w_{1}$ \ $displaystyle$ w _ { $}$ 、 $w_{2}$ any and2 \ displaystyle $w_{2}$ are $w_{2}$ wherees and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and and $w_{1}$ 다음 단어 $w_{1}$ 1 $(\$ 1 $w_{1}$ }) 및 $w_{2}$ 2 $(\$ 가 $w_{2}$ 루트의 왼쪽 및 오른쪽 자식인 이진 트리에 대응하도록 하여 분사를 정의합니다.

또, 바이젝티브 대응은 다음과 같이 정의할 수 있습니다.Dick 워드를 여분의 괄호 쌍으로 묶어서 결과를 리스프 리스트 식(빈 리스트()으로 해석할 수 있습니다.그 후, 적절한 리스트의 도트 페어식은 완전한 괄호로 둘러싸인 식(심볼로서 NIL, ope로서 「」)입니다.rator)는 대응하는 바이너리 트리(실제로 적절한 목록의 내부 표현)를 기술합니다.

이진수를 기호와 괄호의 문자열로 표현하는 능력은 이진수가 싱글톤 집합의 자유 마그마 원소를 나타낼 수 있다는 것을 암시합니다.

이진 트리 저장 방법

바이너리 트리는 프로그래밍 언어 프리미티브에서 여러 가지 방법으로 구성할 수 있습니다.

노드와 참조

레코드와 참조가 있는 언어에서 바이너리 트리는 일반적으로 왼쪽 자녀와 오른쪽 자녀에 대한 데이터와 참조를 포함하는 트리 노드 구조를 가지고 있습니다.또한 고유한 부모에 대한 참조가 포함될 수 있습니다.노드에 자녀 수가 2명 미만인 경우 자녀 포인터의 일부를 특수한 늘 값 또는 특별한 센티넬 노드로 설정할 수 있습니다.

이 바이너리 트리를 저장하는 방법은 포인터가 절반 이상 null(또는 sentinel을 가리킴)이기 때문에 상당한 비트의 메모리를 낭비합니다.더 보수적인 표현은 스레드 바이너리 ^[26]트리입니다.

ML과 같은 태그 부착 결합 언어에서 트리 노드는 종종 두 가지 유형의 노드 태그 부착 결합입니다. 하나는 3 태플의 데이터, 왼쪽 자식 및 오른쪽 자식 노드이고 다른 하나는 "리프" 노드입니다. 이 노드는 데이터를 포함하지 않으며 포인터가 있는 언어의 null 값과 매우 유사한 기능을 합니다.예를 들어 OCaml(ML 방언)의 다음 코드 행은 각 ^[27]노드에 문자를 저장하는 이진 트리를 정의합니다.

유형 chr_tree = 빈   노드 의 차 * chr_tree * chr_tree

어레이

또한 이진 트리는 배열에 암묵적인 데이터 구조로서 폭 우선 순서로 저장될 수 있으며, 트리가 완전한 이진 트리일 경우 이 방법은 공간을 낭비하지 않습니다.이 콤팩트한 배열에서는 노드에 인덱스 i가 있는 경우 노드의 자식은 $2i+1$ 2 $2i+1$ + $1(왼쪽 아이용$ ) $2i+1$ 및 $2i+2$ i + $2($ 아이용)에 있고 부모 노드(있는 경우)는 인덱스 $\left\lfloor {\frac {i-1}{2}}\right\rfloor$ $\left\lfloor {\frac {i-1}{2}}\right\rfloor$ - $\left\lfloor {\frac {i-1}{2}}\right\rfloor$ ${\$ \ $display style$ \ $left$ floor { $frci$ \ $right }$ 에 있습니다.e root에는 인덱스0이 있습니다).아니면,1-indexed에 구현은 아이들은 2나는{2i\displaystyle}에서 발견되고 나는 2및 1{2i+1\displaystyle}과 및 부모 ⌊에 나는/2⌋{\displaystyle \lfloor i/2\rfloor}더 컴팩트한 저장과 더 나은 지방에서 참고의 .[28]이 메서드는 급여, 특히 중에 드러난 간단합니다. 트래버설을 재정렬합니다.그러나^{[citation needed]} n개의 노드가 있는 깊이 h의 트리는 2 - n에 비례하는^h 공간을^{[citation needed]} 낭비한다.

이 저장 방법은 이진 ^{[citation needed]}힙에 자주 사용됩니다.

인코딩

간결한 부호화

간결한 데이터 구조는 정보 이론상 하한을 통해 확립된 최소 가능한 공간에 가까운 구조를 말합니다.n개\ $style$ $\mathrm {C} _{n}$ n노드의 $n$ $다른$ 바이너리 트리 수는 C $\mathrm {C} _{n}$ \ $displaystyle \mathrm$ { $C}_{$ n $\mathrm {C} _{n}$ , $n$ 는n개 \ $displaystyle$ n의 $n$ 카탈로니아 번호입니다(같은 구조의 트리를 동일하다고 가정합니다). $large$ n(\ $displaystyle$ n $n$ 의 경우 $4^{n}$ 약 $4n$ (\ $displaystyle 4^{n$ 입니다.따라서 이를 인코딩하려면 $\log _{2}4^{n}=2n$ 2 $\log _{2}4^{n}=2n$ $\log _{2}4^{n}=2n$ $=$ $(\displaystyle \log$ _ ${2$ } 4 $^{n$ }= $2n}$ 비트 $\log _{2}4^{n}=2n$ $\log _{2}4^{n}=2n$ 이 필요합니다.따라서 간결한 이진 트리는 2n + $2n+o(n)$ ( $2n+o(n)$ n $2n+o(n)$ ) $2n+o(n)$ { $displaystyle 2n$ + $o$ ( n ) $2n+o(n)$ }비트를 $2n+o(n)$ $2n+o(n)$ 합니다.

이 한계를 충족하는 간단한 표현 중 하나는 트리 노드를 사전 순서로 방문하여 내부 노드의 경우 "1"을, ^[29]리프 노드의 경우 "0"을 출력하는 것입니다.트리에 데이터가 포함되어 있는 경우 데이터를 사전 순서로 연속 배열에 동시에 저장할 수 있습니다.이 함수는 다음을 수행합니다.

함수 인코딩간결한(노드 n, 비트 문자열 구조, 어레이 데이터) { n = 0이면 구조에 0을 추가합니다. 그렇지 않으면 구조에 1을 추가하고, 데이터에 데이터를 추가하고, 인코딩합니다.간결(n. left, 구조, 데이터);부호화간결(오른쪽, 구조, 데이터); }

문자열 구조는 마지막에 $2n+1$ $2n+1$ $(\displaystyle 2n+1)$ 밖에 $2n+1$ 없습니다. $n$ 서 n $(\displaystyle$ n $)$ 은 $n$ (내부) 노드의 수입니다.길이를 저장할 필요도 없습니다.정보가 손실되지 않음을 나타내려면 다음과 같이 출력을 원래 트리로 변환할 수 있습니다.

함수 DecodeSuccinct(비트 문자열 구조, 어레이 데이터) { 구조의 첫 번째 비트를 제거하고 b에 넣은 다음, b = 1번째 요소를 제거하고 n.data n.left = DecodeSuccinct(구조, 데이터) n.right = DecodeSuccinct(구조, 데이터) nreturning nil}을 반환합니다.

보다 정교한 간결한 표현은 나무를 콤팩트하게 저장할 수 있을 뿐만 아니라 나무가 간결한 형태를 유지하고 있을 때 트리에 대한 유용한 작업도 가능하게 합니다.

일반 트리를 이진 트리로 인코딩

일반 순서 트리와 이진 트리 사이에는 일대일 매핑이 있으며, 특히 Lisp는 일반 순서 트리를 이진 트리로 표현하기 위해 사용합니다.일반 순서 트리를 이진 트리로 변환하려면 일반 트리를 왼쪽-오른쪽-시블링 방식으로만 표현하면 됩니다.이 표현의 결과는 다른 관점에서 보면 자동으로 이진 트리가 됩니다.순서 트리의 각 노드 N은 바이너리 트리 내의 노드 N'에 대응하고, N'의 왼쪽 자녀는 N의 첫 번째 자녀에 대응하는 노드, N'의 오른쪽 자녀는 N의 다음 형제, 즉 N의 부모 자녀 중 다음 자녀에 대응하는 노드이다.일반 순서 트리의 이 바이너리 트리 표현은 왼쪽 자녀 오른쪽 시블링 바이너리 트리(LCRS 트리, 이중 체인 트리, 효자 체인이라고도 함)라고도 합니다.

이를 생각할 수 있는 한 가지 방법은 각 노드의 자녀가 링크된 목록에 있으며 오른쪽 필드와 함께 연결되어 있으며 노드에는 왼쪽 필드를 통해 이 목록의 시작 또는 선두에 대한 포인터만 있다는 것입니다.

예를 들어 왼쪽 트리에서 A에는 6개의 하위 항목 {B,C,D,E,F,G}이 있습니다.오른쪽의 이진 트리로 변환할 수 있습니다.

바이너리 트리는 원래 트리가 옆으로 기울어져 있는 것으로 생각할 수 있으며, 검은색 왼쪽 가장자리는 첫째 아이를 나타내고 파란색 오른쪽 가장자리는 다음 형제자매를 나타냅니다.왼쪽의 나무 잎은 리스프로 다음과 같이 쓰여 있습니다.

((N O) I J) C D (P) (Q) F (M)

오른쪽의 바이너리 트리로 메모리에 구현되며 왼쪽 자식의 노드에는 문자가 없습니다.

공통 조작

트리 회전은 자가 밸런싱 바이너리 트리에 대한 매우 일반적인 내부 작업입니다.

바이너리 트리에 대해 다양한 작업을 수행할 수 있습니다.일부는 변환 연산이고 다른 일부는 트리에 대한 유용한 정보를 반환합니다.

삽입

노드를 다른 두 노드 사이의 이진 트리에 삽입하거나 리프 노드 뒤에 추가할 수 있습니다.바이너리 트리에서는 삽입된 노드가 누구의 아이로 지정됩니다.

리프 노드

리프 노드 A 뒤에 새 노드를 추가하기 위해 A는 새 노드를 하위 노드 중 하나로 할당하고 새 노드는 노드 A를 상위 노드 중 하나로 할당합니다.

내부 노드

이진 트리에 노드를 삽입하는 프로세스

내부 노드에서의 삽입은 리프 노드에서의 삽입보다 약간 복잡합니다.내부 노드가 노드 A이고 노드 B가 A의 자식이라고 가정합니다(삽입이 오른쪽 자식을 삽입하는 경우 B는 A의 오른쪽 자식이고 왼쪽 자식 삽입도 마찬가지입니다).A는 하위 노드를 새 노드에 할당하고 새 노드는 상위 노드를 A에 할당합니다.그런 다음 새 노드가 하위 노드를 B에 할당하고 B가 상위 노드를 새 노드로 할당합니다.

삭제

삭제는 노드가 트리에서 제거되는 프로세스입니다.이진 트리의 ^[30]특정 노드만 명확하게 제거할 수 있습니다.

하위 항목이 0개 또는 1개 있는 노드

이진 트리에서 내부 노드를 삭제하는 프로세스

삭제하는 노드가 노드A라고 합니다.A에 하위 항목이 없는 경우 A 부모의 하위 항목을 null로 설정하여 삭제합니다.A에 한 명의 자녀가 있는 경우 A 자녀의 부모를 A의 부모로 설정하고 A 부모의 자식을 A의 자녀로 설정합니다.

2자녀 노드

바이너리 트리에서 두 개의 자녀가 있는 노드는 ^[30]명확하게 삭제할 수 없습니다.단, 특정 바이너리 트리(바이너리 검색 트리 포함)에서는 트리 구조의 재배열과 함께 이러한 노드를 삭제할 수 있습니다.

트래버설

루트의 왼쪽 및 오른쪽 서브트리에 있는 각 노드를 재귀적으로 방문함으로써 프리오더, 순서순 및 포스트오더 트래버설은 트리 내의 각 노드를 방문합니다.

깊이 우선 순위

깊이 우선 순서는 항상 루트노드에서 가능한 한 멀리 있는 노드를 방문하려고 하지만 이미 방문한 노드의 자녀일 필요가 있다는 주의사항이 있습니다.그래프의 깊이 우선 검색과 달리 트리는 사이클을 포함할 수 없기 때문에 방문한 모든 노드를 기억할 필요가 없습니다.예약판매는 특별한 경우입니다.자세한 내용은 깊이 우선 검색을 참조하십시오.

폭 우선 순위

깊이 우선 순서는 폭 우선 순서와 대조됩니다.폭 우선 순서는 항상 아직 방문하지 않은 루트에 가장 가까운 노드의 방문을 시도합니다.자세한 내용은 폭 우선 검색을 참조하십시오.레벨 순서 트래버설이라고도 합니다.

완전한 바이너리 트리에서 노드의 폭 지수(i - (2^d - 1))를 루트에서 트래버설 명령으로 사용할 수 있습니다.왼쪽에서 오른쪽으로 비트 단위로 읽습니다.여기서 d는 루트로부터의 노드 거리(d = "log₂(i+1)")이며 문제의 노드는 루트 자체(d > 0)가 아닙니다.폭 인덱스가 비트 d - 1에서 마스킹되면 비트 값은0과 1은 각각 왼쪽 또는 오른쪽으로 스텝하는 것을 의미합니다.이 프로세스는 더 이상 존재하지 않을 때까지 오른쪽으로 다음 비트를 연속적으로 체크함으로써 계속됩니다.맨 오른쪽 비트는 원하는 노드의 부모에서 노드 자체로의 최종 통과를 나타냅니다.이 방법으로 완전한 바이너리 트리를 반복하는 것과 형제 노드에 대한 포인터를 갖는 것 사이에는 시간 공간의 균형이 있습니다.

「」를 참조해 주세요.

레퍼런스

인용문

^ Rowan Garnier; John Taylor (2009). Discrete Mathematics:Proofs, Structures and Applications, Third Edition. CRC Press. p. 620. ISBN 978-1-4398-1280-8.
^ Steven S Skiena (2009). The Algorithm Design Manual. Springer Science & Business Media. p. 77. ISBN 978-1-84800-070-4.
^ ^a ^b Knuth (1997). The Art Of Computer Programming, Volume 1, 3/E. Pearson Education. p. 363. ISBN 0-201-89683-4.
^ Iván Flores (1971). Computer programming system/360. Prentice-Hall. p. 39.
^ Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. p. 749. ISBN 978-0-07-338309-5.
^ David R. Mazur (2010). Combinatorics: A Guided Tour. Mathematical Association of America. p. 246. ISBN 978-0-88385-762-5.
^ ^a ^b "Binary tree", Encyclopedia of Mathematics, EMS Press, 2001 [1994] 로도 인쇄되어 있다.
^ L.R. Foulds (1992). Graph Theory Applications. Springer Science & Business Media. p. 32. ISBN 978-0-387-97599-3.
^ David Makinson (2009). Sets, Logic and Maths for Computing. Springer Science & Business Media. p. 199. ISBN 978-1-84628-845-6.
^ Jonathan L. Gross (2007). Combinatorial Methods with Computer Applications. CRC Press. p. 248. ISBN 978-1-58488-743-0.
^ ^a ^b Kenneth Rosen (2011). Discrete Mathematics and Its Applications 7th edition. McGraw-Hill Science. pp. 352–353. ISBN 978-0-07-338309-5.
^ Te Chiang Hu; Man-tak Shing (2002). Combinatorial Algorithms. Courier Dover Publications. p. 162. ISBN 978-0-486-41962-6.
^ Lih-Hsing Hsu; Cheng-Kuan Lin (2008). Graph Theory and Interconnection Networks. CRC Press. p. 66. ISBN 978-1-4200-4482-9.
^ J. Flum; M. Grohe (2006). Parameterized Complexity Theory. Springer. p. 245. ISBN 978-3-540-29953-0.
^ Tamassia, Michael T. Goodrich, Roberto (2011). Algorithm design : foundations, analysis, and Internet examples (2 ed.). New Delhi: Wiley-India. p. 76. ISBN 978-81-265-0986-7.
^ "full binary tree". NIST.
^ 리처드 스탠리, Enumative Combinatorics, 제2권, 페이지 36
^ "perfect binary tree". NIST.
^ ^a ^b "complete binary tree". NIST.
^ "almost complete binary tree". Archived from the original on 2016-03-04. Retrieved 2015-12-11.
^ "nearly complete binary tree" (PDF).
^ 애런 M.테넨바움 등C, 프렌티스 홀, 1990 ISBN 0-13-19746-7을 이용한 데이터 구조
^ Paul E. Black(ed.), 알고리즘 및 데이터 구조 사전의 데이터 구조 항목. 미국 국립 표준 기술 연구소 2004년 12월 15일 온라인 버전 2010년 12월 21일 Wayback Machine Accessed 2010-12-19에서 보관.
^ Parmar, Anand K. (2020-01-22). "Different Types of Binary Tree with colourful illustrations". Medium. Retrieved 2020-01-24.
^ Mehta, Dinesh; Sartaj Sahni (2004). Handbook of Data Structures and Applications. Chapman and Hall. ISBN 1-58488-435-5.
^ D. Samanta (2004). Classic Data Structures. PHI Learning Pvt. Ltd. pp. 264–265. ISBN 978-81-203-1874-8.
^ Michael L. Scott (2009). Programming Language Pragmatics (3rd ed.). Morgan Kaufmann. p. 347. ISBN 978-0-08-092299-7.
^ Introduction to algorithms. Cormen, Thomas H., Cormen, Thomas H. (2nd ed.). Cambridge, Mass.: MIT Press. 2001. p. 128. ISBN 0-262-03293-7. OCLC 46792720.{{cite book}}: CS1 유지보수: 기타 (링크)
^ Demaine, Erik. "6.897: Advanced Data Structures Spring 2003 Lecture 12" (PDF). MIT CSAIL. Archived from the original (PDF) on 24 November 2005. Retrieved 14 April 2022.
^ ^a ^b Dung X. Nguyen (2003). "Binary Tree Structure". rice.edu. Retrieved December 28, 2010.

참고 문헌

도널드 크누트.The Art of Computer Programming vol 1. 기초 알고리즘, 제3판애디슨 웨슬리, 1997년ISBN 0-201-89683-4.섹션 2.3, 특히 서브섹션 2.3.1–2.3.2 (페이지 318–348)

외부 링크

[GarnierTaylor2009-1] Rowan Garnier; John Taylor (2009). Discrete Mathematics:Proofs, Structures and Applications, Third Edition. CRC Press. p. 620. ISBN 978-1-4398-1280-8.

[Skiena2009-2] Steven S Skiena (2009). The Algorithm Design Manual. Springer Science & Business Media. p. 77. ISBN 978-1-84800-070-4.

[Knuth1997-3] Knuth (1997). The Art Of Computer Programming, Volume 1, 3/E. Pearson Education. p. 363. ISBN 0-201-89683-4.

[Flores1971-4] Iván Flores (1971). Computer programming system/360. Prentice-Hall. p. 39.

[5] Kenneth Rosen (2011). Discrete Mathematics and Its Applications, 7th edition. McGraw-Hill Science. p. 749. ISBN 978-0-07-338309-5.

[Mazur2010-6] David R. Mazur (2010). Combinatorics: A Guided Tour. Mathematical Association of America. p. 246. ISBN 978-0-88385-762-5.

[oem-7] "Binary tree", Encyclopedia of Mathematics, EMS Press, 2001 [1994] 로도 인쇄되어 있다.

[Foulds1992-8] L.R. Foulds (1992). Graph Theory Applications. Springer Science & Business Media. p. 32. ISBN 978-0-387-97599-3.

[Makinson2009b-9] David Makinson (2009). Sets, Logic and Maths for Computing. Springer Science & Business Media. p. 199. ISBN 978-1-84628-845-6.

[Gross2007-10] Jonathan L. Gross (2007). Combinatorial Methods with Computer Applications. CRC Press. p. 248. ISBN 978-1-58488-743-0.

[Rosen2011-11] Kenneth Rosen (2011). Discrete Mathematics and Its Applications 7th edition. McGraw-Hill Science. pp. 352–353. ISBN 978-0-07-338309-5.

[HuShing2002-12] Te Chiang Hu; Man-tak Shing (2002). Combinatorial Algorithms. Courier Dover Publications. p. 162. ISBN 978-0-486-41962-6.

[HsuLin2008-13] Lih-Hsing Hsu; Cheng-Kuan Lin (2008). Graph Theory and Interconnection Networks. CRC Press. p. 66. ISBN 978-1-4200-4482-9.

[FlumGrohe2006-14] J. Flum; M. Grohe (2006). Parameterized Complexity Theory. Springer. p. 245. ISBN 978-3-540-29953-0.

[15] Tamassia, Michael T. Goodrich, Roberto (2011). Algorithm design : foundations, analysis, and Internet examples (2 ed.). New Delhi: Wiley-India. p. 76. ISBN 978-81-265-0986-7.

[16] "full binary tree". NIST.

[17] 리처드 스탠리, Enumative Combinatorics, 제2권, 페이지 36

[18] "perfect binary tree". NIST.

[complete_binary_tree-19] "complete binary tree". NIST.

[almost_complete_binary_tree-20] "almost complete binary tree". Archived from the original on 2016-03-04. Retrieved 2015-12-11.

[nearly_complete_binary_tree-21] "nearly complete binary tree" (PDF).

[22] 애런 M.테넨바움 등C, 프렌티스 홀, 1990 ISBN 0-13-19746-7을 이용한 데이터 구조

[23] Paul E. Black(ed.), 알고리즘 및 데이터 구조 사전의 데이터 구조 항목. 미국 국립 표준 기술 연구소 2004년 12월 15일 온라인 버전 2010년 12월 21일 Wayback Machine Accessed 2010-12-19에서 보관.

[24] Parmar, Anand K. (2020-01-22). "Different Types of Binary Tree with colourful illustrations". Medium. Retrieved 2020-01-24.

[25] Mehta, Dinesh; Sartaj Sahni (2004). Handbook of Data Structures and Applications. Chapman and Hall. ISBN 1-58488-435-5.

[Samanta2004-26] D. Samanta (2004). Classic Data Structures. PHI Learning Pvt. Ltd. pp. 264–265. ISBN 978-81-203-1874-8.

[Scott2009-27] Michael L. Scott (2009). Programming Language Pragmatics (3rd ed.). Morgan Kaufmann. p. 347. ISBN 978-0-08-092299-7.

[28] Introduction to algorithms. Cormen, Thomas H., Cormen, Thomas H. (2nd ed.). Cambridge, Mass.: MIT Press. 2001. p. 128. ISBN 0-262-03293-7. OCLC 46792720.{{cite book}}: CS1 유지보수: 기타 (링크)

[29] Demaine, Erik. "6.897: Advanced Data Structures Spring 2003 Lecture 12" (PDF). MIT CSAIL. Archived from the original (PDF) on 24 November 2005. Retrieved 14 April 2022.

[rice-30] Dung X. Nguyen (2003). "Binary Tree Structure". rice.edu. Retrieved December 28, 2010.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]

[11]

[12]

[13]

[14]

[15]

[16]

[17]

[18]

[19]

[20]

[21]

[22]

[23]

[24]

[25]

[26]

[27]

[29]

[30]

v t 트리 데이터 구조
트리 검색 (다이나믹 세트/어소시에이션 어레이)	2–3 2–3–4 AA (a, b) AVL B B+ B* B^x. (최적) 바이너리 검색 춤추다 HTree 간격 주문통계 (좌향) 레드-블랙 희생양 스플라이 T 나무 UB 무게 밸런스
수북이	바이너리 이항 브로달 피보나치 좌파 페어링 스큐 판 엠데 보아스 약한
시도하다	Ctrie C-trie(압축 ADT) 해시 기수 서픽스 삼진수 검색 X-Fast 고속
공간 데이터 파티션 트리	공 BK BSP 데카르트어 힐베르트 R k-d(표준 k-d) M 미터법 MVP 옥트리 PH 우선 순위 R 쿼드 R R+ R* 부분 부사장 X
기타 트리	덮다 지수 펜윅 손가락. 프랙탈 트리 인덱스 퓨전 해시 캘린더 i디스턴스 K-ary 좌측자녀 우측자매 링크/컷 로그 구조화 결합 머클 p q. 범위 SPQR 정상

Search

이진 트리

네임스페이스

더

목차

정의들

재귀적 정의

그래프 이론 개념 사용

바이너리 트리

이진 트리의 속성

조합

이진 트리 저장 방법

노드와 참조

어레이

인코딩

간결한 부호화

일반 트리를 이진 트리로 인코딩

공통 조작

삽입

리프 노드

내부 노드

삭제

하위 항목이 0개 또는 1개 있는 노드

2자녀 노드

트래버설

깊이 우선 순위

폭 우선 순위

「」를 참조해 주세요.

레퍼런스

인용문

참고 문헌

외부 링크

Search

이진 트리

정의들

재귀적 정의

그래프 이론 개념 사용

바이너리 트리

이진 트리의 속성

조합

이진 트리 저장 방법

노드와 참조

어레이

인코딩

간결한 부호화

일반 트리를 이진 트리로 인코딩

공통 조작

삽입

리프 노드

내부 노드

삭제

하위 항목이 0개 또는 1개 있는 노드

2자녀 노드

트래버설

깊이 우선 순위

폭 우선 순위

「 」를 참조해 주세요.

레퍼런스

인용문

참고 문헌

외부 링크

「」를 참조해 주세요.