나무?
복수개일 경우 숲 forest?
복수개일 경우 숲 forest?
용어정리 시작
{
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
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
{
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.htmlinternal_node = nonterminal_node - https://xlinux.nist.gov/dads/HTML/internalnode.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
Sub: planted_tree
Opp. free_tree //바로아래쪽
https://mathworld.wolfram.com/RootedTree.html
... rooted tree 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
shortest-path tree
{
root(root vertex)의 degree(vertex degree)가 1인 rooted tree.
https://mathworld.wolfram.com/PlantedTree.html
Up: rooted_tree
}
... rooted tree 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-17shortest-path tree
BFS(breadth-first_search)로 방문한 앞부분들, 즉 root 에서 가장 가까운 부분의 부분트리,subtree? notsure. rechk (Menczer p47)
subtree이건 원래 트리,tree의 무엇을? subtree definition을 보면 뜻이 통일된 단어가 아님
https://mathworld.wolfram.com/Subtree.html
https://xlinux.nist.gov/dads/HTML/subtree.html
rel. 부분집합,subset 부분그래프,subgraph
planted_treehttps://mathworld.wolfram.com/Subtree.html
https://xlinux.nist.gov/dads/HTML/subtree.html
rel. 부분집합,subset 부분그래프,subgraph
{
root(root vertex)의 degree(vertex degree)가 1인 rooted tree.
https://mathworld.wolfram.com/PlantedTree.html
Up: rooted_tree
}
}
트리의 특징
그래프,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)
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
- : link의 수 = node의 수 − 1
- 순환,cycle이 없다
- hierarchical (위계,hierarchy)
그래프,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을 포함하게 된다.
- 을 만족한다.
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
segment.tree
}
trie = digital tree = prefix tree
{
= digital_tree = prefix_tree
트리 or 트라이? tbd
트라이
trie
}
parse_tree
{
파스 트리,
}
trie = digital tree = prefix tree
{
= digital_tree = prefix_tree
트리 or 트라이? tbd
트라이
trie
}
parse_tree
{
파스 트리,
expression_tree { 식,expression 트리,tree } 와?
parse tree는 비교적 간단한 expression tree의 확장(extension). (Weiss C)
parse tree는 비교적 간단한 expression tree의 확장(extension). (Weiss C)
parse.tree
}
결정트리,decision_tree - 작성중
게임트리,game_tree - writing
syntax_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 - writingQ2 위 parse_tree 와 관계?
AST,abstract_syntax_tree
http://foldoc.org/syntax tree
↑↓merge
Sub:
{
...의 부분그래프,subgraph이면서 모든 vertex를 cover(포함?)하지만 cycle은 포함하지 않는?
순환,cycle
이진트리,binary_tree
balanced_tree - 작성중
search_tree - 작성중
B-tree - 작성중 (pagename TBD)
B+-tree - 작성중 (pagename TBD)
splay_tree - 작성중 splay_tree
Fibonacci_tree
threaded_tree
multiway_tree
spanning_treebalanced_tree - 작성중
search_tree - 작성중
B-tree - 작성중 (pagename TBD)
B+-tree - 작성중 (pagename TBD)
splay_tree - 작성중 splay_tree
Fibonacci_tree
피보나치_트리
MKLINK Fibonacci_heap
https://xlinux.nist.gov/dads/HTML/fibonacciTree.html
fibonacci.tree
피보나치트리
Merkle_tree = hash_treeMKLINK Fibonacci_heap
https://xlinux.nist.gov/dads/HTML/fibonacciTree.html
fibonacci.tree
피보나치트리
threaded_tree
multiway_tree
각 node가 임의의 수의 child(ren)를 가질 수 있는 tree.
https://xlinux.nist.gov/dads/HTML/multiwaytree.html
multiway_tree
k-ary_treehttps://xlinux.nist.gov/dads/HTML/multiwaytree.html
multiway_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각 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
{
...의 부분그래프,subgraph이면서 모든 vertex를 cover(포함?)하지만 cycle은 포함하지 않는?
순환,cycle
spanning_tree_algorithm - 네트워크,network(fork 네트워킹,networking?)에서.
spanning.tree.algorithm Radia.Perlman
}
minimal_spanning_tree or minimum_spanning_tree ? - TBD ... minimal.spanning.tree minimum.spanning.tree
{
spanning.tree.algorithm Radia.Perlman
}
minimal_spanning_tree or minimum_spanning_tree ? - TBD ... minimal.spanning.tree minimum.spanning.tree
{
}
Minimal Spanning Tree(최소신장트리) minimal_spanning_tree ? 작성중인곳은 minimum_spanning_tree - 같은지 체크. 암튼 둘다 MST - 그래프,graph일부에서 트리를 만들어 내는 것?
Compare:
논리학(논리,logic)에 진리나무,truth_tree(tmp cur. 진리나무,truth_tree)
생물학,biology에 계통수,phylogenetic_tree
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:순환,cycle을 포함하면 x
모든 간선의 가중치가 최소 (그래서 minimal)
방법: Kruskal_algorithm , Prim_algorithm
수형도 tree_diagram
DOM_tree - DOM,Document_Object_Model tree
Compare:
그래프,graph 이론 graph_theory 의 tree는, see Tree_(graph_theory) interwiki ko: 나무_그래프 - 순환,cycle을 갖지 않는 connected graph
etc유사점/차이점 정리 TBW
논리학(논리,logic)에 진리나무,truth_tree(tmp cur. 진리나무,truth_tree)
생물학,biology에 계통수,phylogenetic_tree
Twins:
http://foldoc.org/tree
https://mathworld.wolfram.com/Tree.html
Tree_(data_structure) interwiki ko: 트리_구조
트리(그래프)
http://foldoc.org/tree
https://mathworld.wolfram.com/Tree.html
Tree_(data_structure) interwiki ko: 트리_구조
트리(그래프)
나무_그래프 | Tree_(graph_theory) | graph_theory 쪽. 수학적. |
트리_구조 | Tree_(data_structure) | 자료구조,data_structure쪽. |
수학백과: 수형도 (tree)
숲(forest), 생성수형도(spanning_tree), 최소생성수형도(minimum_spanning_tree, MST) 언급.
두산백과: 수형도 (tree diagram)MST를 찾는 알고리듬 중 Kruskal_algorithm, Prim_algorithm 언급.
차수(번역?)가 1인 꼭짓점 = 매달린 꼭짓점(pendant vertex) = 잎(leaf).