트리,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 .
{



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 .... 전체이진트리 ?????
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:나무_그래프
... 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
}
루트,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. 묘목, 어린 나무