Optimistische Synchronisierung für den binären Suchbaum ⇐ Java

[Guest]

Code: Select all

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

Ich muss einen gleichzeitigen BST-basierten Satz mit dem optimistischen Hand-over-Hand-Sperrmuster implementieren.
Ich verstehe, dass ich die Knoten, die ich zwischen ihnen hinzufüge, sperren muss ( rechts oder links mit übergeordnetem Element)
aber ich bekomme den Teil zum Entfernen nicht hin.
Das ist bisher mein Code, er funktioniert nicht...
hinzufügen:

Code: Select all

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

entfernen:

Code: Select all

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

enthält:

Code: Select all

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

Dieser Code ist in Java, aber es spielt keine Rolle, um welche Sprache es sich handelt,das Konzept ist entscheidend.