Оптимистическая синхронизация для двоичного дерева поиска ⇐ JAVA

[Anonymous]

Код: Выделить всё

public interface Set
{
// returns 'true' if x was added, 'false' if x was already in the set
public boolean add(int x);

// returns 'true' if x was removed, false if x wasn't in the set
public boolean remove(int x);

// returns 'true' if x is in the set, 'false' if it isn't
public boolean contains(int x);
}

Мне нужно реализовать параллельный набор на основе BST, используя оптимистичный шаблон блокировки «передача-за-рукой».
Я понимаю, что мне нужно заблокировать узлы, которые я добавляю между ними ( вправо или влево с родителем)
но я не понимаю часть удаления.
пока это мой код, он не работает...
добавить:

Код: Выделить всё

public boolean add(int key) {
Node newNode = new Node(key);
treeLock.lock();
try {
if (root == null) {
root = newNode;
return true;
}
} finally {
treeLock.unlock();
}

Node parent = null;
Node node = root;
while (node != null) {
parent = node;
if (key == node.key) {
return false; // Duplicate key
} else if (key < node.key) {
node = node.left;
} else {
node = node.right;
}
}

parent.lock.lock();
try {
if (key < parent.key) {
parent.left = newNode;
} else {
parent.right = newNode;
}
} finally {
parent.lock.unlock();
}
return true;
}

удалить:

Код: Выделить всё

public boolean remove(int key) {
treeLock.lock();
try {
if (root == null) {
return false;
}
if (root.key == key) {
if (root.left == null && root.right == null) {
root = null;
} else if (root.left != null && root.right == null) {
root = root.left;
} else if (root.left == null && root.right != null) {
root = root.right;
} else {
Node successor = findMin(root.right);
root.key = successor.key;
deleteNode(root, successor.key);
}
return true;
}
} finally {
treeLock.unlock();
}

Node parent = null;
Node node = root;
while (node != null && node.key != key) {
parent = node;
if (key < node.key) {
node = node.left;
} else {
node = node.right;
}
}

if (node == null) {
return false;
}

parent.lock.lock();
node.lock.lock();
try {
if (node.left == null && node.right == null) {
if (key < parent.key) {
parent.left = null;
} else {
parent.right = null;
}
} else if (node.left != null && node.right == null) {
if (key < parent.key) {
parent.left = node.left;
} else {
parent.right = node.left;
}
} else if (node.left == null && node.right != null) {
if (key < parent.key) {
parent.left = node.right;
} else {
parent.right = node.right;
}
} else {
Node successor = findMin(node.right);
node.key = successor.key;
deleteNode(node, successor.key);
}
} finally {
node.lock.unlock();
parent.lock.unlock();
}
return true;
}

содержит:

Код: Выделить всё

 public boolean contains(int key) {
Node node = root;
while (node != null) {
if (key == node.key) {
return true;
} else if (key <  node.key) {
node = node.left;
} else {
node = node.right;
}
}
return false;
}

этот код написан на Java, но на самом деле не имеет значения, какой это язык,важна концепция.

Подробнее здесь: https://stackoverflow.com/questions/793 ... earch-tree