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

[amarao]

Я научился из списка 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

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

Comments

[eterevsky]

А почему не получается поддеревья хранить в Option<Box<TreeNode>>? Зачем тут Rc?