트리,tree

Difference between r1.26 and the current

@@ -1,10 +1,14 @@
#noindex
(logic)
Sub:
[[진리나무,truth_tree]]
[[게임트리,game_tree]]
----
tree의 [[노드,node]]들은 여러가지가 있는데
[[잎,leaf]] 등등
----
[[탐색트리,search_tree]]
search_tree
[[search_tree]] =,search_tree =,search_tree . search_tree
{
서치트리
탐색트리 ... [[탐색,search]] - 이게 최선?
@@ -13,8 +17,11 @@
암튼 search를 위해 - 그 성능을 유지하기 위해 - (= search time을 최소화하기 위해 )
* balance를 맞춘다/유지한다 - balanced_tree

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

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

rel.
@@ -33,8 +42,18 @@
https://en.wikipedia.org/wiki/Binary_search_algorithm
}

WpEn:Binary_search_tree
= https://en.wikipedia.org/wiki/Binary_search_tree
[[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
}

@@ -47,6 +66,7 @@
{

WtEn:red-black_tree
https://everything2.com/title/Red+Black+Tree

... Google:red-black.tree Naver:red-black.tree
@@ -71,6 +91,7 @@
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가 같다.
@@ -80,14 +101,41 @@
모든 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/이진_트리

... Google:이진트리 Naver:이진트리 Google:binary.tree
[[MathWorld:BinaryTree]] = https://mathworld.wolfram.com/BinaryTree.html
 
... Google:이진트리 Ndict:이진트리 Naver:이진트리 Google:binary.tree
}
----
[[힙,heap]] - [[VG:힙,heap]]
@@ -108,8 +156,11 @@
= https://simple.wikipedia.org/wiki/Heap_%28data_structure%29
}
----
[[spanning_tree]]
[[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 }
@@ -125,14 +176,19 @@
https://proofwiki.org/wiki/Definition:Maximum_Spanning_Tree
... Google:maximum.spanning.tree
----
[[parse_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 . rooted_tree
{
WtEn:rooted_tree ?
Srch:rooted_tree
}

MKLINK
[[abstract_syntax_tree]]
@@ -141,14 +197,18 @@
[[컴파일,compile]]
[[syntax_tree]]

WpKo:파스_트리
WtEn:parse_tree
 
[[WpKo:파스_트리]]
= https://ko.wikipedia.org/wiki/파스_트리
WpEn:Parse_tree
 
[[WpEn:Parse_tree]]
= https://en.wikipedia.org/wiki/Parse_tree
<<footnote>>
}
----
[[abstract_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)

@@ -159,9 +219,11 @@
= https://en.wikipedia.org/wiki/Abstract_syntax_tree
}

[[semantic_resolution_tree]]
[[semantic_resolution_tree]] =,semantic_resolution_tree =,semantic_resolution_tree . semantic_resolution_tree
{
[[의미론,semantics]] { https://simple.wikipedia.org/wiki/Semantics [[WpEn:Semantics_(computer_science)]] }
semantic resolution tree
 
[[의미론,semantics]]

WpSimple:Semantic_resolution_tree
= https://simple.wikipedia.org/wiki/Semantic_resolution_tree
@@ -171,7 +233,8 @@
... Google:Semantic.resolution.tree
}
----
AVL트리 AVL_tree
AVL트리 
AVL_tree

=,AVL_tree =,AVL_tree . AVL_tree
{
@@ -185,10 +248,35 @@
... Google:AVL+tree Naver:AVL+tree
}
----
[[pseudotree]] - writing
[[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
{
@@ -257,7 +345,14 @@

}
[[가지치기,pruning]]
[[식트리,expression_tree]] - [[식,expression]]의 [[표현,representation]]방법 중 하나? 나중에 [[평가,evaluation]]하게 되는...?
[[식트리,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
@@ -266,6 +361,28 @@

}

[[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]])에서

@@ -276,7 +393,7 @@
----
VG [[VG:트리,tree]]

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

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

@@ -285,13 +402,24 @@
cmp: [[위계,hierarchy]]

----
[[WpKo:]]
[[WpSp:Tree_(data_structure)]]
[[WpEn:Tree_(data_structure)]] (DS, ADT)
[[WpSp:]]
[[WpKo:트리_구조]] 
 
 
[[WpEn:Tree_(set_theory)]]
[[WpKo:나무_(집합론)]] ([[집합,set]] [[집합론,set_theory]])
 
[[WpEn:Tree_(descriptive_set_theory)]] ([[descriptive_set_theory]])

[[WpEn:]]
[[WpEn:]]
[[WpEn:]]
[[WpEn:]]

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. 묘목, 어린 나무


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 .
{



randomized_binary_search_tree =,randomized_binary_search_tree . randomized_binary_search_tree
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.")
}



red-black_tree =,red-black_tree =,red-black_tree . 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


Twin






힙,heap - VG:힙,heap
{
트리,tree 중에서 heap_property { Google:heap_property } 를 만족하는 것.

max heap과 min heap이 있다

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


parse_tree =,parse_tree =,parse_tree . parse_tree
{
AKA : parse_tree or parsing_tree or derivation_tree or concrete_syntax_tree[1]
syntax_tree 와 동의어일 수 있음

속성
ordered_tree
rooted_tree =,rooted_tree =,rooted_tree . rooted_tree
{
WtEn:rooted_tree ?
Srch:rooted_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)


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


AVL트리
AVL_tree

=,AVL_tree =,AVL_tree . AVL_tree
{




B트리,B-tree ?
=,B-tree .

BSP_tree =,BSP_tree . BSP_tree
binary_space_partitioning_tree =,binary_space_partitioning_tree =,binary_space_partitioning_tree . binary_space_partitioning_tree


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


ADDHERE
pseudotree =,pseudotree =,pseudotree . pseudotree - writing
{
유사트리 ?


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

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

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


Up: undirected_graph
}

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하게 되는...?
{
수식트리,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


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

ADDHERE
ADDHERE
ADDHERE

tree의 용어들 정리 todo.

참조:


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



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







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

(misc, 실제 나무)
표현
sapling n. 묘목, 어린 나무
트리,tree Modified on 1:19 pm, May 24, 2024.
🎲 Random