[nybble41]

Unfortunately this interface is a little bit too public; it makes it possible to violate the AVL tree invariants:

    let mut tree = AVLTree::Empty;
    tree.insert(1isize);
    tree.insert(2);
    match tree {
        AVLTree::Empty => (), 
        AVLTree::NonEmpty(ref mut node) => { node.right.insert(3); },
    };  

This constructs a tree with two right-leaning nodes (1 → 2 → 3), so the balance factor of the root at the end would be +2. (It isn't stored that way, though, since the root node was never updated in the last insert.) The issue is the fact that AVLTree::NonEmpty is public by default, as the discriminant of a public enum type, so anyone can get a mutable reference to any of the inner nodes by following the fields. It's also possible to use std::mem::replace to swap pieces of two different AVLTree instances, or to change values within the tree so they are no longer in order. Wrapping the Box<Node<T>> in a private struct should fix all this without too much change to the code.

It's also possible to iterate through the AVL tree—destructively, as in IntoIter<T>—without allocating a separate stack by stashing the parent links in node.left. The implementation would look something like this: https://gist.github.com/nybble41/6c7735bd833cf7536734de06d58...