Arc Forumnew | comments | leaders | submitlogin
AVL trees
6 points by waterhouse 2445 days ago | 9 comments
An AVL tree is an ordered data structure that maintains O(log n) lookup, insertion, and removal. In this post, I explain them, give an implementation, draw an example (with Graphviz), and suggest some extensions and uses.

-------

AVL trees are augmented binary search trees: each node, in addition to having a datum and left and right branches, contains the depth of the subtree that it represents. This depth is equal to 1 + max(depth(left branch),depth(right branch)); it's useful for keeping the tree balanced.

Motivation: We start by considering a binary search tree. If this tree is balanced--all the leaves are at the same depth, or within 1 of the same depth--then the depth of the tree with n elements is between log_2(n) and 1+log_2(n). Which means that lookups take O(log n) time, which is good. And we can insert an element in log n time, too, by looking in the tree for where that element would be, and adding it to the bottom. However, this may unbalance the tree; if our tree has the numbers from 1 to 15, and we insert the numbers -1 through -20, then the tree becomes massively unbalanced on the left side and we no longer have O(log n) anything.

The next step is to say, hmm, well, perhaps we could rebalance the tree when we insert something. One way to do that is to construct a new balanced tree from the elements of the old one, plus the new element; this works, but it takes O(n) time for every insertion, which is really bad.

Now, someone at some point had the genius idea that maybe you could only perform local rebalancings. If, in the below case, we've just inserted something into the subtree A, and A has depth x+1, C depth x, and E depth x, then B has depth x+2, and this tree isn't balanced. We can shift around a couple of nodes, as illustrated, and now the two branches of the main tree both have depth x+1, so we're happy.

       D              B
    B     E  -->   A     D
  A   C                C   E
Doing this requires knowing the depth at each node. In general, computing the depth of a binary tree means following every branch all the way to the bottom--i.e. it is O(n).[1] However, if every node contains its depth, then it's an instant lookup. This little rebalancing operation was O(2), so the whole insertion took O(log n).

This looks like a promising approach, if we can get it to work right. If you do some fooling around and thinking, you may figure out that we can require all nodes to be balanced (so that [depth(left) - depth(right)] = 1, 0, or -1), and enforce this by rebalancing from the bottom up every time we insert something. And note that if the maximum difference between left and right branches is 1, then we can prove by induction that the minimum number of elements of an AVL tree with depth n is Fibonacci of something (specifically Fib(n+2)-1), which gives O(log_phi(n)) as an upper bound on the depth of an AVL tree with n elements.

------

Implementation. An AVL node contains a datum, a left and a right branch, and a depth.[2] I'll use nil as an empty AVL node.

  (def node (d x y)
    (obj dt d ;datum, left, right, depth
         lf x
         rt y
         dp (inc:max depth.x depth.y)))

  (def depth (node)
    (if node
        node!dp
        0))
Using the function "node", we can construct AVL trees, as in (node 2 (node 1 nil nil) (node 3 nil nil)). Now we need to handle rebalancing. We could do this by modifying nodes, but I find it easier to just construct new ones.[3]

  ;       rebalancing
  ;
  ;       D               B
  ;    B     E  -->   A       D
  ;  A   C          1   2   C   E
  ; 1 2                           
  ;
  ; ;in top example, 1,2,C,E all have depth x
  ; ;in bottom, A,1,2,E all have depth x
  ;
  ;       D               C
  ;    B     E  -->   B       D
  ;  A   C          A   1   2   E
  ;     1 2                      
  ;
  ;  (and mirror images)
Whenever [depth(left) - depth(right)] isn't -1, 0, or 1, we need to fix that. An imbalance can only happen as the result of a single insertion or removal; this means the depth mismatch of the two branches can be at most 2; for convenience, let's say the left branch (B) has depth x+2, while the right (E) has depth x. (Consult mirror images for the opposite case.) Since we rebalance things from the bottom up, B and E will, individually, be balanced; in particular, this means that the left and right branches of B (A and C) can have depths of, respectively, x+1 and x; x+1 and x+1; or x and x+1. The top chart illustrates the first case, the bottom chart the third case; the second case can be handled as either the first or the third. (All we need to do is make sure no nodes come out unbalanced.)

So here we go. In the following function, x and y correspond to B and E in the charts, and the node to be constructed corresponds to D.[4]

  (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!dt x!lf (node d x!rt y))
            (node x!rt!dt (node x!dt x!lf x!rt!lf)
                  (node d x!rt!rt y)))
        (> depth.y (inc depth.x))
        (if (> (depth y!rt) (depth y!lf))
            (node y!dt (node d x y!lf) y!rt)
            (node y!lf!dt (node d x y!lf!lf)
                  (node y!dt y!lf!rt y!rt)))
        (node d x y)))
Note that, up to this point, we haven't needed to compare any elements, and in fact I had forgotten I would have to do that. This realization pleases me. However, we do need to compare things when inserting or removing.

  (def ainsert (less x tree)
    (if no.tree
        (node x nil nil)
        (less x tree!dt)
        (node/r tree!dt
                (ainsert less x tree!lf)
                tree!rt)
        (node/r tree!dt
                tree!lf
                (ainsert less x tree!rt))))

  (def aremove (less test tree)
    (if no.tree
        (err "aremove: failed to find" x "in" tree)
        (test tree)
        (amerge tree!lf tree!rt)
        (less x tree!dt)
        (node/r tree!dt
                (aremove less test tree!lf)
                tree!rt)
        (node/r tree!dt
                tree!lf
                (aremove less test tree!rt))))

  (def amerge (a b) ;not a general merge; assumes [all of a] ≤ [all of b]
    (if no.a b
        no.b a
        (< depth.a depth.b)
        (node/r b!dt
                (amerge a b!lf)
                b!rt)
        (node/r a!dt
                a!lf
                (amerge a!rt b))))
-------

Time for a pretty picture. Here's what an AVL tree looks like when we insert 10 random numbers followed by 21 consecutive large numbers. I drew it with Graphviz, which is some pretty snazzy (and open source) graph-drawing software.

http://i.imgur.com/9CJ4d.png

Code:

  arc> (= u nil)
  nil
  arc> (repeat 10 (= u (ainsert < rand.100 u)))
  nil
  arc> (for i 200 220 (= u (ainsert < i u)))
  nil
  arc> ashow.u
  #<thread: ashow>

  (def agviz (tree)
    (pr "digraph g {")
    (when tree
      (pr "node [shape = record,height=.1];")
      (xloop (tree tree name "node")
        (pr name "[label = \"{" tree!dt "|depth: " depth.tree "}\"];")
        (pr "\"" name "\";")
        (with (a (string name "0") b (string name "1"))
          (when tree!lf
            (pr "\"" name "\":sw -> \"" a "\";")
            (next tree!lf a))
          (when tree!rt
            (pr "\"" name "\":se -> \"" b "\";")
            (next tree!rt b)))))
    (pr "}"))

  ; this writes Graphviz code, creates a PNG, and opens it. if "name" is
  ;  unspecified, it deletes these files after you close your PNG viewer.
  ; uses MacOSX-specific "open -nW" and requires graphviz
  (def ashow (tr (o name nil)) 
    (let fname (or name (tmpfile))
      (tofile fname agviz.tr)
      (thread:system:string
         "dot -Tpng " fname " -o " fname ".png && open -nW " fname ".png"
         (if no.name
             (string " && rm " fname " " fname ".png")))))
-------

Uses and extensions.

You can use an AVL tree to implement a priority queue. (Priority queue: sorted queue, supports "insert" and "get and delete first element". In this case, both of these are O(log n).) In fact, this was what originally impelled me to do this. The "insert-sorted" procedure in arc.arc, which I mentioned in footnote [2] [my implementation is different but equivalent], obviously wants to treat sorted lists like they're priority queues, but the insertion is O(n).

I haven't (yet) implemented destructive rebalancing, insertion, or removal. These would take O(log n) time as well, but would generate zero unnecessary garbage (instead of O(log n)). Depending on what you're doing, that difference might be desirable (I'd want it for my priority queue), or it might be unimportant, or you might actually need the side-effect-free version.

You can replace the "datum" slot in each node with "key" and "value" slots, perhaps adding a third "key-hash" slot so you can sort diverse or compound keys. This might be useful for, say, string interning, or more generally for a hash table substitute. Paul Graham says in the Arc tutorial: "I once thought alists were just a hack, but there are many things you can do with them that you can't do with hash tables, including sort them, build them up incrementally in recursive functions, have several that share the same tail, and preserve old values." Funnily, you can do all of these things with AVL trees (+key +value +key-hash) and do them in O(log n) time, except for one: if you sort them (presumably according to something other than the hash value, which they'd otherwise be sorted by), then lookups will degrade to O(n).

You can add a "count" slot to each node (and update it when inserting/removing/rebalancing), representing the number of elements in the whole subtree. count(nil) = 0, count(x) = count(x!left) + 1 + count(x!right). This would give you O(log n) access to the kth element, O(log n) insertion or deletion at the kth position (if you want it), plus an O(1) "length" function. This seems like a good general-purpose "list", actually--it beats arrays at "insertion or deletion at the kth position", and it beats normal (linked) lists at everything except lookup/insertion/removal at the head. And if we keep it sorted, then a priority queue becomes just a specific way of using it (you only use "insert-sorted" and "access/delete 0th element").

Continuing with the "count" slot, "append" seems it'd be O(log n). "reverse" would be O(n), but if you really wanted it, you could put in an extra slot, a flag that said "Consider this tree reversed"--it'd be trippy, it'd require writing reversed versions of everything--which would handle nested reverse flags--and when, say, you performed the rebalancing in the top chart and B was reversed but E wasn't, then, in the resulting tree, A and C would get "reversed" flags (and they'd switch places) and B would lose its flag... it'd be pretty ridiculous, but I believe it would work perfectly, and reversal would be O(1). It'd be awesome.

You can add a "parent" slot, a pointer to the parent node (probably nil for the root node). This commits you to destructive insertion/removal; since any part of the tree can be reached from any other part, nondestructively adding something would require copying the whole tree. What does +parent buy you? Well, I thought, it lets insertion (and probably removal) run with constant memory: you go to the bottom, insert your element, then, if needed, go up to the parent and update depth/rebalance (and if you do that, check if the parent of that needs updating; if not, terminate). The alternative (which my nondestructive code currently uses, and which destructive code without +parent would use) is to temporarily store all the nodes on the path to the bottom (implicitly, in a call stack). Upon further thought, this might not make much of a difference, because this call stack gets exactly as deep as the tree, which is approximately log_phi(n), which is 43 when n is 1 billion. I don't know, it might be worth it. It could likewise be used for iterating along the tree.

-------

The point is, there's a lot of cool stuff you can do with AVL trees. Some of it is even useful (like the priority queue, and maybe the general-purpose list). It seems there's lots of room for customizing your AVL tree to fit your problem.

A wise man apparently said, "Data dominates. If you've chosen the right data structures and organized things well, the algorithms will almost always be self-evident. Data structures, not algorithms, are central to programming." That seems to be true here: with every incarnation of AVL trees I've listed above, the ways to manipulate it have seemed clear to me (at least in specification; the implementation may take a bit of thinking).

-------

[1] You might think, "Well, if I keep the tree balanced, then I can just follow one path to the bottom, and that tells me the depth... up to an error of 1. Might that be good enough?" Suppose your left branch has depth 5 (which you correctly compute), and the right has depth 7, but you compute it to be 6, so you don't rebalance it; now your tree is unbalanced, and the next depth calculation could potentially be off by 2. By induction, your tree may become arbitrarily unbalanced.

[2] On an efficiency note: My implementation uses a hash table to represent each node. This was incredibly convenient for me: x!rt!lf is extremely terse, and changing/adding/removing slot names was easy (originally I had each node store the depths of the left and right branches; Wikipedia made me realize this was redundant). However, it consumes more memory (allocating a hash table for each node) and probably more time (doing hash table lookups to access each slot) than it really has to.

One could represent nodes as, e.g., (cons datum (cons left (cons right depth))), or (cons (cons left right) (cons datum depth)); define accessors as (in the second case) (= lf caar rt cdar dt cadr dp cddr); and replace "x!rt!lf" with (lf (rt x)), etc. Or one could use a Racket vector--define (datum node) as (vector-ref node 0), (lf node) as (vector-ref node 1), and so on. Or one could import Racket structs, and maybe add a "struct?" case for "ar-apply" in ac.scm so you can still use the x!rt!lf syntax. All of these are likely more efficient than using tables.

[3] I think the functional approach is easier for the same reason that this:

  (def insert-sorted (< x xs)
    (if (or no.xs (< x car.xs))
        (cons x xs)
        (cons car.xs (insert-sorted < x cdr.xs))))
is simpler than this:

  (def ninsert-sorted (< x xs)
    (if (or no.xs (< x car.xs))
        (cons x xs)
        (do (xloop (xs xs)
              (if (or (no cdr.xs) (< x cadr.xs))
                  (= cdr.xs (cons x cdr.xs))
                  (next cdr.xs)))
            xs)))
[4] I took my code and replaced, e.g., depth:x!lf with (depth x!lf) so this works without super-awesome ssyntax. Ad hoc shell scripts are fun.

  $ pbpaste | sed -E 's/([a-z]+):([a-z]+[.!][a-z]+)/(\1 \2)/g' | pbcopy


4 points by aw 2445 days ago | link

As an experiment I copied to the wiki: https://sites.google.com/site/arclanguagewiki/avl-trees I hope you don't mind. Being able to embed the image was nice :-)

-----

1 point by Pauan 2444 days ago | link

Hmm... I wonder if I could implement conses/lists in PyArc as AVL trees...

-----

0 points by prestonbriggs 2439 days ago | link

Your use of hash tables to represent nodes in the AVL tree bothers me a lot. Yes, you get convenient notation, but it's disgusting, both practically and algorithmically, in terms of both space and time.

To see why, re-implement your stuff in something simple, like C or assembly, then measure space and time consumption. Compare using structs for nodes versus hash tables.

Just because it's wrapped up in pretty syntax doesn't make it efficient for use in all circumstances.

Might play with a C version of alists, versus hash tables, versus binary tree while you're at it. They're all useful, but in different circumstances. Implementing every "dictionary" with one or the other data structure is a mistake. You need to choose the correct data structure to match your application. It's an interesting engineering problem.

Preston

-----

4 points by waterhouse 2438 days ago | link

What I was doing was getting the AVL tree to work (which, by the way, took a certain amount of thinking, debugging, and rewriting). Implementing them with hash tables, with convenient notation, was entirely appropriate for the task at hand. And now that I've got it in working form, it's easy to go and replace the hash table parts with structs or something. In fact, I think that was pretty clearly on my mind, because I described in footnote 2, in some detail, how one might implement the nodes using things other than hash tables. It was not my intention that the nodes should forever remain hash tables. I think you misunderstand me greatly.

And by the way, I did re-implement it in C, using structs, before I wrote the original post. Here's an excerpt.

  avl_node * node_r(st_h *d, avl_node *x, avl_node *y) {
    if (x->dp > 1+y->dp) {
      if (x->lf->dp > x->rt->dp)
        return node(x->dt, x->lf, node(d, x->rt, y));
      else return node(x->rt->dt, node(x->dt, x->lf, x->rt->lf), node(d,x->rt->rt, y)); }
    else {
      if (y->rt->dp > 1+y->lf->dp) {
        if (y->rt->dp > y->lf->dp)
  	return node(y->dt, node(d,x,y->lf), y->rt);
        else return node(y->lf->dt, node(d,x,y->lf->lf), node(y->dt, y->lf->rt, y->rt)); }
      else return node(d,x,y);
    }}
Feels good, man. (The above code, by the way, fails to free() the obsolete nodes. That could be fixed if necessary.) Fortunately, I didn't really have to debug that code; I cribbed directly from my Arc code.

-----

2 points by akkartik 2439 days ago | link

A node has a constant number of fields. Who cares what the time complexity of lookup is?

Perhaps it's inefficient in use of space. But isn't it premature optimization to worry about that?

I don't see how showing an implementation for AVL trees claims to be efficient 'in all circumstances' (what is?), or how it claims that you can use one data structure for everything.

-----

1 point by prestonbriggs 2439 days ago | link

The "constant numbers of fields" is the reason there's a better alternative.

A hash table has an _expected_ constant lookup time. But it might be as bad as O(number of fields). He blows all his O(log n) complexities by putting in an expected O(1) lookup for all his field manipulations.

It's probably premature optimization to use an AVL tree in place of an ordinary binary tree, or even an alist.

I didn't see him promoting AVL trees for all uses, but I did see him suggesting they could/should replace alists.

Of course I don't mind a guy learning about AVL trees, or anything else, by implementing them in Arc or anything else. Indeed, I recommend such exercises to everyone; we learn a lot. But my feedback regarding his implementation of the nodes stands.

Preston

-----

1 point by akkartik 2439 days ago | link

"It's probably premature optimization to use an AVL tree in place of an ordinary binary tree, or even an alist."

Yeah that makes sense, thanks for bringing that up. The constants will probably drown out anything else for small structures.

---

"A hash table has an _expected_ constant lookup time. But it might be as bad as O(number of fields)."

Let me rephrase. A node has a statically constant, small number of fields. Who cares what the time complexity of lookup is?

"He blows all his O(log n) complexities by putting in an expected O(1) lookup for all his field manipulations."

I think you mean O(k) not O(1)? Since k is not n and exactly 4, which is a small number, it's not clear this is a problem.

---

May I suggest referring to the post or idea or implementation rather than to 'the guy'? I'm also finding your use of words like 'disgusting' distracting. (unless you're really feeling flamey :)

-----

1 point by prestonbriggs 2439 days ago | link

Yeah, it is distracting and I'm sorry about that. Similarly, I'm sorry to publicly snipe, 'cause I really do admire folks who make an effort to learn by doing, and better yet, write up their experiences.

But "disgust" was the word I wanted. I can't point at his choice and say "this is all wrong". Instead, I point at it and claim that it "smells" wrong to me, I'd never do it that way, bad taste, etc. Then I tried to argue about why my taste is offended.

Regarding O(1) versus O(k), I actually wrote "expected O(1)". That is, _expected_ constant time, versus guaranteed constant time. Though your point that the number of fields is a constant, 4, is certainly true.

Preston

-----

1 point by aw 2439 days ago | link

By the way, if anyone would like to use struct's from Arc it would be easy to implement. (http://docs.racket-lang.org/guide/define-struct.html)

-----