#noindex
(logic)
Sub:
[[진리나무,truth_tree]]
[[게임트리,game_tree]]
----
tree의 [[노드,node]]들은 여러가지가 있는데
 [[잎,leaf]] 등등
----
[[탐색트리,search_tree]]
[[search_tree]] =,search_tree =,search_tree . search_tree
{
서치트리
탐색트리 ... [[탐색,search]] - 이게 최선?
검색트리 ... [[검색,search]]

암튼 search를 위해 - 그 성능을 유지하기 위해 - (= search time을 최소화하기 위해 )
 * balance를 맞춘다/유지한다 - balanced_tree

WtEn:search_tree ?
Srch:search_tree

Sub:
이진탐색트리 [[binary_search_tree]] =,binary_search_tree =,binary_search_tree . binary_search_tree (BST) =,BST .
{

Sub:
self-balancing_binary_search_tree
{
https://ko.wikipedia.org/wiki/자가_균형_이진_탐색_트리
https://en.wikipedia.org/wiki/Self-balancing_binary_search_tree
https://ja.wikipedia.org/wiki/平衡二分探索木
 평형이분탐색목
}

rel.
[[이진탐색,binary_search]] or binary_search_algorithm
{
linear_search 보다 좋다.. why? tbw.
https://ko.wikipedia.org/wiki/이진_검색_알고리즘
https://simple.wikipedia.org/wiki/Binary_search
https://en.wikipedia.org/wiki/Binary_search_algorithm
}

[[randomized_binary_search_tree]] =,randomized_binary_search_tree . randomized_binary_search_tree
[[treap]] =,treap . treap
{
https://en.wikipedia.org/wiki/Treap
 (TOC전까지, [[Date(2023-11-16T10:33:49)]]
 "In computer science, the '''treap and the randomized binary search tree''' are two closely related forms of binary_search_tree data structures that maintain a dynamic set of ordered keys and allow binary searches among the keys.
 After any sequence of insertions and deletions of keys, the shape of the tree is a random variable with the same probability distribution as a random binary tree; in particular, with high probability its height is proportional to the logarithm of the number of keys, so that each search, insertion, or deletion operation takes logarithmic time to perform.")
}

[[WpEn:Binary_search_tree]]
= https://en.wikipedia.org/wiki/Binary_search_tree

... Google:binary.search.tree Naver:binary.search.tree
}

WpEn:Search_tree
 = https://en.wikipedia.org/wiki/Search_tree
... Google:search.tree Naver:search.tree
}
----
[[red-black_tree]] =,red-black_tree =,red-black_tree . red-black_tree
{

WtEn:red-black_tree

https://everything2.com/title/Red+Black+Tree

... Google:red-black.tree Naver:red-black.tree
}
----
[[이진트리,binary_tree]] =이진트리,binary_tree =,binary_tree 이진트리 binary_tree
{
[[balanced_binary_tree]] =,balanced_binary_tree =,balanced_binary_tree . balanced_binary_tree
 balanced binary tree
 균형이진트리 ?
 번역가능한건 평형 균형 높이균형 ... 균형에 height-balanced 를 강조하는게 있네? 그럼 balance될 수 있는 게 다른 대상이 있나?
 the left and right branches of every item differ in height by no more than 1.
 https://xlinux.nist.gov/dads/HTML/balancedbitr.html
 // no wten
[[complete_binary_tree]] =,complete_binary_tree =,complete_binary_tree . complete_binary_tree
 완전이진트리 ?
 every level, except possibly the last, is completely filled, and all items in the last level are as far left as possible.
 마지막 level을 제외한 level에 node가 가득 차 있다. 마지막 level의 node들은 가장 왼쪽부터 채워진다.
 [[이진힙,binary_heap]] 만들 때 쓰임.
 is a [[완전트리,complete_tree]]
 구현에 [[배열,array]]를 쓰면 편하다.
 https://xlinux.nist.gov/dads/HTML/completeBinaryTree.html
full_binary_tree .... 전체이진트리 ?????
 every item has either 0 or 2 children.
 WtEn:full_binary_tree
 https://xlinux.nist.gov/dads/HTML/fullBinaryTree.html
perfect_binary_tree
 full_binary_tree 이면서 모든 leaf nodes의 depth가 같다.
 가장 아래(깊은) depth(level)의 node들은 child가 없고(0), 그 외의 모든 node들은 child가 두 개다.(2)
 완벽이진트리 ?
 all interior items have two children and all leaves have the same depth or same level. A perfect binary tree is also a full and complete binary tree.
 모든 internal node가 두 children을 가지고, 모든 leaf 노드가 같은 level에 있다.
 https://xlinux.nist.gov/dads/HTML/perfectBinaryTree.html

threaded_binary_tree
 threaded binary tree
 스레드 이진 트리 - wk
 대충 사용되지 않는 leaf node의 오른쪽 child에 대한 null_pointer 를 활용해서 ....?? chk
 https://ko.wikipedia.org/wiki/스레드_이진_트리
 https://en.wikipedia.org/wiki/Threaded_binary_tree
 Bing:"threaded binary tree"
 Ggl:"threaded binary tree"
 "threaded binary tree"

Cartesian_tree
https://en.wikipedia.org/wiki/Cartesian_tree

extended binary tree
extended_binary_tree
WtEn:extended_binary_tree ?
WpEn:Extended_binary_tree ?
## via:
https://mathworld.wolfram.com/ExtendedBinaryTree.html

Twin

[[WtEn:binary_tree]]

https://xlinux.nist.gov/dads/HTML/binarytree.html

[[WpSimple:Binary_tree]]
= https://simple.wikipedia.org/wiki/Binary_tree

[[WpKo:이진_트리]]
= https://ko.wikipedia.org/wiki/이진_트리

[[MathWorld:BinaryTree]] = https://mathworld.wolfram.com/BinaryTree.html

... Google:이진트리 Ndict:이진트리 Naver:이진트리 Google:binary.tree
}
----
[[힙,heap]] - [[VG:힙,heap]]
{
[[트리,tree]] 중에서 heap_property { Google:heap_property  } 를 만족하는 것.

max heap과 min heap이 있다

[[우선순위큐,priority_queue]]구현에 자주쓰이는듯한데 저기에쓰이는 다른거? QQQ

Sub:
[[이진힙,binary_heap]]
{
... Google:binary.heap Naver:binary+heap
}

[[WpSimple:Heap_(data_structure)]]
 = https://simple.wikipedia.org/wiki/Heap_%28data_structure%29
}
----
[[spanning_tree]] =,spanning_tree =,spanning_tree . spanning_tree
 WtEn:spanning_tree

 스패닝트리 신장트리 ... pagename?

 MKLINK
 spanning_subgraph { WpKo:신장_부분_그래프 = https://ko.wikipedia.org/wiki/신장_부분_그래프 https://proofwiki.org/wiki/Definition:Spanning_Subgraph ... Google:spanning.subgraph  }
 spanning_forest { ... Google:spanning.forest }
 Twins:
 WpEn:Spanning_tree = https://en.wikipedia.org/wiki/Spanning_tree
 ... Google:spanning+tree Naver:spanning+tree
 minimum_spanning_tree MST
 https://proofwiki.org/wiki/Definition:Minimum_Spanning_Tree
 ... Google:minimum.spanning.tree
 maximum_spanning_tree
 [[Kruskal_algorithm]]
 https://mathworld.wolfram.com/MaximumSpanningTree.html
 https://proofwiki.org/wiki/Definition:Maximum_Spanning_Tree
 ... Google:maximum.spanning.tree
----
[[parse_tree]] =,parse_tree =,parse_tree . parse_tree
{
AKA : parse_tree or parsing_tree or derivation_tree or concrete_syntax_tree[* WpEn:Parse_tree 첫 문장]
syntax_tree 와 동의어일 수 있음

속성
[[ordered_tree]]
[[rooted_tree]] =,rooted_tree =,rooted_tree . rooted_tree
{
WtEn:rooted_tree ?
Srch:rooted_tree
}


MKLINK
[[abstract_syntax_tree]]
[[parsing]]
[[컴파일러,compiler]]
[[컴파일,compile]]
[[syntax_tree]]

WtEn:parse_tree

[[WpKo:파스_트리]]
 = https://ko.wikipedia.org/wiki/파스_트리

[[WpEn:Parse_tree]]
 = https://en.wikipedia.org/wiki/Parse_tree

<<footnote>>
}
----
[[abstract_syntax_tree]] =,abstract_syntax_tree =,abstract_syntax_tree . abstract_syntax_tree =,AST .
{
AKA: abstract syntax tree (AST), or just syntax_tree (wpen) 또는 간단히 구문트리,syntax_tree (wpko)

[[WpKo:추상_구문_트리]]
 = https://ko.wikipedia.org/wiki/추상_구문_트리

WpEn:Abstract_syntax_tree
 = https://en.wikipedia.org/wiki/Abstract_syntax_tree
}

[[semantic_resolution_tree]] =,semantic_resolution_tree =,semantic_resolution_tree . semantic_resolution_tree
{
semantic resolution tree

[[의미론,semantics]]

WpSimple:Semantic_resolution_tree
 = https://simple.wikipedia.org/wiki/Semantic_resolution_tree
WpEn:Semantic_resolution_tree
 = https://en.wikipedia.org/wiki/Semantic_resolution_tree
 "is a tree used for the definition of the semantics of a programming language"
... Google:Semantic.resolution.tree
}
----
AVL트리
AVL_tree

=,AVL_tree =,AVL_tree . AVL_tree
{

https://rosettacode.org/wiki/AVL_tree

WtEn:AVL_tree

https://everything2.com/title/AVL+tree

... Google:AVL+tree Naver:AVL+tree
}
----
[[B트리,B-tree]] ?
=,B-tree .

https://xlinux.nist.gov/dads/HTML/btree.html
----
[[BSP_tree]] =,BSP_tree . BSP_tree
[[binary_space_partitioning_tree]] =,binary_space_partitioning_tree =,binary_space_partitioning_tree . binary_space_partitioning_tree

is about: [[space_partitioning]] > [[binary_space_partitioning]]

[[computer_graphics]] esp 3D, [[game_development]] 에서 잘 쓰이는? chk

https://everything2.com/title/BSP+Tree
https://everything2.com/title/Binary+Space-Partitioning+Tree

Ggl:BSP+Tree
Bing:BSP+Tree
Naver:BSP+Tree
BSP+Tree
----
----
ADDHERE
----
[[pseudotree]] =,pseudotree =,pseudotree . pseudotree - writing
{
유사트리 ?

~~WtEn:pseudotree~~

MKLINK
[[pseudoforest]] - writing
{
유사숲 ?
유사포레스트 ?
유사포리스트 ?

undirected_graph 인데 모든 연결된 component가 최대 한 개의 [[순환,cycle]]을 가진?

//wpen
"an undirected graph in which every connected component has at most one cycle"

[[WpEn:Pseudoforest]]
 = https://en.wikipedia.org/wiki/Pseudoforest

... Google:Pseudoforest Naver:Pseudoforest

Up: undirected_graph
}

... Google:pseudotree Naver:pseudotree
}
----
Topics
[[루트,root]] = root_node
 rooted_graph
[[노드,node]]
[[버텍스,vertex]] or 꼭지점,vertex or 정점,vertex .... [[점,point]]과 비슷?
[[에지,edge]] { [[WpEn:Glossary_of_graph_theory#edge]] }
parent
child
[[그래프,graph]]
트리그래프 나무그래프 tree_graph .... 이걸그냥 이페이지 [[트리,tree]]에 합병?
{
[[순환,cycle]]을 갖지 않는 [[연결그래프,connected_graph]]. (wpko)
WpKo:나무_그래프
 = https://ko.wikipedia.org/wiki/나무_그래프
... Google:tree.graph
}

숲그래프 포리스트그래프  forest_graph 
{
... Google:forest.graph
}

----
(CS)

[[트리순회,tree_traversal]] - [[순회,traversal]] ... [[순서,order]]가 중요
=트리순회,tree_traversal =,tree_traversal 트리순회 tree_traversal
{

https://ko.wikipedia.org/wiki/트리_순회
 preorder = DFS
 inorder = symmetric traversal
 postorder
 level-order = BFS

https://en.wikipedia.org/wiki/Tree_traversal
 "'''tree traversal''' (also known as '''[[tree_search]]''' and '''walking the tree''')"
 Sub:
 depth-first order search/traversal (DFS) uses [[스택,stack]]
 breadth-first order search/traversal  (BFS) uses [[큐,queue]]
 depth-limited search
 iterative deepening depth-first search

}
[[가지치기,pruning]]
[[식트리,expression_tree]] - w [[식,expression]]의 [[표현,representation]]방법 중 하나? 나중에 [[평가,evaluation]]하게 되는...?
{
##===식트리,expression_tree =,expression_tree . expression_tree
[[수식트리,mathematical_expression_tree]]
 {
 [[수식,mathematical_expression]] [[트리,tree]]
 }
}
[[루트,root]] - root_node ?

[[ordered_tree]] =,ordered_tree =,ordered_tree . ordered_tree
{
[[순서,order]] 있는 [[트리,tree]]

}

[[free_tree]] = [[unrooted_tree]]
{
free tree
unrooted tree

opp. [[rooted_tree]]

https://mathworld.wolfram.com/FreeTree.html
} // free tree = unrooted tree

ADDHERE
ADDHERE
ADDHERE

----
tree의 용어들 정리 todo.

참조:

[[WpEn:Tree_(data_structure)#Terminology]]
https://en.wikipedia.org/wiki/Tree_(data_structure)#Terminology

----
set_theory([[집합,set]]) order_theory([[순서,order]])에서

poset의 일종.
[[WpKo:나무_(집합론)]] = https://ko.wikipedia.org/wiki/나무_%28집합론%29
[[WpEn:Tree_(set_theory)]] = = https://en.wikipedia.org/wiki/Tree_%28set_theory%29

----
VG [[VG:트리,tree]]

[[나무,tree]](같은 영단어 tree 다른 한국어)의 용도는 뭐라 할까? pagerole tbd

[[그래프이론,graph_theory]]의 [[그래프,graph]]의 일종임

[[computation_tree_logic]]

cmp: [[위계,hierarchy]]

----
[[WpSp:Tree_(data_structure)]]
[[WpEn:Tree_(data_structure)]] (DS, ADT)
 [[WpKo:트리_구조]]


[[WpEn:Tree_(set_theory)]]
 [[WpKo:나무_(집합론)]] ([[집합,set]] [[집합론,set_theory]])

[[WpEn:Tree_(descriptive_set_theory)]] ([[descriptive_set_theory]])


https://xlinux.nist.gov/dads/HTML/tree.html

https://everything2.com/title/tree+structure
 Q1 tree와 tree structure 는 equiv? i.e. tree is a [[구조,structure]]?
 그렇다면 tree가 다른 뭔가랑 겹친다면 pagename을 [[tree_structure]]로 할 수도..

----
(misc, 실제 나무)
표현
sapling n. 묘목, 어린 나무