Today I Learned - Tree, Binary Search Tree

Tree(트리)란?

트리는 노드로 이루어진 자료 구조

 

루트(root): 트리의 최상위 노드

트리는 하나의 루트 노드를 갖음.
루트 노드는 0개 이상의 자식 노드를 갖고 있음.
그 자식 노드 또한 0개 이상의 자식 노드를 갖고 있고, 이는 반복적으로 정의됨

 

Tree 관련 용어

 

루트 노드(root node): 부모가 없는 노드, 트리는 하나의 루트 노드만을 가진다.
단말 노드(leaf node): 자식이 없는 노드, ‘말단 노드’ 또는 ‘잎 노드’라고도 부른다.
내부(internal) 노드: 단말 노드가 아닌 노드
간선(edge): 노드를 연결하는 선 (link, branch 라고도 부름)
형제(sibling): 같은 부모를 가지는 노드
노드의 크기(size): 자신을 포함한 모든 자손 노드의 개수
노드의 깊이(depth): 루트에서 어떤 노드에 도달하기 위해 거쳐야 하는 간선의 수
노드의 레벨(level): 트리의 특정 깊이를 가지는 노드의 집합
노드의 차수(degree): 하위 트리 개수 / 간선 수 (degree) = 각 노드가 지닌 가지의 수
트리의 차수(degree of tree): 트리의 최대 차수
트리의 높이(height): 루트 노드에서 가장 깊숙히 있는 노드의 깊이

 

 

 

---

 

 

 

이진 탐색 트리(Binary Search Tree)란?

Binary Tree는 한 개의 Parent node가

최대 2개의 Child node를 갖는 Tree를 말한다. B-tree의 구성은 root 와 left, right로 구성되어있다.
찾고자 하는 값(value)을 입력하면 value와 root를 비교한 후, 작으면 left를, 크면 right를 root로 변환 하고,

변경된 root를 기준으로 다시 비교하여 left 혹은 right로 이동하는 방식의 Tree가 BST이다.
더 이상 비교할 Child Node(left, right)가 존재하지 않을 때 해당 위치에 data를 입력한다.

 

 

순회 (Traversal)

이진트리를 이용하여 순회(Traversal)을 할 수 있다.

순회의종류에는 3가지가 존재한다.

Preorder Traversal

root -> left -> right

 

Inorder Traversal

left -> root -> right

 

Postorder Traversal

left -> right -> root