일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
1 | 2 | 3 | 4 | |||
5 | 6 | 7 | 8 | 9 | 10 | 11 |
12 | 13 | 14 | 15 | 16 | 17 | 18 |
19 | 20 | 21 | 22 | 23 | 24 | 25 |
26 | 27 | 28 | 29 | 30 | 31 |
Tags
- 프리코스
- 우테코
- 젠킨스
- v-on
- vue
- v-model
- Python
- DevOps
- 3003번
- LeetCode
- 실행 컨텍스트
- 10926번
- 10869번
- 빅오표기법
- JavaScript
- 도커
- 쿠버네티스
- 이벤트캡쳐링
- MSA
- 이벤트버블링
- 백준
- v-if
- 객체지향의 사실과 오해
- v-for
- 코어자바스크립트
- hoisting
- 2588번
- 배열파티션
- 파이썬
- 리스트복사
Archives
- Today
- Total
새오의 개발 기록
자료구조: 트리 본문
트리
트리의 정의
계층형 트리 구조를 시뮬레이션 하는 추상 자료형(ADT)으로,
루트 값과 부모-자식 관게의 서브트리로 구성되며, 서로 연결된 노드의 집합
트리의 각 명칭
- 루트: 자식 노드를 가지며 간선으로 연결되어 있음
- 차수: 자식 노드의 개수
- 크기: 자신을 포함한 모든 자식 노드의 개수
- 높이: 현재 위치에서부터 리프까지의 거리
- 깊이: 루트에서부터 현재 노드까지의 거리
트리의 특징
- 트리는 재귀로 정의된 자기 참조 자료구조이다. -> 자식도 트리고 또 그 자식도 트리
- 레벨은 0에서부터 시작한다.
- 항상 단방향이기 때문에 간선의 화살표는 생략 가능하다.
- 방향은 보통 위에서 아래이다.
트리 vs 그래프
트리는 순환 구조를 갖지 않는 그래프이다.
차이점
- 트리는 특수한 형태의 그래프의 일종이며 크게 그래프의 범주에 포함됨
- 트리는 그래프와 달리 어떠한 경우에도 한번 연결된 노드가 다시 연결되는 법이 없음
- 트리는 그래프와 달리 단방향임
- 트리는 하나의 부모 노드와 하나의 루트를 가짐
트리가 아닌 예
- 1) 순환구조임
- 2) C 노드의 부모가 A, D 둘임
- 3) A->B 와 D<-C->E가 서로 연결되어 있지 않으며 루트가 둘임
이진 트리
이진 트리와 이진 탐색 트리(BST)의 정의
- 각 노드가 m개 이하의 자식을 가지고 있으면, m-ary 트리(다항트리, 다진 트리)이며 여기서 m=2일 경우, 즉 모든 노드의 차수가 2 이하일 때는 특별히 이진 트리라고 구분해서 부름
- 이진 트리는 왼쪽, 오른쪽, 최대 2개의 자식을 갖는 매우 단순한 형태로, 다진 트리에 비해 훨씬 간결할 뿐만 아니라 여러가지 알고리즘을 구현하는 일도 좀 더 간단하게 처리할 수 있다.
- 대체로 트리는 이진 트리이다.
이진 트리의 유형
- 정이진 트리(Full Binary Tree): 모든 노드가 0개 또는 2개의 자식 노드를 갖는다.
- 완전 이진 트리(Complete Binary Tree): 마지막 레벨을 제외하고 모든 레벨이 완전히 채워져 있으며, 마지막 레벨의 모든 노드는 가장 왼쪽부터 채워져 있다.
- 포화 이진 트리(Perfect Binary Tree): 모든 노드가 2개의 자식 노드를 갖고 있으며, 모든 리프 노드가 동일한 깊이 또는 레벨을 갖는다. 문자 그대로, 가장 완벽한 유형의 트리
출처: 파이썬 알고리즘 인터뷰
'Algorithm' 카테고리의 다른 글
Python : 백준 2588번 (0) | 2022.08.27 |
---|---|
Python : 백준 3003번 (0) | 2022.08.25 |
Python : 백준 10926번 (0) | 2022.08.25 |
Python : 백준 10869번 (0) | 2022.08.24 |
Python : 백준 1000번 (0) | 2022.08.24 |