Ordered Data Structures # WEEK 2 : Tree 개념& Binary Trees & Tree Traversals 트리순회

• 지금까지 배운 것(array, linked list, stack, queue)는 linear or flat data structures.
• 오늘 배울 Tree는 data structures that provide complicated data and relationships such as a parent, child, and sibling relationships.

---

2.1 Tree Terminology

*terminology 학술적 용어, 전문용어 (=term)

 

A tree is a linked structure with a sense of ancestry (parents,children, siblings, and more)!

 

Terminology

• Each element in our tree is a node
  • In a tree, the nodes will store data and may be labeled
• Each connection between two nodes is an edge
  • Edges do not have names but are referred to by the nodes they connect.
• Trees must always contain a root node that has no incoming edges.
• Nodes that contain no outgoing edges are called leaf nodes.
• Every node, except the root node, has excatly one parent node.
• A node's children are the nodes with that node as it's parent(It's possible to have anywhere from 0 to infinite children)
• Most ancestry terms apply as expected (sibling, ancestor, grandchild, grandparent)

 

In computer science, we often say that we grow trees backwards because it will represent a tree with the root on the top compared to our normal tree, then will grow out by going down instead of going up

 

Tree 3가지 충족 요건

• Tree is a "rooted(계층적), directed(무방향?), and acyclic(비순환)" structure.
  • Must have a root
  • Must have directed edges 
    • 한국어 강의에서는 A -B를 서로 왔다갔다 할 수 있는 양방향이 곧 무방향이라 했는데, 여기선 아래로 내려가는 엣지라는 의미에서 directed를 사용한 거 같다. 알고보니 그래프 이론에서의 트리와 컴퓨터 과학에서의 트리가 다른 가보다. 나중에 더 공부하고 채우기.
  • Must not have a cycle = no loop

---

Tree 요약

• Trees formed with nodes and edges
• Trees must be rooted, directed, and acyclic
• The relationship between nodes in a tree follow classical ancestry terms(parent, child, etc)

---

지금까지는 트리에 관한 용어에 대한 설명이었고 이제부터는 데이터 구조로서의 트리에 대해

 

2.2 Binary Trees

A binary tree is a tree where every node has at most two children.

 

Binary Tree Children

In binary trees, we will label every child as either the "left child" or "right child" of its parent: 

left child를 가리키는 포인터 하나, right child를 가리키는 포인터 하나. 즉 두개의 포인터가 붙은 연결리스트로 볼 수 있음.

 

Binary Tree Property : Height

 

The height of a binary tree is the number of edges in the longest path from the root to a leaf.

height = 2, height = 4

 

Binary Tree Property : Full 정이진트리

 

A binary tree is full if and only if every node has either zero children or two children.

정이진트리 O, X

 

Binary Tree Property : Perfect 포화이진트리

 

A binary tree is perfect if and only if all interior nodes have two children and leaves are at the same level.

Binary Tree Property : Complete 완전이진트리

 

A binary tree is complete if and only if the tree is perfect up until the last level and all leaf nodes on the last level are pushed to the left.

heap을 이야기하기 시작하면 완전이진트리에 대한 아이디어가 중요!

 

첫번째 질문에 대해 오른쪽 빨간 그래프는 no! full 이지만 complete는 아님 / 두번째 질문에 대해 왼쪽 노란 그래프는 no! complete이지만 자식이 1개인 노드가 있으므로 full은 아님

---

Binary Tree 요약

• Binary Trees are a special case of a tree where each node has at most two children.
• The children of binary tree are referred to as the "left child" and "right child"
• Binary Trees have a height and a definition for being full, perfect, and complete.

 

definitions and particular formalities about trees, so we can discuss in detail how these trees work and begin to build complicated data structures with provable runtimes, by understanding the properties of trees we create.

 

adding data to binary trees and start to organize data around and idea of a tree to create an awesome data structure, that's going to run faster than array or a list in certain circumstances.

---

https://machineboy0.tistory.com/148

트리 (Tree Data Structure) 기초 , 이진트리와 이진탐색트리

---

2.3 Tree Traversal

how do we visit every single node and in what order do we visit these node?

순회하며 방정식이 완성되는 트리

 

this tree happens to be a algebraic tree where we have math equation encoded in the tree.

• 후위, 전위, 중위 순회
• level traversal까지 ( bfs)

Traversal in Search (탐색에서의 순회)

 

the idea of a traversal in a search because often these terms are used interchangeably. 

Doing a traversal requires that every single node is visited. On the other hand, a search allows us to discover a particular node throughtout the tree. So when we discover a node in the tree, we may not visit every single node. We may use a strategy developed into traversal to help us find node quickly but a search ends as soon as we find that node while a traversal is going to visit up to every single node.

 

탐색은 particular node, 순회는 every node visit의 차이

---

https://machineboy0.tistory.com/159

트리 순회 (Tree traversal) - 후위 순회, 전위 순회, 중위 순회