Итеративное двоичное дерево поиска с использованием enum и match

Question

Я новичок, так что терпите меня.

Учитывая следующее определение перечисления для BST.

enum Tree {
    Node(i64, Box<Tree>, Box<Tree>),
    Nil,
}

Я хочу реализовать Tree::insert. Вот что у меня так далеко. (Готовьтесь к спагетти).

impl Tree {
    fn new() -> Tree {
        Nil
    }

    fn insert(self: &mut Tree, new_val: i64) -> Tree {
        let mut temp = self;
        loop {
            match *temp {
                Node(val, ref mut left, ref mut right) => /* go left is smaller, else go right*/,
                Nil => { break; },
            }
        }
        /* create new node and have the left or right pointer of the leaf point to it  */
        return *self;
    }

Я понимаю, как бы реализовать это с функциональным стилем, где я создаю новое дерево, каждый вызов с левым и правым поддеревом, являющийся результатом рекурсивного вызова для вставки на соответствующем поддереве. Я также думаю, что я мог бы реализовать это легче с помощью структуры. Но я хочу использовать это сочетание стилей.

На то, что меня смущает ...

Концептуально, я хочу сослаться на root, а затем продолжить мутировать эту ссылку на левое или правое поддеревья, как я бы если бы я написал это на C ++. Но из-за заимствования семантики я не могу перейти к левому и правому поддереву, сделав копию ссылки. Кроме того, ржавчина, кажется, не дает мне доступ к указателям в той же степени, что и C / C ++, и я, как правило, запутался как черт.

Какие-нибудь советы относительно того, что мне нужно сделать, чтобы этот фрагмент кода работал, не сдаваясь и не переходя к функциональному стилю или созданию структуры? Заранее спасибо.

Answer 1

Может быть, что-то вроде следующего?

fn insert(self: &mut Tree, new_val: i64) {
    let mut temp : &mut Tree = self;
    loop {
        temp = match temp {
            Tree::Node(val, ref mut left, ref mut right) => {
                if new_val<*val {
                    left.as_mut()
                } else {
                    right.as_mut()
                }
            },
            Tree::Nil => { break; },
        }
    }
    *temp = Tree::Node(new_val, Box::new(Tree::Nil), Box::new(Tree::Nil))
}