소주제
자료구조, Tree, Graph
노트
- Tree : 단방향 그래프의 한 구조이며, 계층적 자료구조이다. 비 선형구조이며, 아래로만 뻗어나가기 때문에 사이클이 없다. 루트(Root)를 시작으로 여러 개의 데이터를 간선(Edge)으로 연결한다. 각 데이터는 노드(Node)라고 불리며, 두개의 노드가 상하 계층으로 연결되면 부모/자식 관계를 맺는다. 리프(Leaf)는 트리 구조의 끝 지점이며, 자식노드가 없는 노드를 의미한다. 트리구조는 컴퓨터의 디렉토리 구조가 가장 대표적인 예이다. 이 외에 토너먼트 대진표, 가계도, 조직도가 트리 구조의 예이다.
- 깊이(Depth) : 루트로부터 하위 계층의 특정노드까지의 깊이를 표현할 수 있다. 루트를 기준으로 상하 계층이 1개일 때 깊이는 1이다.
- 레벨(Level) : 같은 깊이를 가진 노드를 묶어서 레벨로 표현하며, 같은 레벨의 나란히 있는 노드를 형제 노드(Sibling Node)라고 한다.)
- 높이(Height) : 리프 노드를 기준으로 루트까지의 높이를 표현할 수 있다(깊이와 반대 개념인 것 같다.).
- 서브트리(Sub tree) : 트리 구조를 갖춘 작은 트리
- Binary tree(이진트리) : 자식노드가 최대 두개인 노드로 구성된 트리이다. 자료의 삽입, 삭제 방법에 따라 정이진트리(Full binary tree), 완전 이진트
- Graph:
단문 요약
<aside>
📌
</aside>
Reference
트리 구조
그래프 이론
https://urclass.codestates.com/content/cfab78ac-5f16-4de1-b24c-f45244b6d04b?playlist=4822
https://urclass.codestates.com/content/176f78bb-7e4c-4a12-b604-433538219fd1?playlist=4822