나무?
복수개일 경우 숲 forest?
}
트리의 특징
//from
자료구조,data_structure; merge
그래프,graph의 일종? - Yes
connected acyclc graph - 항상? chk
connected_graph acyclic_graph {
순환,cycle이 없는
그래프,graph }
// via
https://youtu.be/VSgI2cr-f28?t=305
undirected_graph이기도 하다 - 아니라고 볼 수도 있지 않나 (ex. disjoint set을 표현하는 경우)
암튼 저기 관점은,
tree는 연결된 비순환 무방향성 그래프 (connected, acyclic, undirected)
- 두 vertex는 유일한 단순 경로(unique simple path)로 연결된다. // 단순경로,simple_path 연결,connection
- 간선을 (하나만) 제거하면 (그 결과가 되는 그래프는) 더 이상 연결되지 않는다. (disconnected)
- 간선을 하나만 추가하면 (그 결과가 되는 그래프는) 순환,cycle을 포함하게 된다.
- 을 만족한다.
Sub:
RB트리,red-black_tree - 이진트리
AVL트리,AVL_tree
트립,treap
segment_tree
{
Segment Tree
is a data structure that allows answering range queries over an array effectively, while still being flexible enough to allow modifying the array.
https://cp-algorithms.com/data_structures/segment_tree.html
https://news.ycombinator.com/item?id=24650084
↑↓merge
Semi-twins:
'수학백과: 수형도'(
수학백과: 수형도(https://terms.naver.com/entry.naver?docId=3405185&cid=47324&categoryId=47324))의 section 3 참조
{
(graph is connected) ⇔ (graph has its 생성수형도)
}
minimal과 minimum이 둘 다 쓰이나??
'수학백과: 수형도'(
수학백과: 수형도(https://terms.naver.com/entry.naver?docId=3405185&cid=47324&categoryId=47324))의 section 3에서는 minimum
수학백과: 수형도(https://terms.naver.com/entry.naver?docId=3405185&cid=47324&categoryId=47324) (tree)
숲(forest), 생성수형도(spanning_tree), 최소생성수형도(minimum_spanning_tree, MST) 언급.
MST를 찾는 알고리듬 중 Kruskal_algorithm, Prim_algorithm 언급.
차수(번역?)가 1인 꼭짓점 = 매달린 꼭짓점(pendant vertex) = 잎(leaf).
두산백과: 수형도(https://terms.naver.com/entry.naver?docId=1178700&cid=40942&categoryId=32223) (tree diagram)