Я успешно реализовал двоичное дерево поиска в Swift, используя итерационные алгоритмы для операций поиска, вставки и удаления.Теперь мне нужны операции для вычисления высоты для каждого узла, и я понял, что реализация рекурсивных алгоритмов для операций - это самый элегантный и самый простой способ добавить эту функцию.Я застрял при реализации рекурсивной операции delete () , потому что у меня возникли следующие ошибки времени выполнения:
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.
Кажется, при реализации удаления существует конфликт доступа к памяти() рекурсивная операция.Код для операции выглядит следующим образом:
1 public class BSTNode {
2 public typealias EntryType = (key: Int, data: String)
3
4 private var entry: EntryType
5 fileprivate var height: Int
6 fileprivate var left: BSTNode?
7 fileprivate var right: BSTNode?
8 ...
9 }
10
11 public class BST {
12 ...
13 public func delete(_ key: Int, From root: inout BSTNode?, withParent parent: BSTNode?) -> BSTNode? {
14 if let current = root {
15 if key == current.getEntry().key {
16 if current.hasNoChild() {
17 if let previous = parent {
18 if previous.leftChildEqualsTo(current) {
19 previous.setLeftChildTo(nil)
20 } else {
21 previous.setLeftChildTo(nil)
22 }
23 } else {
24 root = nil
25 }
26 } else if current.hasSingleChild() {
27 } else {
28 }
29 return current
30 } else if key < current.getEntry().key {
31 return self.delete(key, From: ¤t.left, withParent: current)
32 } else {
33 return self.delete(key, From: ¤t.right, withParent: current)
34 }
35 } else {
36 return nil
37 }
38 }
39 }
40
41 var tree = BST()
42
43 var xNode: BSTNode?
44
45 tree.insert((3, "three"), In: &xNode)
46 tree.insert((-1, "minus one"), In: &xNode)
47 tree.insert((134, "one hundred and thirty four"), In: &xNode)
48
49 let node = tree.delete(-1, From: &xNode, withParent: nil)
Идея состоит в том, что класс BST может создавать двоичные деревья поиска как внутри, так и снаружи, но это другая история.Вызов операции delete () в строке 49 привел к выводу вышеупомянутой ошибки.
Моя гипотеза о причине проблемы заключается в том, что первый вызов delete () в строке 49 использует xNode в качестве аргумента для параметра inout root , разворачивает root , чтобы получить current , читает узел, указанный как current и отправляет его в качестве аргумента для необязательного параметра parent в рекурсивном вызове в строке 31. В рекурсивном вызове узел, на который ссылается current , имеет видпопытался изменить в строке 19. Таким образом, первый вызов функции считывает область памяти, которая предназначена для изменения во время второго рекурсивного вызова, и это порождает конфликт, верно?
Теперь, как сделатьЯ это исправлю?Я не вижу способа сделать это, поскольку операция требуется для чтения и рекурсивного изменения одной и той же области памяти для узла в дереве двоичного поиска.Возможно, я что-то упустил, или алгоритм может быть изменен таким образом, чтобы конфликт не происходил.Вы видите решение для правильной реализации этой рекурсивной операции?Если бы не было решения, это было бы очень обидно, потому что я предполагал, что выразительность Свифта позволит мне написать рекурсивный код такого типа.