Group Group Group Group Group Group Group Group Group
raywenderlich.com Forums

Swift Algorithm Club: Swift Binary Search Tree Data Structure

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

Hi Kelvin, thanks for a nice article. I happened to be playing lately with binary trees visualisation in Swift 3 Playgrounds, just committed at https://github.com/akpw/VisualBinaryTrees 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?

@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: https://github.com/raywenderlich/swift-algorithm-club/issues/171.

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!

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

@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?

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.

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! :]