Trying to implement Binary tree data structure with all operations - creating, inserting, deleting, searching etc. in a mutable way, ie. without recreating tree but do changes in-place.

type definition:

pub trait Elem: PartialOrd + Clone + Debug {}
impl<T: PartialOrd + Debug + Clone> Elem for T {}

#[derive(Debug, Default, PartialEq)]
pub enum BinTree<T: Elem> {
    #[default]
    Empty,
    Node {
        value: T,
        left: Box<BinTree<T>>,
        right: Box<BinTree<T>>,
    },
}

insertion of an element was straightforward, using mutable reference:

impl<T: Elem> BinTree<T> {
    pub fn insert(&mut self, val: T) -> bool {
        match self {
            Self::Empty => {
                *self = Self::Node {
                    value: val,
                    left: Box::new(Self::Empty),
                    right: Box::new(Self::Empty),
                };
                true
            }
            Self::Node { value, left, right } => {
                if val < *value {
                    left.insert(val);
                } else if val > *value {
                    right.insert(val);
                } else {
                    return false
                };
                true
            }
        }
    }

now there is a struggle with deletion of an element, where subtree (behind Box) has to be moved - rebound. Shortened for simplicity:

pub fn delete(&mut self, val: T) -> bool {
match self {
Self::Empty => false,
&mut BinTree::Node {
ref value,
ref mut left,
ref mut right
} => if val == *value {
*self = **left; // do I really need a clone of BinTree here??
true
} else {
false
},
}
}

error[E0507]: cannot move out of **left which is behind a mutable reference
--> src/lib.rs:100:25
|
100 | *self = **left;
| ^^^^^^ move occurs because **left has type BinTree<T>, which does not implement the Copy trait

Can the re-assignment of a subbranch be rewritten in another way, without resolve to its cloning?

2 posts - 2 participants

Read full topic