News for hackers. Stuff that matters.
Re:AVL tree implementation for Rust learning by nybble41 on Thursday April 09, 2020 @11:19PM (#22829687)
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...

Re:AVL tree implementation for Rust learning by aewens on Thursday April 09, 2020 @11:11AM (#22823281)
If this was made for the context of learning Rust, wouldn't it help to have the README explaining the code or at the very least have comments in the code showing what is going on and why for those who are new to Rust and trying to learn / understand it?
Re:AVL tree implementation for Rust learning by kadoban on Thursday April 09, 2020 @12:05PM (#22823851)
Maybe.

It does look like pretty easy to understand code though, which can be quite educational coming into a new language.

You'd probably need to understand AVL trees fairly well first, but there should be quite a few who do.