Kodeco Forums

Swift Algorithm Club: Swift Tree Data Structure

🎓 Courses & Articles
1

Learn how to implement a Swift Tree data structure through this hands-on tutorial!

This is a companion discussion topic for the original entry at https://www.raywenderlich.com/1053-swift-algorithm-club-swift-tree-data-structure
2

I didn’t read full article so I might be wrong but I would suggest to make the “parent” property weak.

3

Good eye @tobol! Fixed

4

Great tuturial @kelvin_lau, any suggestions on prime use cases for beginners to start implement trees in side projects?

5

Thanks @leokwanbt14!

I’d say anything that requires a custom hierarchical structure is fair grounds to use trees. Perhaps in a game you wanted to lay out a skill tree?

1 Like
6

Why was the parent property made weak?

7

@mayurtolani to fix the retain cycle, parent has a reference to the child, the child must have a weak reference back to the parent.

8

Great tutorial, and very easy to grok explanation. Please do more of these! @kelvin_lau

9

How would I go about deleting a node in this scenario, or moving a node to another parent?

10

hotBeverage.addChild(chocolate)
should be hotBeverage.addChild(cocoa)

11

Basically what @lucianboboc said.

Another way to put it is, make sure 2 objects don’t keep a “strong” reference to each other.

12

@msheaver

Try approaching those problems by utilizing the search method. Since we do have a parent property for each node, the rough idea for deleting is quite simple:

  1. search for the node you want to delete (you can reuse the search function you made in this tutorial)
  2. travel to the parent via the parent property in the node
  3. delete the node from the parent’s children array

Moving to another parent follows a similar pattern, and you can make use of the search and add functions as well! If you get stuck, make a post here and I think everyone would be interested in helping :slight_smile:

If you get the solution though, consider making a PR in the Swift Algorithm Club repository :smiley:

13

@cretech

The solution should still compile fine, but I agree it could be clearer to switch the property name from chocolate to cocoa.

Thanks!

14

I think I am close with the following implementation:

extension Node where T: Equatable {
  func delete(node: Node<T>, value: T) {
    // ensure that node exists
    if let returnedNode = node.search(value) {
      // ensure that returned node has a parent
      if let parent = returnedNode.parent {
        let childIndex = parent.children.indexOf(returnedNode)
        parent.children.removeAtIndex(childIndex)
      }
    }
  }
}

…except for the line that finds the index of the node:

let childIndex = parent.children.indexOf(returnedNode)

How do I correctly get the index of the child?

15

let childIndex = parent.children.indexOf { $0 === returnedNode }

16

I am running Xcode 8 and I know both Swift 3 and Xcode 8 are in beta. I am just trying to figure out why I am getting this error, and what exactly does it mean. I adjusted the method to follow the new Swift 3 guidelines. I am getting an error on the lines in which I add the child to the parent. I get the error Execution was interrupted, reason: EXEC_BAD_ACCESS (code=EXC_I386_GPFLT)

I get this error as well when I copied and used the example code directly in xcode as well.

class Node {
var value: String
var children = Node
weak var parent: Node?

init(value: String) {
    self.value = value
}

func add(child: Node) {
    children.append(child)
    child.parent = self
}

}

let beverages = Node(value: “beverages”)

let hotBeverage = Node(value: “hot beverage”)
let coldBeverage = Node(value: “cold beverage”)

let tea = Node(value: “tea”)
let coffee = Node(value: “coffee”)
let cocoa = Node(value: “cocoa”)

let blackTea = Node(value: “black tea”)
let greenTea = Node(value: “green tea”)
let chai = Node(value: “chai”)

let soda = Node(value: “soda”)
let milk = Node(value: “milk”)

let gingerAle = Node(value: “ginger ale”)
let bitterLemon = Node(value: “bitter lemon”)

beverages.add(child: hotBeverage)
beverages.add(child: coldBeverage)

hotBeverage.add(child: tea)
hotBeverage.add(child: coffee)
hotBeverage.add(child: cocoa)

coldBeverage.add(child: soda)
coldBeverage.add(child: milk)

tea.add(child: blackTea)
tea.add(child: greenTea)
tea.add(child: chai)

soda.add(child: gingerAle)
soda.add(child: bitterLemon)

17

what does indexOf($0 == returnedNode) mean exactly and why doesn’t indexOf(returnedNode) work?

18

Seems like an interesting issue with the weak semantics here. Xcode 7.3 works fine. I’ll investigate further.

19

TL;DR - Our custom Node object doesn’t conform to Equatable, so we don’t get to use the convenient version.

Long version:

Let’s start off with a working example:

let stringArray = ["Hello", "Cats", "Dogs"]
print(stringArray.indexOf("Hello")) // prints 0

The above compiles fine. However, we can’t do the same with our Node object:

let helloNode = Node<String>(value: "Hello")
let catNode = Node<String>(value: "Cat")

let nodeArray = [helloNode, catNode]
print(nodeArray.indexOf(helloNode)) // compiler error

To understand why, you’ll need to dig a bit deeper into where the indexOf method comes from.

CollectionType Protocol

The CollectionType protocol is adopted by types that can be treated as a collection, such as Swift arrays. This protocol has a suite of methods, and amongst them is the indexOf method.

Inside the CollectionType protocol, indexOf has the following signature:

@warn_unused_result func indexOf(@noescape _ predicate: (Self.Generator.Element) 
  throws -> Bool) rethrows -> Self.Index?

Let’s simplify that a bit so we can digest it a little easier:

func indexOf(predicate: (Self.Generator.Element) -> Bool)

The generalized version of indexOf takes in a closure of the form (Self.Generator.Element) -> Bool. The idea is you’ll provide the logic for it to match what you want to find. For example:

let nodeYouWantToFind = Node<String>(value: "Hello")
nodeArray.indexOf { $0 === nodeYouWantToFind }

However, by using protocol extensions, the Swift Standard Library extends the CollectionType protocol by providing a overload of indexOf. You may think of this one as the “convenience” method.

This one abstracts away the closure and just asks for the element, allowing you to call the method without supplying a closure. Continuing from the above example:

nodeArray.indexOf(nodeYouWantToFind)

Using this convenient method has some requirements though. Your type must be equatable to expose it. In this case, the Node class did not conform to equatable, so you aren’t able to use the convenient version of indexOf.

20

Kevin,

Under xCode 8b6 I was doing fine until I added the generic portion of your tutorial. For some reason I’m getting an:

 error: Execution was interrupted, reason: EXEC_BAD_ACCESS(code=EXC_i386_GPFLT) on  the .addChild(node:XXXX).

I’m not sure what the issue is and any pointers would be greatly appreciated.

thanx in advance