![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
деревья, часть 3
Dec. 19th, 2022 06:32 pmВ прошлом посте я придумал обход в ширину, а llivejo справедливо указал, что при наличии dequeue необходимости в "двух списках" нет, и можно обойтись одним. True.
В этой части я думаю о том, как научиться строить деревья из вот такой записи:
[1,2,2,null,3,null,3]
null означает "ничего", то есть соответствующего потомка у узла нет. Какого потомка? Видимо, того, который может быть.
В списке, как мне кажется, обратный "обход в ширину", в котором мы складываем в dequeue (double ended queue) всех потомков от созданного нами узла. Когда мы делаем pop_front мы берём ближайшего потомка, вставляем в него значение, которое нам сказали (в списке), а двух его потомков кладём в push_back этой самой dequeue.
Если в списке null, то мы этого потомка пропускаем (не вставляем в него ничего, и потомков у этого потомка тоже нет).
В реализации в rust возникает очень тонкая интересная деталь: у нас дерево описывается как
Т.е. "потомки" узла - это банальные None в структуре предка. Нам нечего "класть" в dequeue. С другой стороны, такая же проблема есть и в С, в которой NULL'ы. Как ещё решают? Двойным указателем?
Теоретически же, мы можем в Rust делат mem:swap между None и другим Some, если у нас есть mut ref. Мне собирать mut ref'ы от потомков (None) и делать им mem:swap на Some с новым значением? Звучит как очень... извращённо.
Но при этом мы не можем просто работать с текущим узлом, потому что нам нужна "развёртка" (нам надо пройти весь текущий слой перед тем, как переходить к следующему, и мы не знаем какой следующий слой).
Мы можем сделать наоборот, мы можем делать итерацию в обратном порядке. Мы делаем из "нижнего" слоя простые "одноэлементные" деревья. Но когда начинается новый слой? Мы не знаем.
... В то же самое время, я не могу использовать "послойный" алгоритм при прямом сканировании, потому что я, опять же, из списка не вижу, когда начинается следующий слой. Таким образом, dequeue - единственный разумный вариант.
Мне трудно размахивать руками, видимо, я попробую сделать версию с std::mem::swap (заодно наемся borrow checker'а и пойму насколько это sound), а после этого ...
Стоп. У меня же Option<Rc<RefCell<TreeNode>>>, а не Option<Box<TreeNode>>.
В этой части я думаю о том, как научиться строить деревья из вот такой записи:
[1,2,2,null,3,null,3]
null означает "ничего", то есть соответствующего потомка у узла нет. Какого потомка? Видимо, того, который может быть.
В списке, как мне кажется, обратный "обход в ширину", в котором мы складываем в dequeue (double ended queue) всех потомков от созданного нами узла. Когда мы делаем pop_front мы берём ближайшего потомка, вставляем в него значение, которое нам сказали (в списке), а двух его потомков кладём в push_back этой самой dequeue.
Если в списке null, то мы этого потомка пропускаем (не вставляем в него ничего, и потомков у этого потомка тоже нет).
В реализации в rust возникает очень тонкая интересная деталь: у нас дерево описывается как
// pub struct TreeNode {
// pub val: i32,
// pub left: Option<Rc<RefCell<TreeNode>>>,
// pub right: Option<Rc<RefCell<TreeNode>>>,
// }
//
// impl TreeNode {
// #[inline]
// pub fn new(val: i32) -> Self {
// TreeNode {
// val,
// left: None,
// right: None
// }
// }
// }
Т.е. "потомки" узла - это банальные None в структуре предка. Нам нечего "класть" в dequeue. С другой стороны, такая же проблема есть и в С, в которой NULL'ы. Как ещё решают? Двойным указателем?
Теоретически же, мы можем в Rust делат mem:swap между None и другим Some, если у нас есть mut ref. Мне собирать mut ref'ы от потомков (None) и делать им mem:swap на Some с новым значением? Звучит как очень... извращённо.
Но при этом мы не можем просто работать с текущим узлом, потому что нам нужна "развёртка" (нам надо пройти весь текущий слой перед тем, как переходить к следующему, и мы не знаем какой следующий слой).
Мы можем сделать наоборот, мы можем делать итерацию в обратном порядке. Мы делаем из "нижнего" слоя простые "одноэлементные" деревья. Но когда начинается новый слой? Мы не знаем.
... В то же самое время, я не могу использовать "послойный" алгоритм при прямом сканировании, потому что я, опять же, из списка не вижу, когда начинается следующий слой. Таким образом, dequeue - единственный разумный вариант.
Мне трудно размахивать руками, видимо, я попробую сделать версию с std::mem::swap (заодно наемся borrow checker'а и пойму насколько это sound), а после этого ...
Стоп. У меня же Option<Rc<RefCell<TreeNode>>>, а не Option<Box<TreeNode>>.
Моё рассуждение базировалось на option-box-node, то есть ситуации, когда у меня может быть только один mut ref к узлу. А тут - rc/refcell, что, в каком-то смысле, чит с runtime GC. Я могу хранить множественные weak ref'ы для модификации, и превращать их в strong ref'ы в момент вставки (upgrade).
Хотя, ... у меня всё равно Option в начале. Это означает, что left: None (right: None), и мы имеем mut ref Option, который обычный ref без выкрутасов. Возвращаюсь к mem::swap.