Greatest Common Divisor

1. Description Because $$gcd(a,b)=gcd(|a|,|b|)$$, we just consider the nonnegative integers in this article. And $$d|a$$ means $$d$$ divides $$a$$, that is to say, $$a=kd$$ for some integer $$k$$. 2. GCD recursion theorem $$gcd(a,b)=gcd(b,a mod b)$$ Proof: Let $$d=gcd(a,b)$$, then $$d|a$$ and $$d|b$$. $$a\ mod\ b=a-qb$$, where $$q=\left \lfloor a/b \right \rfloor$$, so $$d|(a\ mod\ b)$$.

Binary Search Trees

1 BST Class A binary search tree is a kind of binary tree. Each node of it contains its key, satellite data, attributes left, right, p that point to its left child, right child, and parent. It satisfies the following binary-search-tree property: Let x be a node in a binary search tree. If y is

Hash Tables

1. Direct-address tables Assume all elements’ keys are different and are from $$U={0, 1, …, m-1}$$. Then the direct-address table is $$T[0..m-1]$$, that is to say, the key is the index. 2. Hash tables The actual keys set $$K$$ is so small relative to the universe of keys set $$U$$. So a hash function should