탐색트리,search_tree
search_tree =,search_tree =,search_tree . search_tree
{
서치트리
탐색트리 ... 탐색,search - 이게 최선?
검색트리 ... 검색,search
search_tree =,search_tree =,search_tree . search_tree
{
서치트리
탐색트리 ... 탐색,search - 이게 최선?
검색트리 ... 검색,search
암튼 search를 위해 - 그 성능을 유지하기 위해 - (= search time을 최소화하기 위해 )
search_tree
- balance를 맞춘다/유지한다 - balanced_tree
search_tree
Sub:
이진탐색트리 binary_search_tree =,binary_search_tree =,binary_search_tree . binary_search_tree (BST) =,BST .
{
이진탐색트리 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/平衡二分探索木
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
}
이진탐색,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
treap =,treap . treap
{
https://en.wikipedia.org/wiki/Treap
(TOC전까지, 2023-11-16
"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.")
}"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.")
이진트리,binary_tree =이진트리,binary_tree =,binary_tree 이진트리 binary_tree
{
balanced_binary_tree =,balanced_binary_tree =,balanced_binary_tree . balanced_binary_tree
https://en.wikipedia.org/wiki/Cartesian_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균형이진트리 ?
번역가능한건 평형 균형 높이균형 ... 균형에 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
완전이진트리 ?
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 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
every item has either 0 or 2 children.
full_binary_tree
https://xlinux.nist.gov/dads/HTML/fullBinaryTree.html
perfect_binary_treefull_binary_tree
https://xlinux.nist.gov/dads/HTML/fullBinaryTree.html
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가장 아래(깊은) 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
스레드 이진 트리 - wk
대충 사용되지 않는 leaf node의 오른쪽 child에 대한 null_pointer 를 활용해서 ....?? chk
https://ko.wikipedia.org/wiki/스레드_이진_트리
https://en.wikipedia.org/wiki/Threaded_binary_tree
threaded binary tree
threaded binary tree
"threaded binary tree"
Cartesian_tree스레드 이진 트리 - wk
대충 사용되지 않는 leaf node의 오른쪽 child에 대한 null_pointer 를 활용해서 ....?? chk
https://ko.wikipedia.org/wiki/스레드_이진_트리
https://en.wikipedia.org/wiki/Threaded_binary_tree
threaded binary tree
threaded binary tree
"threaded binary tree"
https://en.wikipedia.org/wiki/Cartesian_tree
extended binary tree
extended_binary_tree
extended_binary_tree ?
Extended_binary_tree ?
https://mathworld.wolfram.com/ExtendedBinaryTree.html
extended_binary_tree
extended_binary_tree ?
Extended_binary_tree ?
https://mathworld.wolfram.com/ExtendedBinaryTree.html
Twin
max heap과 min heap이 있다
우선순위큐,priority_queue구현에 자주쓰이는듯한데 저기에쓰이는 다른거? QQQ
spanning_tree =,spanning_tree =,spanning_tree . spanning_tree
spanning_tree
스패닝트리 신장트리 ... pagename?
MKLINK
spanning_subgraph { 신장_부분_그래프 = https://ko.wikipedia.org/wiki/신장_부분_그래프 https://proofwiki.org/wiki/Definition:Spanning_Subgraph ... spanning.subgraph }
spanning_forest { ... spanning.forest }
Twins:
Spanning_tree = https://en.wikipedia.org/wiki/Spanning_tree
... spanning tree spanning tree
minimum_spanning_tree MST
https://proofwiki.org/wiki/Definition:Minimum_Spanning_Tree
... minimum.spanning.tree
maximum_spanning_tree
Kruskal_algorithm
https://mathworld.wolfram.com/MaximumSpanningTree.html
https://proofwiki.org/wiki/Definition:Maximum_Spanning_Tree
... maximum.spanning.tree
스패닝트리 신장트리 ... pagename?
MKLINK
spanning_subgraph { 신장_부분_그래프 = https://ko.wikipedia.org/wiki/신장_부분_그래프 https://proofwiki.org/wiki/Definition:Spanning_Subgraph ... spanning.subgraph }
spanning_forest { ... spanning.forest }
Twins:
Spanning_tree = https://en.wikipedia.org/wiki/Spanning_tree
... spanning tree spanning tree
minimum_spanning_tree MST
https://proofwiki.org/wiki/Definition:Minimum_Spanning_Tree
... minimum.spanning.tree
maximum_spanning_tree
Kruskal_algorithm
https://mathworld.wolfram.com/MaximumSpanningTree.html
https://proofwiki.org/wiki/Definition:Maximum_Spanning_Tree
... maximum.spanning.tree
parse_tree =,parse_tree =,parse_tree . parse_tree
{
AKA : parse_tree or parsing_tree or derivation_tree or concrete_syntax_tree[1]
syntax_tree 와 동의어일 수 있음
{
AKA : parse_tree or parsing_tree or derivation_tree or concrete_syntax_tree[1]
syntax_tree 와 동의어일 수 있음
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)
{
AKA: abstract syntax tree (AST), or just syntax_tree (wpen) 또는 간단히 구문트리,syntax_tree (wpko)
semantic_resolution_tree =,semantic_resolution_tree =,semantic_resolution_tree . semantic_resolution_tree
{
semantic resolution tree
{
semantic resolution tree
Semantic_resolution_tree
Semantic_resolution_tree
}
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"
... Semantic.resolution.tree"is a tree used for the definition of the semantics of a programming language"
}
AVL트리
AVL_tree
AVL_tree
=,AVL_tree =,AVL_tree . AVL_tree
{
{
BSP_tree =,BSP_tree . BSP_tree
binary_space_partitioning_tree =,binary_space_partitioning_tree =,binary_space_partitioning_tree . binary_space_partitioning_tree
binary_space_partitioning_tree =,binary_space_partitioning_tree =,binary_space_partitioning_tree . binary_space_partitioning_tree
ADDHERE
undirected_graph 인데 모든 연결된 component가 최대 한 개의 순환,cycle을 가진?
//wpen
"an undirected graph in which every connected component has at most one cycle"
"an undirected graph in which every connected component has at most one cycle"
Up: undirected_graph
}
}
Topics
루트,root = root_node
버텍스,vertex or 꼭지점,vertex or 정점,vertex .... 점,point과 비슷?
에지,edge { Glossary_of_graph_theory#edge }
parent
child
그래프,graph
트리그래프 나무그래프 tree_graph .... 이걸그냥 이페이지 트리,tree에 합병?
{
순환,cycle을 갖지 않는 연결그래프,connected_graph. (wpko)
나무_그래프
... tree.graph
}
루트,root = root_node
rooted_graph
노드,node버텍스,vertex or 꼭지점,vertex or 정점,vertex .... 점,point과 비슷?
에지,edge { Glossary_of_graph_theory#edge }
parent
child
그래프,graph
트리그래프 나무그래프 tree_graph .... 이걸그냥 이페이지 트리,tree에 합병?
{
순환,cycle을 갖지 않는 연결그래프,connected_graph. (wpko)
나무_그래프
... tree.graph
}
(CS)
트리순회,tree_traversal - 순회,traversal ... 순서,order가 중요
=트리순회,tree_traversal =,tree_traversal 트리순회 tree_traversal
{
=트리순회,tree_traversal =,tree_traversal 트리순회 tree_traversal
{
https://ko.wikipedia.org/wiki/트리_순회
가지치기,pruning
식트리,expression_tree - w 식,expression의 표현,representation방법 중 하나? 나중에 평가,evaluation하게 되는...?
{
수식트리,mathematical_expression_tree
}
루트,root - root_node ?
preorder = DFS
inorder = symmetric traversal
postorder
level-order = BFS
https://en.wikipedia.org/wiki/Tree_traversalinorder = symmetric traversal
postorder
level-order = BFS
"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
}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하게 되는...?
{
수식트리,mathematical_expression_tree
}
루트,root - root_node ?
}
opp. rooted_tree
ADDHERE
ADDHERE
ADDHERE
ADDHERE
ADDHERE
tree의 용어들 정리 todo.
참조:
poset의 일종.
나무_(집합론) = https://ko.wikipedia.org/wiki/나무_(집합론)
Tree_(set_theory) = = https://en.wikipedia.org/wiki/Tree_(set_theory)
나무_(집합론) = https://ko.wikipedia.org/wiki/나무_(집합론)
Tree_(set_theory) = = https://en.wikipedia.org/wiki/Tree_(set_theory)
나무,tree(같은 영단어 tree 다른 한국어)의 용도는 뭐라 할까? pagerole tbd
cmp: 위계,hierarchy
Tree_(data_structure)
Tree_(data_structure) (DS, ADT)
Tree_(set_theory)
Tree_(descriptive_set_theory) (descriptive_set_theory)
Tree_(data_structure) (DS, ADT)
Tree_(set_theory)
Tree_(descriptive_set_theory) (descriptive_set_theory)
https://everything2.com/title/tree structure
Q1 tree와 tree structure 는 equiv? i.e. tree is a 구조,structure?
그렇다면 tree가 다른 뭔가랑 겹친다면 pagename을 tree_structure로 할 수도..
그렇다면 tree가 다른 뭔가랑 겹친다면 pagename을 tree_structure로 할 수도..
(misc, 실제 나무)
표현
sapling n. 묘목, 어린 나무
표현
sapling n. 묘목, 어린 나무