| Because I cannot post on http://arclanguage.org/item?id=14181 anymore, I created this discussion instead. waterhouse's post on AVL trees was extremely helpful to me, and I thank you a lot for it. It's hard finding algorithms to create efficient immutable data structures (almost all tutorials teach you how to make mutable AVL/Red Black trees). I was astonished at how simple the code was, and I was recently in need of a tree data structure, so I tried porting the code over to JavaScript. In doing so, I found that insertion works very well (and is actually really fast! The immutable AVL trees are competitive in speed to JavaScript's built-in mutable objects!). However, deletion did not work correctly. To be more specific, the deletion algorithm can sometimes create an unbalanced tree. First, I must correct the "aremove" function a little, since it had some typos: (def aremove (less x tree)
(if no.tree
(err "aremove: failed to find" x "in" tree)
(is x tree!dt)
(amerge tree!lf tree!rt)
(less x tree!dt)
(node/r tree!dt
(aremove less x tree!lf)
tree!rt)
(node/r tree!dt
tree!lf
(aremove less x tree!rt))))
Now I will introduce a "verify" function that will test that a tree conforms to all of the AVL requirements: ; Depth must be correct
(def verify-depth (tree)
(is (depth tree)
(inc:max (depth tree!lf)
(depth tree!rt))))
; Depth must not vary by more than 1
(def verify-height (tree)
(let diff (- (depth tree!lf)
(depth tree!rt))
(in diff -1 0 1)))
(def verify-tree (tree tests)
; Empty trees are always valid
(or (no tree)
(and (verify-depth tree)
(verify-height tree)
; Verify that:
; #1 all keys to the left are lower than
; #2 all keys to the right are greater than
(all (fn (f) (f tree)) tests)
(verify-tree tree!lf (cons (fn (x) (< x!dt tree!dt)) tests))
(verify-tree tree!rt (cons (fn (x) (> x!dt tree!dt)) tests)))))
(def verify (tree)
(if (verify-tree tree nil)
tree
(err "bad tree")))
Now I will create a list of the numbers 0 to 1000, but in a random order: ; This is a part of Arc/Nu and is *not* a part of Arc 3.1,
; but it's necessary because Racket has a shuffle function and Arc doesn't
(%:namespace-require 'racket/list)
; Get a list of numbers from 0 - 1000, but shuffled in a random order
(= numbers (%.shuffle (range 0 1000)))
I also need to create a "foldl" function since Arc's "reduce" does not accept an init argument: (def foldl (f init x)
(if (no x)
init
(foldl f (f init (car x)) (cdr x))))
And now let's create an AVL tree by inserting the numbers into it, in sorted order: ; This takes a while, but it does eventually finish
(= tree
(foldl (fn (x y)
(verify (ainsert < y x)))
nil
numbers))
Notice the call to "verify", which makes sure that at the end of every insertion, the tree is still correct.Now let's try removing the elements from the tree: (= tree
(foldl (fn (x y)
(verify (aremove < y x)))
tree
numbers))
With extremely high probability, you will get "error: bad tree".The problem is actually with the "node/r" function. Strangely enough, it's incorrect in a way that only causes problems with deletion, not insertion. The fix is really simple, though: (def node/r (d x y) ;like node but rebalances
(if (> depth.x (inc depth.y))
(if (< (depth x!lf) (depth x!rt))
(node x!rt!dt (node x!dt x!lf x!rt!lf)
(node d x!rt!rt y))
(node x!dt x!lf (node d x!rt y)))
(> depth.y (inc depth.x))
(if (< (depth y!rt) (depth y!lf))
(node y!lf!dt (node d x y!lf!lf)
(node y!dt y!lf!rt y!rt))
(node y!dt (node d x y!lf) y!rt))
(node d x y)))
All I did was swap the calls to "node" so that the double rotation is checked for first, using "<" rather than ">". And that's it! It took me quite a while to figure out what the problem was, since "node/r" works fine for insertion.Also, I was quite surprised that the "amerge" function actually works. It seems quite clever to me. Binary search tree deletion normally uses an algorithm like this: ; Finds the minimum element in a tree and returns a list of:
; #1 The minimum element
; #2 The tree, excluding the minimum element
(def amin (tree)
(if (no tree!lf)
(list tree tree!rt)
(let (min left) (amin tree!lf)
(list min (node/r tree!dt left tree!rt)))))
(def amerge (a b) ;not a general merge; assumes [all of a] ≤ [all of b]
(if no.a b
no.b a
(let (min right) (amin b)
(node/r min!dt a right))))
In any case, thanks again! Now I have lovely fast immutable sorted dictionaries, sorted sets, and unsorted arrays using AVL trees. Most operations are O(log n), including concatenating two arrays! | 
