[Tree] Tree Traversal Iterative Method

Inorder: LinkedList<>stack=.. while ( root != null || !stack.isEmpty()) {        if ( root != null )       {             stack.push(root);             root = root.left;        }        else // root ==null       {             root= stack.pop();             res.add(root.val);             root= root.right;       } }

Preorder: LinkedList<>stack=.. while (root!= null || !stack.isEmpty()) {         if (root!= null)         {               stack.push(root);               res.add(root.val);              root =root.left;           }         else // root == null         {                root = stack.pop();                root = root.right;         } }

Postorder: LinkedList<>stack=... TreeNode pre = new TreeNode(); while (root != null || !stack.isEmpty()) {        if (root!= null)        {               stack.push(root);               root = root.left;        }        else // root ==null        {               TreeNode peekNode = stack.peek();               //while (peekNode.right != null && peekNode.right != pre)                              //peekNode.right == null;               if ( peekNode.right != null && pre != peekNode.right)               {                      root = peekNode.right;                }               else { //peekNode.right ==null                      stack.pop();                      res.add(pre.val);                      //root = pre.right;                      pre = peekNode;               }         } } peekNode.right != null, right has a chilren, traverse first 2. pre!= peekNode.right, already traverse right children, traverse me parent(root) now

[Data Structure]Map Implementation using BST

http://www.sanfoundry.com/java-program-implement-hash-tables-chaining-binary-trees/
1. Map
Map<K,V>
store key and value pair
key datatype is K
value datatype is V

2. BST
2.1 each node has at most two children
2.2 the value of the nodes on the left subtree is less than
2.3 the value of the nodes on the right subtree is greater than
each node stores a key and associate with a value
keys are fully ordered
3. Implementation
Map
variable: key,data, node[pair], node's left and right child
method: get(key), set(key,value)
get and set do binary search, when a key showed up we compare it with the root.
If less go left, it greater go right until we find the target

// the node class - clients will not interact with directly
public class BSTNode {

     public K key;
     public V value;
     public BSTNode left ,right; // children
     BSTNode(K k, V v){ // constructor
         key = k;
         value  =v;
     }

     // Lookup:
     public V lookup(K key, Comparator keycomp){
         // COMPARE from the root(this.key)
         int cmp = keycomp.compare(key, this.key);
         if ( cmp == 0 ){//equal, k == n.key
             return value;
         } else if ( cmp < 0 && left != null ) {// less than, k < n.key
             return left.lookup(key,keycomp);
         } else if ( cmp > 0 && right != null ) {//greater than, k > n.key
             return right.loopup(key, keycomp);
         } else
             return null; // key not present in tree

     }

     // Insert: 
     public V insert(K key, V value, Comparator keycomp){
         int cmp = keycomp.compare(key,this.key);
         if ( cmp == 0) {
             V old = this.value;
             this.value = value;
             return old;
         //} else if ( cmp < 0 && left != null ){
         } 
         else if ( cmp < 0) {
             if (left == null) 
             {
                left = new BSTNode (key,value);
                return null ;// old value
             } 
             else
             {
                return left.insert(key,value,keycomp);
             }       
         }   
         //} else if ( cmp > 0 && right != null  ) {
         else if ( cmp >0){
             if ( right == null)
             {
                 right = new BSTNode(key,value);
                 return null;// old value
             }
             else 
             {
                return right.insert(key, value, keycomp);
             }
         } 
         //else {
         //
         //} 
             
     }

     // Remove:
     public V remove(K key, Comparator keycomp){
        int cmp = keycomp.compare(key, this.key);
        if ( cmp == 0) {
             
        //} else if ( cmp < 0 && left != null ) {
        else if (  cmp < 0 ){
             
             // left.loopup(key, left.key);
        }
        //} else if ( cmp > 0 && right != null ) {
        else if ( cmp > 0 ){   
             
             // right.lookup(key, right.key);
        } else {


        }
     }

     // FindMinNode:


     // RemoveMinNode:


}
public class BST {

     private BSTNode root;
     private Comparator keyComp;

     public BST(Comparator keycomp){
            this.root = null; //empty tree
            this.keycomp = keycomp;
     }

     // Get: look up value associated with given key 
     // @parameter: K key
     // @return : V vlaue
     public V get(K key){
           // Tree is Empty
          if (root == null)
            return null;
          else
          {
              return root.lookup(key,keycomp);
          }
     }


     // Put: add or replace key, value pair
     // @return V previous value
     public V put(K key, V value){
          // Tree is Empty
          if (root ==null)
          {
              root = new BSTNode(key, value);
              return null; //NOTE: Previous value
          }
          else 
              return root.insert(key, value, keycomp);
     }


     // Remove: remove key (and its associated value)
     // @returns the value associated with the deleted key, or null if no such key exist
     public V remove(K key){
           // Tree is Empty
           if (root == null)
                  return null
           else
           {
                  V old = root.lookup(key, keycomp);
                  // No such node exist
                  if (old == null)
                        return null;
                  else
                  {
                        root = root.remove(key, keycomp);
                        return old;
                  }
             
           }    
     }
}

[Multi-Threading] POSIX Example

1. Parallelize a presented segment of code using PThread primatives, being sure to highlight concerns with

            1. .resource conflicts,  

            2. order dependencies, and

            3.deadlock conditions.  


The above can be simplified - wherever there is a pthread_mutex_unlock() followed immediately by a pthread_mutex_lock() of the same mutex, the unlock/lock pair can be removed.

This program is supposed to synchronize several threads of "visitors" and "cars".

Visitors wander around for a random amount of time until they decide to go on a car ride.

If they are first in line for a car ride and a car is available they take a ride,

else they must wait till they are first in line or a car comes back.

If there are no visitors in line the cars wait in order until a visitor wants to go on a ride.

pthread_mutex_t c_mutex = PTHREAD_MUTEX_INITIALIZER; /* mutex protecting c_line and cars_out */ pthread_mutex_t v_mutex = PTHREAD_MUTEX_INITIALIZER; /* mutex protecting v_line */ pthread_cond_t c_cond[TOTALCARS]; /* condition variables for waiting for c_state[i] to change from VISITORS to another value */ pthread_cond_t v_cond[TOTALVISITORS]; /* condition variables for visitor waiting to be first in line or ejected from a car */ pthread_cond_t v_car_cond = PTHREAD_COND_INITIALIZER; /* Condition variable for a visitor first in line, but waiting for a car. */ pthread_mutex_t sc[TOTALCARS]; /* one mutex per car, sc[i] protects c_state[i] */ int main(){    int i;    void *status;    pthread_t c[TOTALCARS];    pthread_t v[TOTALVISITORS];    srand(time(NULL));    printf("Jurassic Park is open, cars are being prepped for passengers\n"); mutex init if multiple, cond init if multiple,  thread creation    for (i = 0; i < TOTALCARS; i++){        pthread_mutex_init(&sc[i], NULL);        pthread_cond_init(&c_cond[i], NULL);    }    for (i = 0; i < TOTALVISITORS; i++){        pthread_cond_init(&v_cond[i], NULL);    }    for (i = 0; i < TOTALCARS; i++){        c_state[i] = TOTALVISITORS;        pthread_create(&c[i], NULL, car, (void *)i);    }    for (i = 0; i < TOTALVISITORS; i++){        pthread_create(&v[i], NULL, visitor, (void *)i);    }    for (i = 0; i < TOTALVISITORS; i++){        pthread_join(v[i], &status);    }    museum_empty++;    printf("All visitors have left Jurassic Park\n");    for (i = 0; i < TOTALCARS; i++){        pthread_mutex_lock(&sc[i]);        c_state[i] = -1;        pthread_cond_signal(&c_cond[i]);        pthread_mutex_unlock(&sc[i]);    }    for (i = 0; i < TOTALCARS; i++){        pthread_join(c[i], &status);    }    printf("Jurrasic Park is closed, all cars have been parked\n");    pthread_exit(NULL);    return 0; } // For each car void *car(void *i) {    int c_id = (int) i;// Current car id    int v_id;    while (museum_empty != 1) { // Museum is open        /1* join end of car queue */ c_line[c_id]        pthread_mutex_lock(&c_mutex);        c_line[c_id] = set_car_place_in_line();        if (c_line[c_id] == 1)            pthread_cond_signal(&v_car_cond);        printf("Car %d is ready for a passenger and is %d in line                        %d of %d cars are out\n", c_id, c_line[c_id], cars_out, TOTALCARS);        pthread_mutex_unlock(&c_mutex);        /2* wait until occupied */ c_state[c_id]        pthread_mutex_lock(&sc[c_id]);        while (    (v_id = c_state[c_id]) == TOTALVISITORS     ) {            pthread_cond_wait(&c_cond[c_id], &sc[c_id]);        }        pthread_mutex_unlock(&sc[c_id]);        if(museum_empty == 1){            break;        }        pthread_mutex_lock(&c_mutex);// casrs_out        cars_out++;        printf("Visitor %d is riding in car %d                                           %d of %d cars are out --\n", v_id, c_id, cars_out, TOTALCARS);        pthread_mutex_unlock(&c_mutex);        /3* visitor is on car ride for random amount of time */        sleep(rand()%5);        printf("Visitor %d is  done riding in car %d\n", v_id, c_id);        /4* eject visitor from car */        pthread_mutex_lock(&sc[c_id]);//c_state        c_state[c_id] = TOTALVISITORS;        pthread_cond_signal(&v_cond[v_id]);        pthread_mutex_unlock(&sc[c_id]);        pthread_mutex_lock(&c_mutex); // casrs_out        cars_out--;        pthread_mutex_unlock(&c_mutex);    }    return NULL; } // For each visitor void *visitor(void *i) {    int v_id = (int) i;    int next_v;    int j = 0;    int car;    while (j < RIDES) {        if (j == 0) {            printf("Visitor %d entered museum and is wandering around\n", v_id);        } else {            printf("Visitor %d got back from ride and is wandering around\n", v_id);        }        sleep(rand()%3); /* visitor is wandering */        /1* join end of visitor queue */ // v_line        pthread_mutex_lock(&v_mutex);        v_line[v_id] = set_visitor_place_in_line();        printf("Visitor %d is %d in line for a ride\n", v_id, v_line[v_id]);        /2* wait until first in line */ //v_line        while (v_line[v_id] != 1) {            pthread_cond_wait(&v_cond[v_id], &v_mutex);        }        pthread_mutex_unlock(&v_mutex);        /3* wait until there is a car free */        pthread_mutex_lock(&c_mutex);        while ((car = get_next_car()) == TOTALCARS) {            pthread_cond_wait(&v_car_cond, &c_mutex);        }        /4* remove car from car queue */ //c_line        move_car_line();        pthread_mutex_unlock(&c_mutex);        /5* remove self from visitor queue */  //v_line        pthread_mutex_lock(&v_mutex);        move_passenger_line();        next_v = get_next_passenger();        if (next_v < TOTALVISITORS)            pthread_cond_signal(&v_cond[next_v]);        pthread_mutex_unlock(&v_mutex);        /6* occupy car */        pthread_mutex_lock(&sc[car]);//c_state        c_state[car] = v_id;        pthread_cond_signal(&c_cond[car]);        /7* wait until not in car anymore */        /* NOTE: This test must be against v_id and *not* VISITORS, because the car could have been         * subsequently occupied by another visitor before we are woken. */        while(c_state[car] == v_id) {            pthread_cond_wait(&v_cond[v_id], &sc[car]);        }        pthread_mutex_unlock(&sc[car]);        j++;    }    printf("Visitor %d leaving museum.\n", v_id);    return NULL; }