If you’re looking for an Objective-C implementation of an immutable AVL tree, based on Mono’s implementation of AvlNode (System.Collections.Immutable namespace), you’ve come to the right place :)

You can find the code right here: AvlNode gist

Insert performance is considerably slower than an NSMutable array, and about half the speed of a mutable AVL tree (due to the extra object allocations). However because this implementation is immutable (any operation on the tree potentially creates a new root node, and doesn’t alter the base tree at all), trees can be shared freely between threads. This has the benefit no locking / synchronization is needed to “modify” the collection.

Another interesting property is you’re free to retain “old” trees, effectively keeping a snapshot of past states.

Here are some timings for comparison (inserting 50000 NSNumbers). Note the increasing times of the regular immutable NSArray, using arrayByAddingObject:

AVL tree (mutable)
2014-01-17 21:44:40.003 AVLTree[98872:303] elapsed subtime = 33.4581
2014-01-17 21:44:40.045 AVLTree[98872:303] elapsed subtime = 37.948
2014-01-17 21:44:40.082 AVLTree[98872:303] elapsed subtime = 36.437
2014-01-17 21:44:40.123 AVLTree[98872:303] elapsed subtime = 40.668
2014-01-17 21:44:40.165 AVLTree[98872:303] elapsed subtime = 40.554
2014-01-17 21:44:40.209 AVLTree[98872:303] elapsed subtime = 43.584
2014-01-17 21:44:40.250 AVLTree[98872:303] elapsed subtime = 40.233
2014-01-17 21:44:40.284 AVLTree[98872:303] elapsed subtime = 33.158
2014-01-17 21:44:40.322 AVLTree[98872:303] elapsed subtime = 37.446
2014-01-17 21:44:40.361 AVLTree[98872:303] elapsed time = 391.786

AVL node (immutable)
2014-01-17 21:44:40.441 AVLTree[98872:303] elapsed subtime = 78.872
2014-01-17 21:44:40.536 AVLTree[98872:303] elapsed subtime = 93.391
2014-01-17 21:44:40.631 AVLTree[98872:303] elapsed subtime = 93.877
2014-01-17 21:44:40.727 AVLTree[98872:303] elapsed subtime = 95.449
2014-01-17 21:44:40.835 AVLTree[98872:303] elapsed subtime = 107.319
2014-01-17 21:44:40.943 AVLTree[98872:303] elapsed subtime = 106.377
2014-01-17 21:44:41.043 AVLTree[98872:303] elapsed subtime = 99.7339
2014-01-17 21:44:41.145 AVLTree[98872:303] elapsed subtime = 100.765
2014-01-17 21:44:41.285 AVLTree[98872:303] elapsed subtime = 140.152
2014-01-17 21:44:41.397 AVLTree[98872:303] elapsed time = 1034.59

Mutable array
2014-01-17 21:44:41.412 AVLTree[98872:303] elapsed subtime = 0.232995
2014-01-17 21:44:41.413 AVLTree[98872:303] elapsed subtime = 0.267982
2014-01-17 21:44:41.414 AVLTree[98872:303] elapsed subtime = 0.232995
2014-01-17 21:44:41.415 AVLTree[98872:303] elapsed subtime = 0.340998
2014-01-17 21:44:41.415 AVLTree[98872:303] elapsed subtime = 0.244975
2014-01-17 21:44:41.416 AVLTree[98872:303] elapsed subtime = 0.337005
2014-01-17 21:44:41.417 AVLTree[98872:303] elapsed subtime = 0.227988
2014-01-17 21:44:41.418 AVLTree[98872:303] elapsed subtime = 0.178993
2014-01-17 21:44:41.419 AVLTree[98872:303] elapsed subtime = 0.231981
2014-01-17 21:44:41.420 AVLTree[98872:303] elapsed time = 8.18902

Mutable array with locking
2014-01-17 21:44:41.422 AVLTree[98872:303] elapsed subtime = 0.946999
2014-01-17 21:44:41.423 AVLTree[98872:303] elapsed subtime = 0.873029
2014-01-17 21:44:41.425 AVLTree[98872:303] elapsed subtime = 0.846028
2014-01-17 21:44:41.426 AVLTree[98872:303] elapsed subtime = 0.813007
2014-01-17 21:44:41.427 AVLTree[98872:303] elapsed subtime = 0.771999
2014-01-17 21:44:41.428 AVLTree[98872:303] elapsed subtime = 0.835001
2014-01-17 21:44:41.430 AVLTree[98872:303] elapsed subtime = 0.808001
2014-01-17 21:44:41.431 AVLTree[98872:303] elapsed subtime = 0.815034
2014-01-17 21:44:41.432 AVLTree[98872:303] elapsed subtime = 0.89401
2014-01-17 21:44:41.434 AVLTree[98872:303] elapsed time = 13.129

Immutable array
2014-01-17 21:44:41.489 AVLTree[98872:303] elapsed subtime = 52.946
2014-01-17 21:44:41.638 AVLTree[98872:303] elapsed subtime = 147.815
2014-01-17 21:44:41.886 AVLTree[98872:303] elapsed subtime = 247.666
2014-01-17 21:44:42.201 AVLTree[98872:303] elapsed subtime = 313.846
2014-01-17 21:44:42.620 AVLTree[98872:303] elapsed subtime = 419.08
2014-01-17 21:44:43.122 AVLTree[98872:303] elapsed subtime = 500.611
2014-01-17 21:44:43.720 AVLTree[98872:303] elapsed subtime = 597.283
2014-01-17 21:44:44.413 AVLTree[98872:303] elapsed subtime = 692.916
2014-01-17 21:44:45.245 AVLTree[98872:303] elapsed subtime = 830.406
2014-01-17 21:44:46.305 AVLTree[98872:303] elapsed time = 4868.87
About these ads