# 3.1 Contiguous vs. Linked Data Structures

## Arrays

`array of 1 element+--+|a |+--+double the array (2 elements)  +--++--+  |a ||b |  +--++--+double the array (4 elements)  +--++--++--++--+  |a ||b ||c ||c |  +--++--++--++--+double the array (8 elements)  +--++--++--++--++--++--++--++--+    |a ||b ||c ||c ||x ||x ||x ||x |  +--++--++--++--++--++--++--++--+double the array (16 elements)  +--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+    |a ||b ||c ||c ||x ||x ||x ||x ||  ||  ||  ||  ||  ||  ||  ||  |   +--++--++--++--++--++--++--++--++--++--++--++--++--++--++--++--+`

# 3.4 Binary Search Trees

## Implementing Binary Search Trees

`tree *search_tree(tree *l, item_type x){    if (l == NULL) return(NULL);    if (l->item == x) return(l);    if (x < l->item)        return( search_tree(l->left, x) );    else         return( search_tree(l->right, x) );}`
`tree *find_minimum(tree *t) {    tree *min;  //pointer to minimum    if (t == NULL) return(NULL);    min = t;    while (min->left != NULL) //Iteratively        min = min->left;    return(min);}`
`void traverse_tree(tree *l){ // in-order    if (l != NULL) {        traverse_tree(l->left);        process_item(l->item);        traverse_tree(l->right);    }}`
`/* A utility function to insert a new node with given key in BST */struct node* insert(struct node* node, int key){    /* If the tree is empty, return a new node */    if (node == NULL){       node* p = malloc(sizeof(tree)); /* allocate new node */       p->key = key;       p->left = p->right = NULL;       return p;    }     /* Otherwise, recur down the tree */    if (key < node->key)        node->left  = insert(node->left, key);    else if (key > node->key)        node->right = insert(node->right, key);        /* return the (unchanged) node pointer */    return node;}`

# 3.5 Priority Queues

`struct item {   int item;   int priority;}`

# 3.7 Hashing and Strings

## Efficient String Matching via Hashing

`function RabinKarp(string t[1..n], string p[1..m])  hpattern := hash(p[1..m]); // length = m-1+1 = m  for i from 1 to n-m+1 //e.g. n=5, m=3, 1->n-m+1=>1->3. n-m+1-1+1 = n-m+1 times of hash computations.    hs := hash(t[i..i+m-1]) // length = i+m-1-i+1 = m    if hs = hpattern      if t[i..i+m-1] = p[1..m]        return i  return not found# Above algorithm reduces string matching to n−m+2 hash value computations (the n−m+1 windows of t, plus one hash of p), plus what should be a very small number of O(m) time verification steps`

Software Engineer in Tokyo. Aim to understand computer science very well. LinkedIn: https://www.linkedin.com/in/peng-larry-yang-9a794561/

## More from Larry | Peng Yang

Software Engineer in Tokyo. Aim to understand computer science very well. LinkedIn: https://www.linkedin.com/in/peng-larry-yang-9a794561/