Древесные истории

Я научился из списка leetcode'а делать дерево! Это было невероятно тяжело, и Rust в этом месте показал learning curve в районе over 60°. Зато к финалу я стал много лучше чувствовать ownership/borrow, особенно, в контексте Rc/RefCell.

Примерно через три часа размышлений о том, как совместить VecDeqeue.get и VecDequeue.pop_front, я понял, что я не могу решать проблему, игнория существование и свойства Rc<RefCell<TreeNode>>. До этого момента я пытался обойтись голым Option, не используя свойства Rc.

Потом я написал функцию mktreefull, которая не умеет несбалансированные деревья (то есть у каждой ноды заполнены оба потомка). В этот момент я почувствовал свет истины.

Потом я ушёл писать walk, чтобы проверить, что я написал правильно, и опять застрял в "получении значения из Rc<RefCell> без .borrow()". И вот тут-то на меня снизошло понимание, что нельзя их использовать без borrow, и все мои выкрутасы тут - фигня.

Я на 99% уверен, что мой алгоритм настолько далёк от компактного, насколько можно, но вот он в двух словах.

У нас есть тип (дерева):

pub struct TreeNode {

pub val: i32,

pub left: Option<Rc<RefCell<TreeNode>>>,

pub right: Option<Rc<RefCell<TreeNode>>>,

}

type Tree = Option<Rc<RefCell<TreeNode>>>;

Нам надо читая список вида

Some(1),
Some(2), Some(3),
Some(4), None, None, Some(7),
Some(8),

Собрать дерево. Вот такое:


1
2 3
4 None None 7
8 None None None
None None

(каждая строка - уровень дерева) Можно заметить, что вывод похож на вход, хотя None больше, потому что в компактном вводе "оставшиеся None" не указываются.

Идея, которая у меня не взлетела - класть в VecDeque left и right ноды (None) и заменять из с помощью mem::swap.
Новая идея, которая сработала: вместо сохранения потомков у узла, сохранять сам узел, и обрабатывать его дважды (для левой и правой части). Грубо говоря, для левой части мы делаем push_back(cur.left), push_front(cur). А когда делаем push_back(curl.right), то не делать push_front(cur). Когда мы обрабатываем новое значение, мы смотрим на текущее значение curl.left, и если оно пустое, то это обработка левого поддерва, если не пустое - правого.

Это работало для сбалансированного дерева. Для несбалансированного дерева мы, обрабатывая значения можем получить None, то есть "левый лист не нужен". В этой ситуации, если мы сделаем в следующю итерацию проверку на cur.left.is_none, то получим, что left is none, то есть надо идти на лево, хотя надо было на право.

Чтобы решить эту проблему я сделал enum для состояния узла в VecDeque:

enum NodeState {

Left(Tree),

Right(Tree),

}

impl NodeState {

fn new(t: &Tree) -> Self {

NodeState::Left(t.as_ref().cloned())

}

}

Заметим, тут же происходит магия Rc/RefCell, я использую t.as_ref.cloned.

напоминаю, что

type Tree = Option<Rc<RefCell<TreeNode>>>;

то есть t.as_ref превращает &Option<Rc<RefCell<TreeNode>>> в Option<&Rc<RefCell<TreeNode>>>.
Потом мы дёргаем cloned, что проходит в Rc (сквозь Option за счёт трейта Deref, насколько я понимаю) и это делает магию Rc, то есть приводит к появлению +1 на счётчике и ещё одной ссылки (вместо клонирования содержимого). Я вытащил этот самый as_ref().cloned() в реализацию NodeState просто, чтобы сэкономить нажатие кнопок в основной функции.

Дальше у нас простая state machine:

let cur = buff.pop_front().unwrap();

match cur {

NodeState::Left(Some(node)) => {...},

NodeState::Right(Some(node)) => {...},

_ => {panic!();}
}

 

 

В которой у нас разное поведение для left и right. Если мы в left, то мы кладём в конец новый узел, а в голову возвращаем текущую ноду, но в состоянии 'Right'.
В Right мы кладём новый узел в голову, а текущий узел уже никуда не добавляем.

Ну, и, разумеется, в текущей ноде поддеревья попадают в разные стороны.

Процесс модификации текущей ноды целиком зависит от магии Rc (мы делаем borrow_mut из немутабельной ссылки):

node.borrow_mut().left = subtree;

Повторю, я на 100% уверен, что есть более элегантные решения, но у этого есть неоспоримое достоинство - я его сам думал целиком, а заодно учился жить с Rc/RefCell.

Код: https://github.com/amarao/leetcode-tree-build/blob/master/src/main.rs#L41

А вот теперь, я пойду читать как эту проблему решают взрослые мальчики.

post-tree

Интернеты говорят, что во-первых Rc<RefCell> не идиоматично для Rust (деревья правильно держать как банальные вектора, содержащие в себе вектора векторов). Во-вторых, я, в целом, всё правильно сделал.

После некоторого кумекания получилось вот так вот, и я не вижу как его сделать существенно компактнее. Может быть, можно уйти от Enum и бального true/false хватит?

Да, получилось.

fn mktree(source: &[Option<i32>]) -> Tree {

if source.is_empty() || source[0].is_none() {

return None;

}

let tree: Tree = new_tree(source[0].unwrap());

let mut buff = VecDeque::new();

buff.push_back((tree.as_ref().cloned(), false));

for val in source[1..].into_iter() {

let subtree = val.and_then(|val| {

let subtree = new_tree(val);

buff.push_back((subtree.as_ref().cloned(), false));

subtree

});

let (node, is_last) = buff.pop_front().unwrap();

if is_last {

node.unwrap().borrow_mut().right = subtree;

} else {

node.as_ref().unwrap().borrow_mut().left = subtree;

buff.push_front((node.as_ref().cloned(), true));

}

}

tree

}

Что меня смущает? Изобилие as_ref().cloned(). Ща буду думать...