자료구조,data_structure (rev. 1.47)

추상자료형,abstract_data_type,ADT 페이지를 따로 만들 것인가 여기 적을 것인가...tbd

Q: vector/tuple/array의 차이는 무엇인가?

타입,type페이지에 있어야 하나?
현재는 수학 내용만 있음 - 벡터,vector 튜플,tuple 배열,array{2-D 배열은 행렬,matrix과 밀접. dense/sparse가 있음.}

문자열,string 이건 type인가 data_structure인가?

Sub:
그래프,graph
트리,tree
스택,stack
큐,queue

데크,deque or dequeue or double-ended_queues
우선순위큐,priority_queue

리스트,list

연결리스트,linked_list

singly linked list

집합,set에 포함시킬까 아님 비순서집합,unordered_set 페이지에 자료구조 내용을 적을까?
{
uset

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

1.1. union operation
1.2. find operation

2. heap

2.1. min heap / max heap
2.2. heap property
2.3. actions/methods
2.4. heapify

3. map / dictionary / hash / hashing

3.1. KU황인준, db, tmp

4. Algorithms associated with data structures

5. Persistent data structure

6. Links

[edit]

1. disjoint set ¶

disjoint_set data structure

disjoint-set data structure, union–find data structure, merge–find set

집합,set을 트리,tree로 나타냄
i.e.
트리,tree를 이용해 집합,set을 표현
화살표가 항상 parent를 향하고, root가 대표원소인?

MKLINK
부분집합,subset

union find

[edit]

1.1. union operation ¶

union_operation?
{
∪

가중치 법칙
가중치 법칙을 써서 tree의 height가 너무 높아지지 않도록 할 수 있다 (heuristic) - 높이 최소화 방법
union연산을 할 때, 노드 개수가 적은 트리의 루트를 노드 개수가 많은 트리의 루트의 자식 노드로 한다.
이 때는 루트마다 노드 수에 대한 정보가 필요.

}

[edit]

1.2. find operation ¶

find_operation?
{
원소가 속한 부분집합 찾기

find연산에 의한 경로압축,path_compression: find연산 수행시 경로,path의 모든 노드가 루트를 가리키도록 변경
여기에 아커만_함수,Ackermann_function의 역함수,inverse_function(즉 매우 느리게 증가하는 함수)가 나오는데 tbw

경로압축을 안하면 대체적으로 O(log n), 하면 대체적으로 constant time? (O(1)은 아니지만 대체적으로 그에 가깝다고 - chk)
}

https://ratsgo.github.io/data structure&algorithm/2017/11/12/disjointset/

Disjoint-set_data_structure

서로소_집합_자료_구조

[edit]

2. heap ¶

힙,heap

히프/더미/힙

MKLINK
ADT abstract_data_type 우선순위큐,priority_queue

대부분 binary_heap 임을 가정하고 설명하는 듯
이하 binary heap을 가정.

heap order property - 각 node(의 key)는 both children(의 key)보다 항상 크다 or 작다.
heap shape property - complete_binary_tree 이며 마지막 level에서는 왼쪽부터만 채워진.

(0-indexed를 가정)
Heap size가 $n$ 이면,

internal nodes의 범위: $0 \;{\rm to}\; \left\lfloor \frac{n}{2} \right\rfloor-1$
leaves의 범위: $\left\lfloor \frac{n}{2} \right\rfloor \;{\rm to}\; n-1$

[edit]

2.1. min heap / max heap ¶

root가 최소원소 / root가 최대원소

[edit]

2.2. heap property ¶

Root node must be less/greater than all subnodes(recursively) - chk

[edit]

2.3. actions/methods ¶

삽입/insert/ enqueue? - $O(\log n)$
삭제/delete/pop/extract dequeue?

delete_max / delete_min - $O(\log n)$
find_max / find_min - root node가 대상인데 - $O(1)$

insert와 delete시 heap property를 보존하기 위한 행동이 일어남 - 그외에? 그리고 O(log n) ? chk

make_heap 을 하기 위해선 heapify_down 연산을 해야 한다 ? (신찬수 https://www.youtube.com/watch?v=6VMSTOdHRfI)

추가/삽입 연산시 맨 마지막에 추가된 다음 위로 올라가는
(percolate up, trickle up, bubble up)

삭제 연산시 루트를 삭제하고 루트 자리에 맨 마지막을 옮겨오고 아래로 내려가는
(percolate down, trickle down, down heap?)

[edit]

2.4. heapify ¶

보통 구현을 보면 max_heapify는 largest(largest element's index)라는 변수 이름을 씀

분류: complete_tree, binary_heap일 경우 complete_binary_tree - chk ... 자료구조,data_structure

[edit]

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_external_hashing

extendible_hashing

파일,file에 (별도의?) 추가적 access structure(aka directory ... QQQ FS의 directory와 관계가? 대충, global_depth(기호 d)가 d이면 2^d개의 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