추상자료형,abstract_data_type,ADT 페이지를 따로 만들 것인가 여기 적을 것인가...tbd
겹치는 게 워낙 많아서
Q: vector/tuple/array의 차이는 무엇인가?타입,type페이지에 있어야 하나?
현재는 수학 내용만 있음 - 벡터,vector 튜플,tuple 배열,array{2-D 배열은 행렬,matrix과 밀접. dense/sparse가 있음.}
문자열,string 이건 type인가 data_structure인가?현재는 수학 내용만 있음 - 벡터,vector 튜플,tuple 배열,array{2-D 배열은 행렬,matrix과 밀접. dense/sparse가 있음.}
Sub:
그래프,graph
트리,tree
큐,queue
리스트,list
집합,set에 포함시킬까 아님 비순서집합,unordered_set 페이지에 자료구조 내용을 적을까?
{
uset
그래프,graph
트리,tree
red-black_tree { red-black tree red-black_tree } // "red-black tree" red-black tree
AVL_tree { AVL tree AVL_tree } // "AVL 트리" AVL 트리 AVL 트리 "AVL tree" AVL tree
스택,stackAVL_tree { AVL tree AVL_tree } // "AVL 트리" AVL 트리 AVL 트리 "AVL tree" AVL tree
큐,queue
리스트,list
집합,set에 포함시킬까 아님 비순서집합,unordered_set 페이지에 자료구조 내용을 적을까?
{
uset
Operations
}
sorted_set
{
sset
- size() or length()
- add(x)
x와 값이 같은 y가 없으면 추가
Return true if x was added to the set and false otherwise.
- remove(x)
x와 같은 y가 있다면, y를 삭제하고 y를 돌려줌.
y가 없다면 nil을 돌려줌.
- find(x)
x와 같은 y가 있다면, y를 돌려줌.
없다면 nil을 돌려줌.
}
sorted_set
{
sset
ordered_set과 같은건가?
Contents
1. disjoint set ¶
disjoint_set data structure
disjoint set, union-find, merge-find
disjoint-set data structure, union–find data structure, merge–find set
disjoint-set data structure, union–find data structure, merge–find set
// tmp from 신찬수 union-find 자료구조 1/2
{
기본연산
{
기본연산
- make_set(x) -
- find(x) : x가 속한 집합에 대한 membership_function? -
- union(x, y) -
트리,tree로 표현하면 더 좋다
root_node는 포인터로는 자기 자신을 가리킨다.
root node의 원소는 집합을 대표하는 '대표 원소'역할을 한다.
find() 연산은 '대표 원소'를 찾아 돌려준다.
find() 연산은 트리의 높이 에 대해 복잡도.
}
// tmp from 신찬수 union-find 자료구조 2/2
{
merge(=union)연산을 tree로 구현할 때,
합병 후 tree를 height를 낮추는 게 좋으므로, (당연)
높이가 더 낮은 tree의 root가 다른쪽의 root를 가리키도록 합병되는게 합병 후의 height를 낮출 수 있다.
}
root_node는 포인터로는 자기 자신을 가리킨다.
root node의 원소는 집합을 대표하는 '대표 원소'역할을 한다.
find() 연산은 '대표 원소'를 찾아 돌려준다.
find() 연산은 트리의 높이 에 대해 복잡도.
}
// tmp from 신찬수 union-find 자료구조 2/2
{
merge(=union)연산을 tree로 구현할 때,
합병 후 tree를 height를 낮추는 게 좋으므로, (당연)
높이가 더 낮은 tree의 root가 다른쪽의 root를 가리키도록 합병되는게 합병 후의 height를 낮출 수 있다.
}
1.1. union operation ¶
가중치 법칙
가중치 법칙을 써서 tree의 height가 너무 높아지지 않도록 할 수 있다 (heuristic) - 높이 최소화 방법
union연산을 할 때, 노드 개수가 적은 트리의 루트를 노드 개수가 많은 트리의 루트의 자식 노드로 한다.
이 때는 루트마다 노드 수에 대한 정보가 필요.
가중치 법칙을 써서 tree의 height가 너무 높아지지 않도록 할 수 있다 (heuristic) - 높이 최소화 방법
union연산을 할 때, 노드 개수가 적은 트리의 루트를 노드 개수가 많은 트리의 루트의 자식 노드로 한다.
이 때는 루트마다 노드 수에 대한 정보가 필요.
}
1.2. find operation ¶
find연산에 의한 경로압축,path_compression: find연산 수행시 경로,path의 모든 노드가 루트를 가리키도록 변경
여기에 아커만_함수,Ackermann_function의 역함수,inverse_function(즉 매우 느리게 증가하는 함수)가 나오는데 tbw
여기에 아커만_함수,Ackermann_function의 역함수,inverse_function(즉 매우 느리게 증가하는 함수)가 나오는데 tbw
경로압축을 안하면 대체적으로 O(log n), 하면 대체적으로 constant time? (O(1)은 아니지만 대체적으로 그에 가깝다고 - chk)
}
}
2. heap ¶
히프/더미/힙
대부분 binary_heap 임을 가정하고 설명하는 듯
이하 binary heap을 가정.
이하 binary heap을 가정.
heap order property - 각 node(의 key)는 both children(의 key)보다 항상 크다 or 작다.
heap shape property - complete_binary_tree 이며 마지막 level에서는 왼쪽부터만 채워진.
heap shape property - complete_binary_tree 이며 마지막 level에서는 왼쪽부터만 채워진.
(0-indexed를 가정)
Heap size가 이면,
{
heap의 높이가 라 하면
이며
heapify_down operation :
make_heap operation :
}
그리고 heap을 하나씩 모두 꺼내는 게 이니
힙정렬,heap_sort의 복잡도는
Heap size가 이면,
internal nodes의 범위:
leaves의 범위:
// tmp, chk, via 신찬수leaves의 범위:
{
heap의 높이가 라 하면
이며
heapify_down operation :
make_heap operation :
}
그리고 heap을 하나씩 모두 꺼내는 게 이니
힙정렬,heap_sort의 복잡도는
2.3. actions/methods ¶
- 삽입/insert/ enqueue? -
- 삭제/delete/pop/extract dequeue?
delete_max / delete_min -
- find_max / find_min - root node가 대상인데 -
make_heap 을 하기 위해선 heapify_down 연산을 해야 한다 ? (신찬수 https://www.youtube.com/watch?v=6VMSTOdHRfI)
추가/삽입 연산시 맨 마지막에 추가된 다음 위로 올라가는
(percolate up, trickle up, bubble up)
(percolate up, trickle up, bubble up)
삭제 연산시 루트를 삭제하고 루트 자리에 맨 마지막을 옮겨오고 아래로 내려가는
(percolate down, trickle down, down heap?)
(percolate down, trickle down, down heap?)
3. map / dictionary / hash / hashing ¶
이름을 해시,hash 혹은 해싱,hashing 둘 중에.
사전,dictionary or map, hash, hashtable, hashmap, hashing (table이라고도.. ie lookup_table ?)
{
key와 value로 이루어진 pair (k, v)를 unordered_set으로 정의
두 pair들의 key가 같다면 equal
사전,dictionary or map, hash, hashtable, hashmap, hashing (table이라고도.. ie lookup_table ?)
{
key와 value로 이루어진 pair (k, v)를 unordered_set으로 정의
두 pair들의 key가 같다면 equal
from ods-python.pdf p.20
see also 사상,map
3.1. KU황인준, db, tmp ¶
static_hashing
dynamic_hashing dynamic_hashing
dynamic_external_hashing
extendible_hashing extendible_hashing
- 파일,file에 (별도의?) 추가적 access structure(aka directory ... QQQ FS의 directory와 관계가? 대충, global_depth(기호 d)가 d이면 2d개의 entry 사용 가능... cmp: local_depth. 기호 d'. local depth는 global depth보다 클 수 없음.)를 사용
- based on the result of the hash function to the search_field
- 인덱스,index와 비슷하지만 search_field를 기반으로 함
- access structure가 필요없음
- 해시함수,hash_functions들의 sequence에 기반
4. Algorithms associated with data structures ¶
insertion - 삽입,insertion
deletion
searching - 검색,search? 검색알고리즘,search_algorithm? 탐색?
merging
sorting
traversal - 순회,traversal
deletion
searching - 검색,search? 검색알고리즘,search_algorithm? 탐색?
merging
sorting
traversal - 순회,traversal
5. Persistent data structure ¶
바뀔 때 옛 버전을 하상 보존(preserve)하는 자료구조. 방법은 COW,copy-on-write, fat node, path copying, ...
Persistent_data_structure
Persistent_data_structure
6. 크기의 유한/무한에 따라 ¶
유한한 건 bounded?
MKLINK
codata { 코데이터.. 쌍대자료? coinductively defined type. MKLINK: coinduction 정의,definition 자료,data 데이터,data }
codata { 코데이터.. 쌍대자료? coinductively defined type. MKLINK: coinduction 정의,definition 자료,data 데이터,data }
via Coinduction 앞부분 "Coinductively defined types are known as codata and are typically infinite data structures, such as streams."
}
}
7. Links ¶
Advanced Data Structures, a graduate class at MIT
6.851: Advanced Data Structures
Prof. Erik Demaine
http://courses.csail.mit.edu/6.851/
6.851: Advanced Data Structures
Prof. Erik Demaine
http://courses.csail.mit.edu/6.851/
Twins:
https://mathworld.wolfram.com/DataStructure.html
DataStructures
CategoryDataStructure
http://www.linfo.org/data_structure.html - 참고하여 분류 mk
https://everything2.com/title/data structure (tmp)
https://mathworld.wolfram.com/DataStructure.html
DataStructures
CategoryDataStructure
http://www.linfo.org/data_structure.html - 참고하여 분류 mk
https://everything2.com/title/data structure (tmp)
Up: 전산학,compsci