Chapter 10: Trees
The tree is a data structure of profound importance. It is used in numerous facets of software development, such as:
• Representing hierarchical relationships.
• Managing sorted data.
• Facilitating fast lookup operations.
There are many types of trees, and they come in various shapes and sizes. In this chapter, you will learn the basics of using and implementing a tree.
트리는 매우 중요한 데이터 구조입니다. 다음과 같은 소프트웨어 개발의 여러 측면에서 사용됩니다.
• 계층 적 관계를 나타냅니다.
• 정렬 된 데이터 관리.
• 빠른 조회 작업을 용이하게합니다.
많은 종류의 나무가 있으며 다양한 모양과 크기로 나옵니다. 이 장에서는 트리 사용 및 구현의 기본 사항을 배웁니다.
Terminology
There are many terms associated with trees, so you will get acquainted with a couple right off the bat.
Node
Like the linked list, trees are made up of nodes.
Each node can carry some data and keeps track of its children.
Parent and child
Trees are viewed starting from the top and branching towards the bottom, just like a real tree, only upside-down.
Every node (except for the topmost one) is connected to exactly one node above it.
That node is called a parent node. The nodes directly below and connected to it are called its child nodes. In a tree, every child has exactly one parent. That’s what makes a tree, well, a tree.
Terminology
나무와 관련된 많은 용어가 있으므로 박쥐에서 바로 부부를 알게 될 것입니다.
Node
연결된 목록과 마찬가지로 트리는 노드로 구성됩니다.
각 노드는 일부 데이터를 전달할 수 있으며 해당 자식을 추적합니다.
Parent and child
나무는 실제 나무처럼 거꾸로 만 위에서부터 시작하여 아래쪽으로 분기됩니다.
모든 노드 (최상위 노드 제외)는 그 위의 정확히 하나의 노드에 연결됩니다.
이 노드를 부모 노드라고합니다. 바로 아래에 연결되어있는 노드를 하위 노드라고합니다. 나무에서 모든 어린이는 정확히 하나의 부모를 갖습니다. 그것이 나무를 만드는 것입니다.
Root
The topmost node in the tree is called the root of the tree. It is the only node that has no parent:
Root
트리의 최상위 노드를 트리의 루트라고합니다. 부모가없는 유일한 노드입니다.
Leaf
A node is a leaf if it has no children:
You will run into more terms later on, but this should be enough to get you started.
Leaf
자식이없는 노드는 잎입니다.
나중에 더 많은 용어를 사용할 수 있지만 시작하기에 충분해야합니다.
Implementation
Open up the starter playground for this chapter to get started. A tree is made up of nodes, so your first task is to create a TreeNode class.
Create a new file named TreeNode.swift and write the following inside it:
Implementation
이 장의 시작 놀이터를 열어 시작하십시오. 트리는 노드로 구성되어 있으므로 첫 번째 작업은 TreeNode 클래스를 만드는 것입니다.
TreeNode.swift라는 새 파일을 만들고 그 안에 다음을 작성하십시오.
Each node is responsible for a value and holds references to all its children using an array.
Next, add the following method inside the TreeNode class:
This method adds a child node to a node.
Time to give it a whirl. Head back to the playground page and write the following:
Hierarchical structures are natural candidates for tree structures, so, here, you have defined three different nodes and organized them into a logical hierarchy. This arrangement corresponds to the following structure:
각 노드는 값을 담당하며 배열을 사용하여 모든 자식에 대한 참조를 보유합니다.
다음으로 TreeNode 클래스 안에 다음 메소드를 추가하십시오.
이 방법은 자식 노드를 노드에 추가합니다.
소용돌이를 줄 시간입니다. 놀이터 페이지로 돌아가서 다음을 작성하십시오.
계층 구조는 트리 구조의 자연스러운 후보이므로 여기서는 세 개의 서로 다른 노드를 정의하고 논리 계층으로 구성했습니다. 이 배열은 다음 구조에 해당합니다.
Traversal algorithms
Iterating through linear collections such as arrays or linked lists is straightforward. Linear collections have a clear start and end:
Iterating through trees is a bit more complicated:
Should nodes on the left have precedence? How should the depth of a node relate to its precedence? Your traversal strategy depends on the problem that you’re trying to solve. There are multiple strategies for different trees and different problems. In the next section, you will look at depth-first traversal, a technique that starts at the root and visits nodes as deep as it can before backtracking.
Traversal algorithms
배열 또는 연결된 목록과 같은 선형 컬렉션을 반복하는 것은 간단합니다. 선형 컬렉션에는 명확한 시작과 끝이 있습니다.
나무를 반복하는 것은 조금 더 복잡합니다.
왼쪽의 노드가 우선해야합니까? 노드의 깊이는 우선 순위와 어떤 관련이 있습니까? 순회 전략은 해결하려는 문제에 따라 다릅니다. 다른 나무와 다른 문제에 대한 여러 가지 전략이 있습니다. 다음 섹션에서는 루트에서 시작하여 역 추적하기 전에 최대한 깊이 노드를 방문하는 기술인 깊이 우선 탐색을 살펴 봅니다.
Depth-first traversal
Write the following at the bottom of TreeNode.swift:
This simple code uses recursion process the next node.
You could use your own stack if you didn’t want your implementation to be recursive.
Time to test it out. Head back to the playground page and write the following:
Depth-first traversal 깊이 우선 탐색
TreeNode.swift의 맨 아래에 다음을 작성하십시오.
이 간단한 코드는 다음 노드에서 재귀 프로세스를 사용합니다.
구현이 재귀 적이기를 원하지 않으면 자신의 스택을 사용할 수 있습니다.
그것을 테스트 할 시간. 놀이터 페이지로 돌아가서 다음을 작성하십시오.
This function creates the following tree:
Next, add this:
This produces the following depth-first output:
In the next section, you will look at level-order traversal, a technique that visits each node of the tree based on the depth of the nodes.
다음 섹션에서는 노드의 깊이에 따라 트리의 각 노드를 방문하는 기술인 레벨 순서 순회를 살펴 봅니다.
Level-order traversal
Write the following at the bottom of TreeNode.swift:
Level-order traversal 레벨 순회 Breadth-first search(너비 우선 탐색)이라고도 불린다.
TreeNode.swift의 맨 아래에 다음을 작성하십시오.
forEachLevelOrder visits each of the nodes in level-order:
forEachLevelOrder는 각 노드를 레벨 순서로 방문합니다.
Note how you used a queue (not a stack) to make sure that the nodes are visited in the right level-order. A simple recursion (which implicitly uses a stack) would not have worked!
Head back to the playground page and write the following:
스택이 아닌 큐를 사용하여 노드가 올바른 레벨 순서로 방문되었는지 확인하십시오. 암시 적으로 스택을 사용하는 간단한 재귀는 효과가 없었습니다!
놀이터 페이지로 돌아가서 다음을 작성하십시오.
In the console, you will see the following output:
콘솔에서 다음과 같은 결과가 나타납니다.
Search
You already have a method that iterates through all the nodes, so building a search algorithm shouldn’t take long. Write the following at the bottom of TreeNode.swift:
Head back to the playground page to test your code. To save some time, simply copy the previous example and modify it to test the search method:
You will see the following console output:
Here, you used your level-order traversal algorithm. Since it visits all of the nodes, if there are multiple matches, the last match will win. This means that you will get different objects back depending on what traversal you use.
Search
이미 모든 노드를 반복하는 방법이 있으므로 검색 알고리즘을 작성하는 데 시간이 오래 걸리지 않습니다. TreeNode.swift의 맨 아래에 다음을 작성하십시오.
놀이터 페이지로 돌아가서 코드를 테스트하십시오. 시간을 절약하려면 이전 예제를 복사하고 수정하여 검색 방법을 테스트하십시오.
다음과 같은 콘솔 출력이 표시됩니다.
여기에서는 레벨 순서 순회 알고리즘을 사용했습니다. 모든 노드를 방문하므로 여러 경기가 있으면 마지막 경기가 승리합니다. 즉, 어떤 순회를 사용 하느냐에 따라 다른 객체를 다시 얻게됩니다.
Key points
• Trees share some similarities to linked lists, but, whereas linked-list nodes may only link to one successor node, a tree node can link to many child nodes.
• Every tree node, except for the root node, has exactly one parent node.
• A root node has no parent nodes.
• Leaf nodes have no child nodes.
• Be comfortable with the tree terminology such as parent, child, leaf and root. Many of these terms are common tongue for fellow programmers and will be used to help explain other tree structures.
• Traversals, such as depth-first and level-order traversals, aren’t specific to the general tree. They work on other trees as well, although their implementation will be slightly different based on how the tree is structured.
Key points
• 트리는 연결된 목록과 일부 유사점을 공유하지만 연결된 목록 노드는 하나의 후속 노드에만 연결될 수 있지만 트리 노드는 많은 하위 노드에 연결될 수 있습니다.
• 루트 노드를 제외한 모든 트리 노드에는 정확히 하나의 부모 노드가 있습니다.
• 루트 노드에는 부모 노드가 없습니다.
• 리프 노드에는 자식 노드가 없습니다.
• 부모, 자식, 잎 및 뿌리와 같은 나무 용어에 익숙해 지십시오. 이 용어들 중 다수는 동료 프로그래머들에게 공통적 인 용어이며 다른 트리 구조를 설명하는 데 사용됩니다.
• 깊이 우선 및 레벨 순서 순회와 같은 순회는 일반 트리에만 국한되지 않습니다. 다른 트리에서도 작동하지만 트리의 구조에 따라 구현 방식이 약간 다릅니다.
