트리 트래버설

컴퓨터 과학에서 트리 트래버설(트리 검색 및 트리 워킹이라고도 함)은 그래프 트래버설의 한 형태이며 트리 데이터 구조의 각 노드를 정확히 한 번 방문하는 프로세스(예: 검색, 업데이트 또는 삭제)를 말합니다.이러한 통과는 노드가 방문하는 순서에 따라 분류됩니다.다음 알고리즘은 이진 트리에 대해 설명되지만 다른 트리에 대해서도 일반화될 수 있습니다.

종류들

원칙적으로 선형 순서로 횡단되는 링크드 리스트, 1차원 어레이 및 기타 선형 데이터 구조와는 달리 트리는 여러 가지 방법으로 횡단될 수 있다.깊이 우선 또는 폭 우선 순서로 교차할 수 있습니다.깊이 우선 순서의 세 가지 일반적인 방법, 즉 순서대로, 사전 순서 및 ^[1]사후 순서가 있습니다.이러한 기본적인 트래버설을 넘어, 심도 우선 검색의 반복적인 심도 우선 검색과 같은 심도 제한 검색과 같은 다양한 보다 복잡한 또는 하이브리드 스키마가 가능합니다.후자는 너비 우선 검색과 함께 무한 트리를 통과하는 데도 사용할 수 있습니다(아래 참조).

트리 트래버설을 위한 데이터 구조

트리를 통과하려면 모든 노드에서 어떤 방식으로든 반복해야 합니다.특정 노드에서 다음 노드가 여러 개(선형 데이터 구조가 아님) 있기 때문에 순차 계산(병렬이 아님)을 가정할 때 일부 노드는 나중에 방문하기 위해 어떤 방식으로든 저장해야 합니다.이것은 많은 경우 스택(LIFO) 또는 큐(FIFO)를 통해 수행됩니다.트리는 자기 참조(재귀적으로 정의) 데이터 구조이므로 트래버설은 재귀 또는 보다 미묘하게 자연스럽고 명확한 방법으로 정의할 수 있습니다.이 경우 지연된 노드는 콜스택에 암묵적으로 저장됩니다.

깊이 우선 검색은 재귀적으로(콜 스택을 통해) 스택을 통해 쉽게 구현되며 폭 우선 검색은 큐를 통해(콜 스택을 통해)^[2]^{: 45−61} 쉽게 구현됩니다.

깊이 우선 검색

이진 트리의 깊이 우선 통과(점 경로):

사전 주문(빨간색 ● 위치에서 방문한 노드):
F, B, A, D, C, E, G, I, H
순서대로(녹색 ● 위치에서 방문한 노드):
A, B, C, D, E, F, G, H, I
사후 주문(파란색 ● 위치에서 방문한 노드):
A, C, E, D, B, H, I, G, F

DFS(Depth-First Search)에서는 검색 트리를 최대한 깊게 한 후 다음 형제 검색으로 이동합니다.

깊이 우선 검색을 사용하여 이진 트리를 이동하려면 각 ^[3]^[4]노드에서 다음 작업을 수행합니다.

현재 노드가 비어 있으면 반환하십시오.
다음의 3개의 조작을 ^[5]일정한 순서로 실행합니다.
N: 현재 노드를 방문합니다.

L: 현재 노드의 왼쪽 서브트리를 재귀적으로 통과합니다.

R: 현재 노드의 오른쪽 서브트리를 재귀적으로 통과합니다.

횡단의 흔적은 트리의 순차화라고 불립니다.트래버설 트레이스는 방문한 각 노드의 목록입니다.사전, 순차 또는 사후 순서에 따른 어떤 순차화도 기본 나무를 고유하게 설명하지 않는다.트리에 고유한 요소가 있는 경우, 트리를 고유하게 설명하려면 사전 순서 또는 순차와 쌍을 이루는 사후 순서 중 하나로 충분합니다.단, 후순이 있는 사전 순서는 트리 ^[6]구조에 애매한 점이 있습니다.

노드(그림에서는 빨강, 초록 또는 파랑)에 대한 트래버설의 위치가 노드의 방문을 실행하는 방법은 세 가지가 있습니다.다음 설명과 같이 정확히 한 가지 색상을 선택하면 노드가 한 번 방문됩니다.세 가지 색상을 모두 방문하면 동일한 노드를 세 번 방문하여 "모든 순서" 시퀀셜라이제이션이 이루어집니다.

F-B-A-A-D-C-C-D-D-E-E-D-B-G-I-H-H-I-I-G-F

사전 주문, NLR

현재 노드를 방문합니다(그림: 빨간색 위치).
현재 노드의 왼쪽 하위 트리를 재귀적으로 통과합니다.
현재 노드의 오른쪽 하위 트리를 재귀적으로 통과합니다.

부모 노드는 하위 노드 중 하나가 수행되기 전에 처리되기 때문에 사전 순서 통과는 토폴로지적으로 정렬된 것입니다.

사후 주문, LRN

현재 노드의 왼쪽 하위 트리를 재귀적으로 통과합니다.
현재 노드의 오른쪽 하위 트리를 재귀적으로 통과합니다.
현재 노드를 방문합니다(그림: 파란색 위치).

포스트오더 트래버설은 바이너리 식 트리의 포스트픽스식을 취득하는 경우에 편리합니다.

순서대로, LNR

현재 노드의 왼쪽 하위 트리를 재귀적으로 통과합니다.
현재 노드를 방문합니다(그림: 녹색 위치).
현재 노드의 오른쪽 하위 트리를 재귀적으로 통과합니다.

각 노드에서 키가 왼쪽 서브트리의 모든 키보다 크고 오른쪽 서브트리의 모든 키보다 작도록 정렬된 바이너리 검색 트리에서 트래버설은 오름차순으로 ^[7]키를 검색합니다.

역순서, NRL

현재 노드를 방문합니다.
현재 노드의 오른쪽 하위 트리를 재귀적으로 통과합니다.
현재 노드의 왼쪽 하위 트리를 재귀적으로 통과합니다.

역순서, RLN

현재 노드의 오른쪽 하위 트리를 재귀적으로 통과합니다.
현재 노드의 왼쪽 하위 트리를 재귀적으로 통과합니다.
현재 노드를 방문합니다.

역순서, RNL

현재 노드의 오른쪽 하위 트리를 재귀적으로 통과합니다.
현재 노드를 방문합니다.
현재 노드의 왼쪽 하위 트리를 재귀적으로 통과합니다.

각 노드에서 키가 왼쪽 서브트리의 모든 키보다 크고 오른쪽 서브트리의 모든 키보다 작도록 정렬된 바이너리 검색 트리에서 역순으로 키를 검색합니다.

임의 트리

깊이 우선 검색을 사용하여 임의 트리(꼭 이진 트리일 필요는 없음)를 이동하려면 각 노드에서 다음 작업을 수행합니다.

현재 노드가 비어 있으면 반환하십시오.
현재 노드를 방문하여 사전 주문 트래버설을 확인하십시오.
1에서 현재 노드의 하위 트리 수 - 1까지의 각 i에 대해, 또는 역 트래버설의 경우 후자에서 전자로의 i에 대해 다음을 수행합니다.
1. 현재 노드의 i번째 하위 트리를 재귀적으로 통과합니다.
2. 순서대로 통과하려면 현재 노드를 방문하십시오.
현재 노드의 마지막 하위 트리를 재귀적으로 통과합니다.
주문 후 트래버설은 현재 노드를 참조하십시오.

눈앞의 문제에 따라서는, 프리오더, 포스트오더, 특히 서브트리수의 1개(1개의 순서 내 조작)가 옵션인 경우가 있습니다.또한 실제로는 사전 주문, 사후 주문 및 순차 작업이 둘 이상 필요할 수 있습니다.예를 들어 삼원수에 삽입할 때는 항목을 비교하여 사전 주문 조작을 실시한다.나중에 트리의 균형을 재조정하기 위해 사후 작업이 필요할 수 있습니다.

폭 우선 검색

레벨 순서: F, B, G, A, D, I, C, E, H.

폭 우선 검색(BFS) 또는 레벨 순서 검색에서는 검색 트리를 최대한 넓힌 후 다음 깊이로 이동합니다.

기타 타입

깊이 우선 검색이나 폭 우선 검색으로 분류되지 않는 트리 통과 알고리즘도 있습니다.그러한 알고리즘 중 하나는 몬테카를로 트리 검색으로, 가장 유망한 움직임을 분석하는 데 초점을 맞추고, 검색 공간의 무작위 샘플링에 기반한 검색 트리의 확장을 기반으로 한다.

적용들

산술식을 나타내는 트리:A * (B − C) + (D + E)

사전 순서 트래버설을 사용하여 식 트리에서 접두사 식(폴란드어 표기법)을 만들 수 있습니다. 식 트리를 사전 순서로 트래버설합니다.예를 들어, 표시된 산술식을 사전 순서로 이동하면 "+ * A - B C + D E"가 생성됩니다.프리픽스 표기법에서는 각 연산자가 일정한 수의 오퍼랜드를 가지고 있는 한 괄호는 필요 없습니다.프리오더 트래버설은 트리의 복사본을 만드는 데도 사용됩니다.

포스트오더 트래버설은 바이너리 트리의 포스트픽스 표현(폴란드어 역 표기법)을 생성할 수 있습니다.그림으로 나타낸 산술식을 후순으로 이동하면 "A B C - * D E +"가 생성됩니다. 후자는 스택 머신에 의해 식을 평가하기 위해 기계 코드로 쉽게 변환할 수 있습니다.포스트오더 트래버설은 트리를 삭제하는 데도 사용됩니다.각 노드는 하위 노드를 해방한 후 해방됩니다.

순서 트래버설은 바이너리 검색 트리를 설정한 비교기에 따라 기본 집합에서 값을 순서대로 반환하기 때문에 바이너리 검색 트리에서 매우 일반적으로 사용됩니다.

실장

깊이 우선 검색 구현

사전 주문 구현

노드 = null return visit(node) preorder(node.left) preorder(node.right)인 경우 절차 preorder(node).

stack.is Empty() 노드← stack.pop() visit(node) // 오른쪽 아이가 먼저 푸시되고 node.right null stack.right(node.right) node.right null stack.right(node.right) node.right(node.right)가 node.right null이면 왼쪽이 먼저 처리됩니다.stack.snode(node.left)

주문 후 구현

노드 = null return postorder(node.left) postorder(node.right) visit(node)인 경우 절차 포스트오더(node)

절차 repeativePostorder(노드) stack ← 빈 스택 lastNodeVisited ← null(stack).isEmpty() 또는 node ifnull(노드) node ← node.left else peekNode ← stack.dack() //가 아닌 동안 null을 실행한 다음 ri를 이동합니다.peekNode.right null null 및 lastNodeVised peek peekNode.right node ← peekNode.right else vised(peekNode) lastNodeVised ← stack.pop()인 경우 ght

순서대로의 실장

노드 = null return inorder(node.left) visit(node) inorder(node.right)인 경우 절차 inorder(node)

procedure repeativeInder(node) stack ← stack.isEmpty() 또는 node nullnode ← node . left else node ← stack . pop ( node ) visit ( node )node ← node . right node node node node node node node while while while while while.

다른 종류의 사전 주문

트리가 배열로 표시되는 경우(첫 번째 인덱스는 0) 다음 ^[8]^{[clarification needed]}요소의 인덱스를 계산할 수 있습니다.

절차 bubbleUp(배열, i, 리프) k ← 1 i ← (i - 1)/2인 반면 (리프 + 1) % (k * 2) k k ← 2 * k 반환 i 프로시저 사전 순서(배열) i ← 0인 반면 i ≠ 배열.size visit(array[i]) i ← 1 / 2 크기인 경우 i ← 1 / 2 크기 </2 크기 i>리프 ← i - size/2 부모 ← bubble_up(어레이, i, 리프) i ← 부모 * 2 + 2

다음 노드 또는 이전 노드로 진행

그node이진 검색 트리에서 찾을 수 있습니다.bst여기에 부모 포인터 없이 구현에서 보여지는 표준 검색 기능에 의해, 즉, 그것은 다음을 사용한다.stack조상 포인터를 보유할 수 있습니다.

프로시저 검색(bst, key) // (노드, 스택) 노드 = bst.root stack ← 빈 스택을 반환하고, 키가 = 노드인 경우 노드 ≠ null stack.dlack(노드)을 반환합니다.키 < 노드일 경우 키 반환(노드, 스택)키 노드 ← node.left else 노드 ← node.right return(비어 있음, 빈 스택)

inorderNext^[2]^{: 60} 함수는 다음 네이버를 순서대로 반환합니다.node, 순서부여의 어느쪽인가(용)dir=1또는 프로세서 순서(용)dir=0) 및 갱신된stack따라서 이진 검색 트리를 순서대로 정렬하여 지정된 방향으로 검색할 수 있습니다.dir더 멀리.

프로시저 inorderNext(노드, dir, stack) newnode ← child[ node ]null do node ← newnode stack . node ← node . child [ 1 - node ]newnode [ node ]node ← null return ( node , stack ) // node : stack . is Empty ( setry ( scome ) // node ) ） 。oldnode ← node node ← stack.pop() // oldnode = child [ hild ] // 이제 oldnode [ child ], // 즉, 노드 = 원래 노드 반환(노드, 스택)의 상위 노드(및 이전 노드)

함수는 키를 사용하지 않습니다. 즉, 순차 구조는 이진 검색 트리의 가장자리에 의해 완전히 기록됩니다.방향 변경이 없는 트래버스의 경우 전체 트래버스는 크기 $n$ 의 BST에 대해 $2n-2$ - $2n-2$ ({ $display$ $style$ $2n-2}$ 스텝 $2n-2$ ,엣지 업에 대해 $1스텝$ ,엣지 다운에 대해 1스텝의 스텝이 $2n-2$ 하기 때문에 평균 ${\mathcal {O}}(1),$ 는 ${\mathcal {O}}(1),$ O(1 ${\mathcal {O}}(1),$ { $displaystyle {O}($ 1)입니다 ${\mathcal {O}}(1),$ $.$ 최악의 경우 복잡도는 O $h)$ style $(h$ )이고 ${\mathcal {O}}(h)$ h $(h$ $)$ style $(h)$ 는 $h$ tree 높이로 h( $h)$ 를 나타낸다 $.$

위의 모든 구현에는 트리의 높이에 비례하는 스택공간이 필요합니다.이것은 재귀용 콜스택이며 반복용 부모(고조)스택입니다.균형이 잘 잡히지 않는 나무에서는 이 문제가 상당히 심각할 수 있습니다.반복 구현에서는 각 노드에서 부모 포인터를 유지하거나 트리(다음 섹션)를 스레드화함으로써 스택 요건을 제거할 수 있습니다.

스레딩을 사용한 순서대로 Morris 통과

바이너리 트리는 모든 왼쪽 자녀 포인터(존재하는 경우)가 노드의 순서 있는 이전 노드(존재하는 경우)를 가리키도록 하여 스레드화되어 모든 오른쪽 자녀 포인터(존재하는 경우)가 노드의 순서 있는 후계 노드(존재하는 경우)를 가리키도록 합니다.

장점:

콜 스택을 사용하여 메모리와 시간을 소비하는 재귀가 회피됩니다.
노드에는 부모 레코드가 유지됩니다.

단점:

그 나무는 더 복잡하다.
한 번에 한 번만 통과시킬 수 있습니다.
두 개의 자식 모두 존재하지 않고 노드의 두 값이 모두 상위 항목을 가리킬 경우 오류가 발생하기 쉽습니다.

Morris traversal은 ^[9]스레드를 사용하는 순차 트래버설 구현입니다.

순서대로 후계자 링크를 만듭니다.
이 링크를 사용하여 데이터를 인쇄합니다.
변경 내용을 원래 트리로 되돌립니다.

폭 우선 검색

또한 다음 목록은 단순 큐베이스 레벨순서 트래버설용 의사코드입니다.또한 특정 깊이의 최대 노드 수에 비례하는 공간이 필요합니다.이는 전체 노드 수의 절반까지 가능합니다.이러한 유형의 횡단에 대한 보다 공간 효율적인 접근방식은 반복적인 깊이 우선 검색을 사용하여 구현될 수 있다.

procedure levelorder(node) queue ← empty() node ← queue.dequeue() visit(node) if node.left null node.right right null queue.enqueue(node.left) if node.right right node.

트리가 배열로 표시되는 경우(첫 번째 인덱스는 0), 모든 요소에서 충분히 반복됩니다.

프로시저 레벨 순서(배열)는 0 ~array.size 방문(array[i])입니다.

무한대나무

트래버설은 보통 노드 수가 유한한 트리(따라서 유한 깊이 및 유한 분기 계수)에 대해 수행되지만 무한 트리에 대해서도 수행될 수 있습니다.무한 데이터 구조는 (엄밀하게) 평가되지 않지만 무한 시간이 걸리기 때문에 쉽게 정의하고 작업할 수 있기 때문에 기능 프로그래밍(특히 느린 평가)에 특히 관심이 있습니다.체스나 바둑용 게임 트리처럼 어떤 유한한 나무는 너무 커서 명시적으로 나타낼 수 없기 때문에 무한하다고 해석하는 것이 유용하다.

트래버설의 기본 요건은 결국 모든 노드를 방문하는 것입니다.무한 트리의 경우 단순한 알고리즘이 실패하는 경우가 많습니다.예를 들어 무한한 깊이의 이진 트리가 주어진 경우 깊이 우선 검색은 트리의 한 쪽(정례적으로 왼쪽) 아래로 내려가고 나머지 부분에는 방문하지 않습니다.순서 또는 후순 트래버설은 리프(실제로 리프)에 도달하지 않았기 때문에 노드를 방문하지 않습니다.반면 폭 우선(레벨 순서) 트래버설은 문제 없이 무한 깊이 이진 트리를 통과하며, 실제로 경계 분기 계수가 있는 모든 트리를 통과합니다.

한편 루트에 무한히 많은 자녀가 있고 이들 자녀 각각이 2명의 자녀가 있는 깊이 2의 트리가 주어지면 깊이 우선 검색은 모든 노드를 방문합니다.이는 손자(한 노드의 자녀)가 소진되면 다음 순서로 진행되기 때문입니다(루트에 도달하지 않는 경우).반면 폭 우선 탐색은 자녀들을 먼저 지치게 하기 때문에 손자 손녀에게는 절대 닿지 않는다.

실행 시간의 보다 정교한 분석은 무한 서수를 통해 얻을 수 있습니다. 예를 들어, 위의 깊이 2 트리의 폭 우선 탐색은 첫 번째 레벨에 대해 θ, 두 번째 레벨에 대해 다른 θ의 두 단계를 거칩니다.

따라서 단순한 깊이 우선 또는 너비 우선 검색은 모든 무한 트리를 통과하는 것이 아니며 매우 큰 트리에서 효율적이지 않습니다.그러나 하이브리드 방법은 기본적으로 대각선 인수를 통해 (계수적으로) 무한 트리를 통과할 수 있습니다("수직과 수평의 조합인 "대각선"은 깊이와 폭의 조합에 해당합니다).

구체적으로는 무한히 갈라진 나무에서 뿌리(1), (2), …, 손자(1, 1), (1, 2), …, (2, 2), … 등에게 라벨을 붙인다.따라서 노드는 셀 수 있고 엔트리의 합에 의해 먼저 순서가 매겨질 수 있는 양의 유한(아마도 빈) 시퀀스와 일대일 대응 관계에 있으며, 그 후 주어진 합계 내에서 사전적 순서에 의해 배치될 수 있다(최종적으로 많은 시퀀스만 주어진 값에 도달하므로, 모든 엔트리에 도달한다). 공식적으로는 유한한 수의 수가 존재한다.주어진 자연수, 특히 2가지ⁿ⁻¹ 성분인 n ), 1)의 성분으로 구성되며, 이는 횡단을 제공한다.명시적:

()
(1)
(1, 1) (2)
(1, 1, 1) (1, 2) (2, 1) (3)
(1, 1, 1, 1) (1, 1, 2) (1, 2, 1) (1, 3) (2, 1, 1) (2, 2) (3, 1) (4)

기타.

이는 무한 깊이 바이너리 트리를 이 트리에 매핑한 다음 폭 우선 검색을 적용하는 것으로 해석할 수 있습니다. 부모 노드를 두 번째 자녀와 연결하는 "다운" 에지를 첫 번째 자녀에서 두 번째 자녀로, 두 번째 자녀에서 세 번째 자녀로 "오른쪽" 에지로 교체하는 것입니다.따라서 각 스텝에서는 아래로 내려가거나(마지막 번호에 1을 추가) 오른쪽(루트 제외)로 갈 수 있습니다.이러한 루트는 무한 바이너리 트리와 위의 번호의 대응관계를 나타냅니다.엔트리의 합계는 루트로부터의 거리에 대응하고 있습니다(1을 뺀 값)는 동의하고 있습니다.h 무한 이진 트리의 깊이 n - 1에 있는 2개의ⁿ⁻¹ 노드(2개는 이진수에 해당).

레퍼런스

^ "Lecture 8, Tree Traversal". Retrieved 2 May 2015.
^ ^a ^b Pfaff, Ben (2004). An Introduction to Binary Search Trees and Balanced Trees. Free Software Foundation, Inc.
^ 바이너리 트리 트래버설 방식
^ "Preorder Traversal Algorithm". Retrieved 2 May 2015.
^ R 앞의 L은 그림과 같이 (표준) 시계 반대 방향 횡단을 의미합니다.
L과 R의 전, 간 또는 후의 N의 실행에 의해서, 상기의 몇개의 방법이 결정됩니다.
트래버설이 반대로(시계 방향으로) 이동하면 트래버설이 반전됩니다.특히 데이터를 내림차순으로 검색하는 역순으로 설명합니다.
^ "Algorithms, Which combinations of pre-, post- and in-order sequentialisation are unique?, Computer Science Stack Exchange". Retrieved 2 May 2015.
^ Wittman, Todd. "Tree Traversal" (PDF). UCLA Math. Archived from the original (PDF) on February 13, 2015. Retrieved January 2, 2016.
^ "constexpr tree structures". Fekir's Blog. 9 August 2021. Retrieved 2021-08-15.
^ Morris, Joseph M. (1979). "Traversing binary trees simply and cheaply". Information Processing Letters. 9 (5): 197–200. doi:10.1016/0020-0190(79)90068-1.

원천

데일, 넬Lilly, Susan D. "Pascal Plus Data Structures"D. C. 히스 앤 컴퍼니1995년 매사추세츠 주 렉싱턴제4판
드로즈덱, 아담"C++의 데이터 구조 및 알고리즘"브룩/콜퍼시픽 그로브, 캘리포니아, 2001년제2판
'트리의 횡단'(math.northwestern.edu)

외부 링크

PHP의 트래버설 예제를 사용하여 데이터베이스에 계층 데이터 저장
MySQL에서의 계층 데이터 관리
MySQL에서의 그래프 조작
Python의 재귀 트리 트래버설 샘플 코드입니다.
Rosetta 코드의 다양한 프로그래밍 언어로 구현된 트리 트래버설을 참조하십시오.
재귀 없는 트리 트래버설

[holtenotes-1] "Lecture 8, Tree Traversal". Retrieved 2 May 2015.

[Pfaff-2] Pfaff, Ben (2004). An Introduction to Binary Search Trees and Balanced Trees. Free Software Foundation, Inc.

[3] 바이너리 트리 트래버설 방식

[4] "Preorder Traversal Algorithm". Retrieved 2 May 2015.

[5] R 앞의 L은 그림과 같이 (표준) 시계 반대 방향 횡단을 의미합니다.
L과 R의 전, 간 또는 후의 N의 실행에 의해서, 상기의 몇개의 방법이 결정됩니다.
트래버설이 반대로(시계 방향으로) 이동하면 트래버설이 반전됩니다.특히 데이터를 내림차순으로 검색하는 역순으로 설명합니다.

[6] "Algorithms, Which combinations of pre-, post- and in-order sequentialisation are unique?, Computer Science Stack Exchange". Retrieved 2 May 2015.

[7] Wittman, Todd. "Tree Traversal" (PDF). UCLA Math. Archived from the original (PDF) on February 13, 2015. Retrieved January 2, 2016.

[8] "constexpr tree structures". Fekir's Blog. 9 August 2021. Retrieved 2021-08-15.

[9] Morris, Joseph M. (1979). "Traversing binary trees simply and cheaply". Information Processing Letters. 9 (5): 197–200. doi:10.1016/0020-0190(79)90068-1.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Search

트리 트래버설

네임스페이스

더

목차

종류들