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