Operations
- 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을 돌려줌.
from ods-python.pdf p.20
}
sorted_set
{
sset
ordered_set과 같은건가?
1. disjoint set ¶
disjoint set, union-find, merge-find
disjoint-set data structure, union–find data structure, merge–find set
// tmp from
신찬수 union-find 자료구조 1/2(https://www.youtube.com/watch?v=GaET9oHzC3Q&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=35&ab_channel=Chan-SuShin)
{
기본연산
원형 양방향 연결리스트 circular_linked_list
bidirectional linked list ? 로 구현하는걸 잠시 알아보는데 find() 연산이 O(n)이라 부적합하다고.
트리,tree로 표현하면 더 좋다
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연산을 할 때, 노드 개수가 적은 트리의 루트를 노드 개수가 많은 트리의 루트의 자식 노드로 한다.
이 때는 루트마다 노드 수에 대한 정보가 필요.
}
1.2. find operation ¶
경로압축을 안하면 대체적으로 O(log n), 하면 대체적으로 constant time? (O(1)은 아니지만 대체적으로 그에 가깝다고 - chk)
}
히프/더미/힙
대부분 binary_heap 임을 가정하고 설명하는 듯
이하 binary heap을 가정.
heap order property - 각 node(의 key)는 both children(의 key)보다 항상 크다 or 작다.
heap shape property -
complete_binary_tree 이며 마지막 level에서는 왼쪽부터만 채워진.
(0-indexed를 가정)
Heap size가
이면,
internal nodes의 범위:
leaves의 범위:
// tmp, chk, via
신찬수(https://www.youtube.com/watch?v=6VMSTOdHRfI&list=PLsMufJgu5933ZkBCHS7bQTx0bncjwi4PK&index=22&ab_channel=Chan-SuShin)
{
heap의 높이가
라 하면
이며
heapify_down operation :
make_heap operation :
}
그리고 heap을 하나씩 모두 꺼내는 게
이니
힙정렬,heap_sort의 복잡도는
2.1. min heap / max heap ¶
2.2. heap property ¶
Root node must be less/greater than all subnodes(recursively) - chk
2.3. actions/methods ¶
insert와 delete시 heap property를 보존하기 위한 행동이 일어남 - 그외에? 그리고 O(log n) ? chk
추가/삽입 연산시 맨 마지막에 추가된 다음 위로 올라가는
(percolate up, trickle up, bubble up)
삭제 연산시 루트를 삭제하고 루트 자리에 맨 마지막을 옮겨오고 아래로 내려가는
(percolate down, trickle down, down heap?)
보통 구현을 보면 max_heapify는 largest(largest element's index)라는 변수 이름을 씀
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
from ods-python.pdf p.20
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를 기반으로 함
linear_hashing
linear_hashing
4. Algorithms associated with data structures ¶
5. Persistent data structure ¶
6. 크기의 유한/무한에 따라 ¶
유한한 건 bounded?
via
Coinduction 앞부분 "Coinductively defined types are known as codata and are typically infinite data structures, such as streams."
}