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