Kodeco Forums

Swift Algorithm Club: Swift Binary Search Tree Data Structure

🎓 Courses & Articles
1

Learn how to implement a Swift binary search tree. Code snippets for quick reference, plus a step-by-step tutorial and explanation.

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

Hi Kelvin, thanks for a nice article. I happened to be playing lately with binary trees visualisation in Swift 3 Playgrounds, just committed at GitHub - akpw/VisualBinaryTrees: Visual Binary Trees with Swift 3 Playgrounds and started to described it in an on-going blog series. If you think it’d be useful, perhaps we should merge some of the tree visualisation code into Swift Algorithm Club repo?

3

@apow

First of all, thanks! I just took a look at your blog / repo. I love the use of protocols, in particular the way you defined a binary search tree purely by conforming to a binary search tree protocol on a normal binary tree. Nice use of the standard library protocols too!

We were talking about visualizations of algorithms just a while ago actually via this issue: Visualization of Algorithms in Playgrounds / Cocoa / Swift · Issue #171 · raywenderlich/swift-algorithm-club · GitHub.

Needless to say I think your suggestion to incorporate some visualization code to the SAC is most welcomed. The Binary Tree article in the repo is fairly basic, and is probably a great candidate to try some visualization stuff. I’ll be trying some of that in the future myself :slight_smile:

Thanks for sharing and hope to see you around!

5

The period of updating the articles here is so long,if per week you can update,it’s good…

6

@kelvin_lau
Hi Kevin! Thanks for this very useful article!

I am wondering about the following note:

Note: Average time complexity for a binary search tree for the traditional implementation using classes is O(log n), which is considerably faster. Using classes (reference semantics) won’t have the copy-on-write behaviour, so you’ll be able to insert without making a complete copy of the tree.

Precisely, why would we not use classes instead of structs? no copy on write, better performance at insertion… What does structs give us?

7

Value types offer the gift of immutability :slight_smile:

Due to their immutability, the compiler can perform optimizations. I want to clarify that some implementations using class based nodes and a struct based LinkedList type can achieve the same time complexity while having the same benefits of copy-on-write.

8

This tutorial is more than six months old so questions are no longer supported at the moment for it. We will update it as soon as possible. Thank you! :]