[자료구조] 트리(tree)

트리의 특징

1. Tree는 비선형 자료구조 이다.

 

이 말은 linear(선형)인 자료구조들 즉 스택과 배열 처럼 자료들간 앞뒤관계가 1:1인 것들과 다르게 하나의 자료 뒤에 여러개의 자료가 존재한다는 뜻이다. 

2. 트리는 계층적 관계를 표현하는 자료구조이다.

 

즉 level 이 있다는 뜻이다. tree는 층별 숫자를 매긴다. Root노드 부터 0으로 시작해서 아래로 내려갈수록 커진다.

이때 트리의 최고레벨을 가리켜 height라고 한다.

 

트리의 구성요소

- node(노드): 트리를 구성하고 있는 각각의 요소이다.

- edge(엣지): 간선 (즉 노드와 노드를 연결하는 선이다.)

- root node(루트노드): 트리의 최상위에 있는 노드이다.

- terminal node,leaf node (단말노드): 하위에 다른 node가 연결되어 있지 않은 노드

- internal node(내부노드): 단말노드가 아닌 노드들(root 노드도 포함)

- parent node (부모노드): 

- chile node (자식노드)

 

트리의 종류

1. Binary Tree(이진트리)

- root node중심으로 2개의 subtree로 나누어진다. 그리고 그 두 서브트리도 이진트리여야한다. 

조금더 쉽게 설명하자면 childnode가 최대 두개까지만 붙는 tree를 binary tree라고 한다는 말이다.

이렇게 세개로 나누어지면 ternary tree 이고 네개로 나누어지는 트리도있다.

- 공집합도 이진트리로 포함시켜야한다. 

 

Binary Search Tree(이진 탐색 트리)

-  우선 이 binary search tree는 binary tree의 종류중 하나이며 효율적인 탐색을 위해 특정한 데이터를 저장하는 규칙을 따른다.

-  각각의 node의 값들이 root node보다 크면 오른쪽, 작으면 왼쪽에 놓여진다.

-  이진 탐색트리의 탐색 연산은 주로 O(logn)이다.

-  하지만 skewed tree(편향트리), 노드들이 한쪽으로만 몰려서 생기는 현상이 나타날 경우 탐색의 worst case가 되어 O(n)이 될 수도 있다.

 

Balanced Binary Tree v.s Unbalanced Binary Tree(

균형이 맞는 트리와 그렇지 않은 트리이다.  위에 나왔던 skewed tree의 해결책중 하나인 red-black tree 또한 balanced tree이다.

 

Complete Binary Tree(완전 이진 트리)

이 완전 이진트리는 마지막레벨을 제외하고 모든 노드들이 채워져있다. 

그리고 마지막 레벨은 왼쪽에서부터 오른쪽으로 채워져야한다.

 

Full Binary Tree v.s Perfect  Binary tree

우선 full binary tree 부터 소개하자면 

하나의 child node를 가진 트리가 없는 tree를 full binary tree라고 한다.

 

반면, perfect binary tree는 full binary tree와는 다르게 레벨까지 딱 떨어져야 한다. 

 

 

 

참고자료

https://github.com/JaeYeopHan/Interview_Question_for_Beginner/tree/master/DataStructure#tree

https://www.youtube.com/watch?v=LnxEBW29DOw&list=PLjSkJdbr_gFY8VgactUs6_Jc9Ke8cPzZP&index=1