[알고리즘][트리] 이진트리(Tree Diagram) - Python

1. 트리 구조

1.1 트리의 정의

https://ko.wikipedia.org/wiki/%ED%8A%B8%EB%A6%AC_%EA%B5%AC%EC%A1%B0

 

- 트리는 계층형 트리 구조를 시물레이션하는 추상형 자료형(ADT)으로, 루트 값과 부모-자식 관계의 서브트리로 구성되며, 서로 연결된 노드의 집합입니다. 

- 트리의 중요한 속성은 '재귀로 정의된(Recursively Defined) 자기 참조(Self Refrential) 자료구조' 라는 점입니다. 풀어 설명하자면, 트리의 자식도 트리이고 그 자식의 자식도 트리입니다. 즉, 트리는 여러개의 서브트리로 구성되어있습니다.

- 보통 데이터베이스는 내부적으로 대용량 데이터 처리에 적합하도록 트리 자료구조를 이용하여 항상 데이터가 정렬되어 있습니다. 탐색에 빠르고 용이한 트리구조로 되어있어서, 데이터가 많아도 탐색 속도가 빠릅니다. 

 

 

1.1 트리의 특징

- "트리는 순환 구조(Cyclic)를 갖지 않는 그래프"

: 트리는 그래프의 범주에 포함되지만, 다른 그래프와 달리 어떠한 경우에도 한 번 연결된 노드가 다시 연결되는 법이 없습니다.

 

<트리 vs 그래프>

1) 트리는 부모 노드에서 자식 노드로 가르키는 단 방향 노드밖에 없다.

2) 트리는 단 하나의 부모 노드를 갖는다. 

3) 트리는 루트도 하나이다.

 

 

 

 

https://techdifferences.com/difference-between-tree-and-graph.html

 

	트리(Tree)	그래프(Graph)
path	두 노드간에는 하나의 길만 존재	두 노드 간에는 하나 이상의 길이 존재
루트 노드	단 하나의 루트 노드 존재	루트 노드가 없음
루프	허용 안됨	루프 가능
복잡도	덜 복잡	상대적으로 더 복잡
순회 방법	Pre-order, In-order, Post-order	BFS, DFS
edge 수	노드가 n개라면 n-1	제한 없음
모델 유형	계층(Hierarchical)	네트워크(Network)

https://techdifferences.com/difference-between-tree-and-graph.html

 

 

2. 이진 트리(Binary Tree)

2.1 이진 트리의 정의 

- [나무위키] 이진트리란 부모 노드 밑의 자식 노드 개수, 즉 차수(degree)를 최대 2개로 제한하는, 트리의 가장 간단한 형태다. 두 자식 노드를 보통 왼쪽 자식과 오른쪽 자식으로 구분지으며, 하나의 값과 왼쪽, 오른쪽 자식 노드를 각각 가리킬 두 개의 포인터를 가진 구조로 구현할 수 있다.

 

2.2 이진 트리의 유형

트리 유형	설명
정 이진 트리 (Full Binary Tree)	- 모든 트리의 자식은 0개나 2개다.
완전 이진 트리 (complete binary tree)	- 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있습니다. - 포화 이진 트리는 완전 이진 트리의 부분집합입니다.
포화 이진 트리 (perfect binary tree)	- 모든 노드가 2개의 자식 노드를 갖고 있으며, 몯느 리프 노드가 동일한 깊이의 레벨을 갖습니다.  - 문자 그대로 가장 완벽한 유형의 트리입니다. .

https://greatzzo.tistory.com/m/14?category=662799

 

3. 이진 탐색 트리(Binary Search Tree)

3.1 이진 탐색 트리의 정의

- [나무위키] 이진 트리의 일종으로, 노드의 왼쪽 가지에는 노드의 값보다 작은 값들만 있고, 오른쪽 가지에는 큰 값들만 있도록 구성되었다.

=> 왼쪽 자식 노드 < 부모 노드 < 오른쪽 자식 노드

https://namu.wiki/w/%ED%8A%B8%EB%A6%AC(%EA%B7%B8%EB%9E%98%ED%94%84)

 

3.2 이진 탐색 트리의 특성

 - 이진 탐색 트리 구조로 되어있다면, 어떤 값 n을 찾을 때, 루트 노드와 비교해서 n이 더 작다면 루트 노드보다 큰 값들만 모여 있는 오른쪽 가지는 전혀 탐색할 필요가 없다. 마찬가지로 루트 노드의 왼쪽 자식보다 n이 크다면 왼쪽 자식의 왼쪽 가지는 탐색할 필요가 없습니다.

- 다시 말해 트리 자체가 이진 탐색을 하기에 적합한 구성이 되는 것이다. 또한 값을 찾을 때 뿐만이 아니라 값을 삽입하거나 삭제할 때도 똑같은 과정을 거칩니다. 

 

- 이상적인 상황에서 탐색/삽입/삭제 모두 시간복잡도가 O(log N)이 된다. 하지만, 운이 안좋으면(트리가 편향된 경우) 최악의 경우에 O(N)의 시간이 걸리게 됩니다.

 

 

<참고>

http://www.kyobobook.co.kr/product/detailViewKor.laf?ejkGb=KOR&mallGb=KOR&barcode=9791189909178&orderClick=LEa&Kc=

파이썬 알고리즘 인터뷰 - 교보문고