- Tree 란?
- 그래프의 부분집합 [ Graph ) Tree ]
- 모든 점이 서로 연결돼 있으면서 순환되지 않는 형태의 그래프 (no cycle)
- < Binary Search Tree ⊂ Binary Tree ⊂ Tree ⊂ Graph >
- Tree의 특징
- 비선형적 구조 (Non-linear) : 1차원 배열로 표현이 불가함.
- 재구적인 구조 (Recursive) : Root + Subtrees로 나뉜다.
- 계층적인 구조 (Hierarchical) : Parent- children의 구조를 가진다.
- Tree의 특성
- 임의의 두 노드를 연결하는 path는 유일하다. -> 순환되지 않는 구조이기 때문에
- E = V - 1 ( 간선의 수 = 노드의 수 - 1)
- Tree의 Depth와 Height
- Depth (깊이) : 루트 노드부터 임의의 노드x까지 경로의 길이
- Height (높이) : 임의의 노드 x부터 리프 노드까지 경로 중 가장 긴 경로의 edge 수
- 트리의 Height = 루트 노드의 Height
'Python > 자료구조, 알고리즘' 카테고리의 다른 글
| 자료구조, 알고리즘) Graph - About Graph, DFS, BFS (1) | 2024.05.22 |
|---|---|
| 자료구조, 알고리즘) Sorting - Shellsort, Mergesort, Heapsort, Radixsort (1) | 2024.05.17 |
| 자료구조, 알고리즘) Sorting - Bubblesort, Selectionsort, Insertionsort, Quicksort + Partition (1) | 2023.12.10 |
| 자료구조) Binary Search Tree (6) | 2023.12.05 |
| 자료구조) Binary Tree (4) | 2023.11.28 |