트리,tree

나무?
복수개일 경우 숲 forest?

def. connected graph without cycle ? 순환,cycle 없는 연결그래프,connected_graph?

용어정리 시작
{
root - tree에서 parent가 없는 유일한.. 'node'? - https://xlinux.nist.gov/dads/HTML/root.html
aka root_vertex ?
aka root_node ? CHK.
{
이거 pagename 근/root과 겹치는데 어떻게하는게 최선인지 TBD
https://mathworld.wolfram.com/RootVertex.html
https://proofwiki.org/wiki/Definition:Root_Node
}
leaf = external node = terminal node - child(ren)이 없는 node. https://xlinux.nist.gov/dads/HTML/leaf.html
node - https://xlinux.nist.gov/dads/HTML/node.html
external_node - =leaf.
internal_node = nonterminal_node - https://xlinux.nist.gov/dads/HTML/internalnode.html
order (1) (tree에 대해) =height. (2) (binomial_tree에 대해) root의 children의 수. (3) (B-tree에 대해) node의 최대 children의 수. (4) (multiway_merge에서) data_stream의 수. ω로 표기. https://xlinux.nist.gov/dads/HTML/order.html
ordered tree - 모든 node의 children에 순서,order가 정해진 tree. https://xlinux.nist.gov/dads/HTML/orderedtree.html
rooted tree = oriented tree - root가 있는 tree. https://xlinux.nist.gov/dads/HTML/rootedtree.html
rooted_tree
{
rooted tree = oriented tree



Opp. free_tree //바로아래쪽

https://mathworld.wolfram.com/RootedTree.html
... Ndict:rooted tree Google:rooted tree
}
free tree - root가 없는 tree. https://xlinux.nist.gov/dads/HTML/freetree.html
free_tree
{
https://mathworld.wolfram.com/FreeTree.html "A tree which is not rooted" "aka unrooted tree"
}
degree (1) (vertex에 대해) 그것에 연결된 edge 수. (2) (그래프,graph에 대해) the maximum degree of any vertex. (3) (트리,tree node에 대해) 그것이 가진 child node의 수. https://xlinux.nist.gov/dads/HTML/degree.html
height 높이 https://xlinux.nist.gov/dads/HTML/height.html
depth 깊이 - (한 node에 대해) root로부터의 거리. https://xlinux.nist.gov/dads/HTML/depth.html
level - (1) 한 tree에서 같은 depth를 가진 모든 node들. (2) (한 node에 대해) =depth. https://xlinux.nist.gov/dads/HTML/level.html
parent https://xlinux.nist.gov/dads/HTML/parent.html
child(ren) https://xlinux.nist.gov/dads/HTML/child.html
sibling - 같은 parent를 가진 node들. https://xlinux.nist.gov/dads/HTML/sibling.html
descendant 자손/후손/... https://xlinux.nist.gov/dads/HTML/descendant.html
ancestor 조상/선조/... https://xlinux.nist.gov/dads/HTML/ancestor.html
forest - 하나 이상의 tree(들)의 collection. https://xlinux.nist.gov/dads/HTML/forest.html
https://mathworld.wolfram.com/Forest.html < A forest is an acyclic graph. Forests therefore consist only of (possibly disconnected) trees, hence the name "forest." >

2022-12-17
shortest-path tree
BFS(breadth-first_search)로 방문한 앞부분들, 즉 root 에서 가장 가까운 부분의 부분트리,subtree? notsure. rechk (Menczer p47)
subtree
planted_tree
{
root(root vertex)의 degree(vertex degree)가 1인 rooted tree.
https://mathworld.wolfram.com/PlantedTree.html
Up: rooted_tree
}

}


트리의 특징
//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을 포함하게 된다.
  • $|E|=|V|-1$ 을 만족한다.

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

Google:segment.tree
}
trie = digital tree = prefix tree
{
= digital_tree = prefix_tree
트리 or 트라이? tbd
Namu:트라이
Google:trie
}
parse_tree
{
파스 트리,


expression_tree { 식,expression 트리,tree } 와?
parse tree는 비교적 간단한 expression tree의 확장(extension). (Weiss C)

Google:parse.tree
}
결정트리,decision_tree - 작성중
게임트리,game_tree - writing
syntax_tree
Q1 혹시 AST와동의어? 아님 abstract하지 않은 s.t.가 있는지?
Q2 위 parse_tree 와 관계?
AST,abstract_syntax_tree
http://foldoc.org/syntax tree
derivation_tree - writing




↑↓merge


Sub:
이진트리,binary_tree
rel. 이진탐색 or 이진검색 binary_search
mkl. 이진힙,binary_heap
balanced_tree - 작성중
search_tree - 작성중
B-tree - 작성중 (pagename TBD)
B+-tree - 작성중 (pagename TBD)
splay_tree - 작성중 WtEn:splay_tree
Fibonacci_tree
Merkle_tree = hash_tree
threaded_tree
multiway_tree
각 node가 임의의 수의 child(ren)를 가질 수 있는 tree.
https://xlinux.nist.gov/dads/HTML/multiwaytree.html
Google:multiway_tree
k-ary_tree
ary가 arity 얘기 맞는지 chk. mklink: arity
각 node가 k개를 초과하는 child(ren)를 가질 수 없는 tree. (i.e. 각 node가 최대 k개의 child(ren)을 가지는 tree.)
https://xlinux.nist.gov/dads/HTML/karyTree.html
Wikipedia에선 m-ary tree.
https://en.wikipedia.org/wiki/M-ary_tree

AST,abstract_syntax_tree

spanning_tree
{
...의 부분그래프,subgraph이면서 모든 vertex를 cover(포함?)하지만 cycle은 포함하지 않는?
순환,cycle

Semi-twins:
'수학백과: 수형도'([https]수학백과: 수형도)의 section 3 참조
{
(graph is connected) ⇔ (graph has its 생성수형도)
}



minimal과 minimum이 둘 다 쓰이나??
'수학백과: 수형도'([https]수학백과: 수형도)의 section 3에서는 minimum


}
Minimal Spanning Tree(최소신장트리) minimal_spanning_tree ? 작성중인곳은 minimum_spanning_tree - 같은지 체크. 암튼 둘다 MST - 그래프,graph일부에서 트리를 만들어 내는 것?
모든 정점을 포함
순환,cycle을 포함하면 x
모든 간선의 가중치가 최소 (그래서 minimal)
방법: Kruskal_algorithm , Prim_algorithm


수형도 tree_diagram
DOM_tree - DOM,Document_Object_Model tree

Topics:
Compare:
그래프,graph 이론 graph_theory 의 tree는, see WpEn:Tree_(graph_theory) interwiki ko: WpKo:나무_그래프 - 순환,cycle을 갖지 않는 connected graph
유사점/차이점 정리 TBW

etc
논리학(논리,logic)에 진리나무,truth_tree(tmp cur. RR:진리나무,truth_tree)
생물학,biology계통수,phylogenetic_tree



WpKo:나무_그래프 WpEn:Tree_(graph_theory) graph_theory 쪽. 수학적.
WpKo:트리_구조 WpEn:Tree_(data_structure) 자료구조,data_structure쪽.

[https]수학백과: 수형도 (tree)
숲(forest), 생성수형도(spanning_tree), 최소생성수형도(minimum_spanning_tree, MST) 언급.
MST를 찾는 알고리듬 중 Kruskal_algorithm, Prim_algorithm 언급.
차수(번역?)가 1인 꼭짓점 = 매달린 꼭짓점(pendant vertex) = 잎(leaf).
[https]두산백과: 수형도 (tree diagram)