Previous | Next --- Slide 14 of 31
Back to Lecture Thumbnails
kayvonf

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!

amaliujia

@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);
}
}

plymouth

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.

amaliujia

@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.

jazzbass

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;
}

zhanpenf

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.