School/DataStructure

Data Structure - Tree ( Heaps )

Heap은 우리가 우선순위 큐를 구현할 떄 빈번히 사용됩니다. 우선순위 큐란, 우선순위가 높은 것 먼저 빠져 나가는 것을 말합니다. Max Heap max(min) tree란 parent의 key가 child의 키보다 작지 않은 것을 말합니다. 그리고 max(min) heap는 complete binary tree로써, max (min) tree인 것을 말합니다. 즉 max (min) tree에서 root의 값은 최댓값이거나 최솟값이 될 수 밖에 없습니다. 또한 이들은 complete binary tree이기 때문에 우리는 array representation으로도 heap을 나타낼 수 있습니다. Insertion into a Max Heap 여기서 저희는 bubble up process라는 것을 정의해..

Data Structure - Hashing ( Dynamic Hashing )

Dynamic Hasing 여지것 우리는 배열(bucket)의 사이즈를 바꾸지 않는 Static Hashing에 대해 알아보았습니다. 우리는 좋은 성능을 내기 위해서, hash table의 사이즈를 늘려주어야 할 필요가 있게 됩니다. loading density가 이미 정해진 경곗값 이상으로 올라가게 되면 말이죠. 예를 들어서 b개의 bucket과 divisor D = b -> 2b + 1가 되어야 합니다. D = 2b + 1로 array doubling을 해주어야 합니다. 우리는 해시 함수도 다시 구축해야 합니다. 모든 쌍들을 다시 만든 해시 함수에 다시 매핑시켜주어야 합니다. 이 Dynamic Hashing에는 2가지 방법이 있습니다. Dynamic hashing using directories Di..

Data Structure - Hashing ( Overflow handling )

hash table에서 overflow는 새로운 사전에서 slot이 꽉찼을 떄 발생한다고 앞에서 말씀드렸습니다. 이를 다루기 위해서 두가지 방법을 소개합니다. Open addressiong Linear probing Quadratic probing Rehashing Random probing Chaining Linear probing 우리가 key를 집어 넣을 떄, linear probing은 ( ht[h(k) + i] % b, 0

Data Structure - Hashing ( Hash Functions )

Hash Function hash function은 key를 bucket에 mapping시켜주기 위한 함수입니다. 이는 계산하기 쉬워야합니다. 그리고 collision을 최소화 시킬 수 있어야 합니다. 이는 편향적인 결과를 내면 안됩니다. ( 하나에 몰빵되면 안됨 ) Uniform hash Function random key K가 있다고 해 봅시다. 이 때 h(k) = i이 나올 확률은 1/b에 근사해야 합니다. 이러한 hash function을 uniform hash function이라고 합니다. Division Division은 가장 널리 사용되는 hash function중 하나입니다. 여기서 저희는 key는 음수가 아니라고 가정합니다. 그리고 home bucket은 modulo ( % )연산에 의해..