Hello, developers. Hope you can help me.
I have succesfully implemented a binary search tree in Swift using iterative algorithms for search, insert and delete operations. Now, I need the operations to compute height for every node, and I realized that implementing recursive algorithms for the operations were the most elegant and the easiest way to add this feature. I got stuck when implementing the recursive delete() operation because I got the following run-time errors:
Simultaneous accesses to 0x600003e0b1f0, but modification requires exclusive access.
Previous access (a modification) started at (0x13249e91c).
Current access (a read) started at:
0 libswiftCore.dylib 0x000000010a476a20 swift_beginAccess + 568
5 AVLTree 0x000000010a0ed570 main + 0
6 CoreFoundation 0x000000010bc578e0 __CFRUNLOOP_IS_CALLING_OUT_TO_A_BLOCK__ + 12
7 CoreFoundation 0x000000010bc56f20 __CFRunLoopDoBlocks + 312
8 CoreFoundation 0x000000010bc519e0 __CFRunLoopRun + 1284
9 CoreFoundation 0x000000010bc51500 CFRunLoopRunSpecific + 438
10 GraphicsServices 0x0000000114705b6f GSEventRunModal + 65
11 UIKitCore 0x0000000110208412 UIApplicationMain + 1621
12 AVLTree 0x000000010a0ed570 main + 205
13 libdyld.dylib 0x000000010d09bcf4 start + 1
Fatal access conflict detected.It seems there are conflicting memory accesses when implementing the delete() operation recursively. The code for the operation is as follows:
public class BSTNode {
public typealias EntryType = (key: Int, data: String)
private var entry: EntryType
fileprivate var height: Int
fileprivate var left: BSTNode?
fileprivate var right: BSTNode?
...
}
public class BST {
...
public func delete(_ key: Int, From root: inout BSTNode?, withParent parent: BSTNode?) -> BSTNode? {
if let current = root {
if key == current.getEntry().key {
if current.hasNoChild() {
if let previous = parent {
if previous.leftChildEqualsTo(current) {
previous.setLeftChildTo(nil)
} else {
previous.setLeftChildTo(nil)
}
} else {
root = nil
}
} else if current.hasSingleChild() {
} else {
}
return current
} else if key < current.getEntry().key {
return self.delete(key, From: ¤t.left, withParent: current)
} else {
return self.delete(key, From: ¤t.right, withParent: current)
}
} else {
return nil
}
}
}
var tree = BST()
var xNode: BSTNode?
tree.insert((3, "three"), In: &xNode)
tree.insert((-1, "minus one"), In: &xNode)
tree.insert((134, "one hundred and thirty four"), In: &xNode)
let node = tree.delete(-1, From: &xNode, withParent: nil)The idea is that the class BST is able to build binary search trees both internally or externally, but that is a different story. The call to the delete() operation in line 51 produced the aforementioned error output.
My hypothesis of the cause of the problem is that the first call to delete() in line 51 uses xNode as argument for the inout parameter root, unwraps root to get current, reads the node refered by current and sends it as an argument for the optional parameter parent in the recursive call in line 33. In the recursive call, the node refered to by current is tried to be modified in line 21. Thus, the first call to the function reads a memory area that is intended to be modified during the second recursive call, and this generates the conflict, right?
Now, how do I fix this? I cannot see a way to do it, since the operation is required to read and recursively modify the same memory area for a node in the binary search tree. Perhaps I am missing something, or the algorithm can be modified in a way the conflict does not happen. Do you see a solution to implement this recursive operation properly? If there were no solution, that would be very disappointing, because I assumed Swift's expressiveness would allow me to write this kind of recursive code.
Thanks. Kindest regards.
/TBC
I don't understand how you are creating this tree. You create the tree. That's fine. But then you create a node reference. Then you insert values into the tree, passing that reference as an inout parameter. Then you delete something from the tree using a key. That's fine too. But again, you use that node reference. And you supply a nil parent parameter. That might be acceptable in some intermediary method, and in some other language. I expect there is a more Swift-friendly way of doing that.
Unfortunately, that's about all I can say about it. I think your hypothesis is probably correct. The issue is that current is initialized to root (xNode). But this depends on xNode having been set as root (of tree) as a side effect of the insert methods. Just get rid of xNode. You don't want it. Your tree object should have a root node. Use that. You don't need the parent parameter either. You can store the parent in the node at the cost of some memory. You can do it with a parameter parameter to save that memory, but that seems like a premature optimization at this point.