C'mon class, no one has taken me up on my challenge. Last year we had a full solution in the comments by this time!

@Kayvonf

Here is lock-insert version:

struct Tree {
   Node *root;
   Lock *lock;
};

struct Node{
   int value;
   Node *left;
   Node *right;
   Lock *lock;
};

void insert(Tree *tree, int value){
   lock(tree->lock);
   if (tree->root == NULL){
      Node *pn = (Node *)malloc(sizeof(struct Node));
      pn->value = value;
      pn->lock = lock();
      tree->root = pn;
      unlock(tree->lock);
      return;
    } else {
       lock(tree->root->lock);
       unlock(tree->lock);
       insert_node(tree->root, value);  
    }
 }

 void insert_node(node *n, int value){
    if (value <= n->value) {
       if(n->left == NULL){
          Node *pn = (Node *)malloc(sizeof(struct Node));
          pn->value = value;
          n->left = pn;
          pn->lock = lock();
          unlock(n->lock);
          return;
       }
       lock(n->left->lock);
       unlock(n->lock);
       insert_node(n->left, value);
    } else {
      if (n->right == NULL) {
         Node *pn = (Node *)malloc(sizeof(struct Node));
         pn->value = value;
         n->right = pn;
         unlock(n->lock);
         return;
      }
      lock(n->right->lock);
      unlock(n->lock);
      insert_node(n->right, value);
    }
 }

Looks good, but I think there are a couple of typos that were confusing when I was reading through.

In the case where n->left is NULL, it should be n->left = pn instead of pn->left = n. Same thing for the n->right is NULL case.

In the value <=n->value case, lock is called on n->left->right when it should be called on n->left->lock.

Also, if you add a single tab to the start of each line of code, Markdown will treat the section as verbatim and the indentation will be displayed correctly.

@plymouth

Thanks for your suggestions. : )

However, I don't know how to insert indentation. Tried several methods, but failed. The best thing I can do now, is not insert wired characters.

Here is the delete function. I wrote this quickly so it may have some bugs, please let me know if you see any so I can improve the answer :). Also the code is not as clean as it can be, again I coded this quickly. I will look at the code more carefully again in the night.

//helper function. finds the successor of root in its right subtree.
//assumes we have lock on root.
//this function will lock the result node,
//it will also lock the parent result node,
//also, it will assume that root has a non-null right child (the successor is in the right subtree).
void find_successor(Node * root, Node ** result, Node ** result_parent);

//assumes that there is always a fictitious root node
//it is not actually used, it is a implementation detail
//to keep the previous/current lock invariant.
void delete(Tree * tree, int value) {
    lock(tree->fake_root->lock);
    if(tree->root == NULL) {
        unlock(tree->fake_root->lock);
        return;
    }

    Node * previous = tree->fake_root;
    Node * current = tree->root;
    Node ** parent_child_ptr = &tree;->root; //pointer to child node of the parent
    lock(tree->root->lock);

    //find the node with node->value = value
    while(1) {
        if(value > current->value) {
            if(current->right != NULL) {
                lock(current->right->lock); //conservative approach
                unlock(previous->lock);
                previous = current;
                current = current->right;
                parent_child_ptr = &previous;->right;
            }
            else {
                //node not on the tree, free locks, exit
                unlock(previous->lock);
                unlock(current->lock);
                return;
            }
        }
        else if(value < current->value) {
            if(current->left != NULL) {
                lock(current->left->lock); //conservative approach
                unlock(previous->lock);
                previous = current;
                current = current->left;
                parent_child_ptr = &previous;->left;
            }
            else {
                //node not on the tree, free locks, exit
                unlock(previous->lock);
                unlock(current->lock);
                return;
            }
        }
        else {
            //found the node, let's break out of this loop and delete it.
            break;
        }
    }

    //here current points to the node we have to delete
    //previous points to the parent of the node, or to the fake root.
    //*parent_child_ptr is either tree->root or one of the right or left child pointers of previous
    //(whichever current is)
    if(node->right == NULL && node->left == NULL) {
        *parent_child_ptr = NULL;
    }
    else if(node->right == NULL) {
        *parent_child_ptr = node->left;
    }
    else if(node->left == NULL) {
        *parent_child_ptr = node->right;
    }
    else {
        //we must find successor of current
        Node * successor = NULL;
        Node * successor_parent = NULL;
        find_successor(current, &successor;, &successor;_parent);
        //we know that successor->left is NULL, since it is the minimum
        //of the subtree of current->right
        //we are also guaranteed that successor != NULL and successor_parent != NULL

        //detach successor from old parent
        if(successor_parent->right == successor) {
            successor_parent->right = successor->right;
        }
        else {
            successor_parent->left = successor->right;
        }
        //attach successor to new parent, effectively deleting current
        *parent_child_ptr = successor;
        successor->right = current->right;
        successor->left = current->left;

        //free successors locks
        if(successor_parent != current) unlock(successor_parent->lock);
        unlock(successor->lock);
    }

    //unlock current and previous locks.
    if(previous != NULL) unlock(previous->lock);
    unlock(current->lock);
    current->left = NULL;
    current->right = NULL;
    delete current; //safe to delete now.
}

void find_successor(Node * root, Node ** result, Node ** result_parent) {
    //assume we have lock on root.
    //this function will lock the result node,
    //it will also lock the parent result node
    //also, assume root has a non-null right child.
    Node * current = root->right;
    Node * previous = root;
    lock(current->right);
    while(current->left != NULL) {
        lock(current->left);
        if(previous != root) unlock(previous);
        previous = current;
        current = current->left;
    }
    *result = current;
    *result_parent = previous;
}

I think another way for the deletion is that after we find the node to delete, we use left rotation and right rotation to adjust the node to a leaf node, and then delete it. In this way, the deletion code can be written in a similar way as the search code.