Реализация двоичной вставки дерева [дубликат]

Question

Реализация двоичной вставки дерева [дубликат]

Чтобы найти конкретную ошибку, запустите это:

SHOW ENGINE INNODB STATUS;

И посмотрите в разделе LATEST FOREIGN KEY ERROR.

Тип данных для дочернего столбца должен точно соответствовать родительскому столбцу , Например, поскольку medicalhistory.MedicalHistoryID является INT, Patient.MedicalHistory также должен быть INT, а не SMALLINT.

Кроме того, перед запуском запроса set foreign_key_checks=0 DDL, чтобы вы могли создавать таблицы в произвольном порядке, а не создавать все родительские таблицы перед соответствующими дочерними таблицами.

12

rust binary-tree

задан Shepmaster 12 March 2018 в 21:45

4 ответа

Он работает:

fn back(&mut self) -> &mut Link {
    let mut anchor = &mut self.root;
    while anchor.is_some(){
        anchor = &mut {anchor}.as_mut().unwrap().next;
    }
    anchor
}

2

ответ дан aSpex 15 August 2018 в 23:49

Вы можете использовать рекурсию для выполнения проверки чека. Это имеет недостаток в создании фрейма стека для каждого элемента в вашем списке. Если ваш список длинный, это, безусловно, приведет к переполнению стека. LLVM оптимизирует метод Node::back в цикле (см. LLVM IR, сгенерированный на игровой площадке )

impl Node {
    fn back(&mut self) -> &mut Link {
        match self.next {
            Some(ref mut node) => node.back(),
            None => &mut self.next,
        }
    }
}

impl Recursive {
    fn back(&mut self) -> Option<&mut Link> {
        self.root.as_mut().map(|node| node.back())
    }
}

7

ответ дан oli_obk - ker 15 August 2018 в 23:49

Исходный код работает как-один раз нелексические времена жизни включены:

#![feature(nll)]

type Link = Option<Box<Node>>;

struct Node {
    next: Link
}

struct Recursive {
    root: Link
}

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;
        while let Some(node) = anchor {
            anchor = &mut node.next;
        }
        anchor
    }
}

fn main() {}

Нелексические времена жизни увеличивают точность проверки счетчика компилятора, что позволяет чтобы увидеть, что изменчивый заимствование anchor больше не используется. Мы также можем упростить ключевые слова в if let из-за недавних изменений языка.

6

ответ дан Shepmaster 15 August 2018 в 23:49

Другие вопросы по тегам:

rust binary-tree

Похожие вопросы:

score 16 · Accepted Answer

Возможно ... но мне жаль, что у меня не было более элегантного решения.

Трюк НЕ заимствовать у anchor и, следовательно, жонглировать между двумя аккумуляторами:

, в котором выполняется ссылка на текущий узел
, другому назначается ссылка на следующий узел

Это приводит меня к:

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;

        loop {
            let tmp = anchor;
            if let Some(ref mut node) = *tmp {
                anchor = &mut node.next;
            } else {
                anchor = tmp;
                break;
            }
        }

        anchor
    }
}

Не совсем красиво, но это что-то, что может проверить заемщик ¯ \ _ (ツ) _ / ¯.

@ker улучшил это, создав неназванное временное:

impl Recursive {
    fn back(&mut self) -> &mut Link {
        let mut anchor = &mut self.root;

        loop {
            match {anchor} {
                &mut Some(ref mut node) => anchor = &mut node.next,
                other => return other,
            }
        }
    }
}

Фокус здесь в том, что использование {anchor} перемещает содержимое anchor в неназванное временное, на котором выполняется совпадение. Поэтому в блоке match мы не заимствуем из anchor, а из временного, оставляя нас свободными изменять anchor. См. Связанный пост в блоге Материал, который выполняет функция идентификации (в русте) .

16

ответ дан Peter Hall 15 August 2018 в 23:49

1

Потрясающие! Просто, чтобы понять, что здесь происходит: 1) anchor имеет начальную ссылку 2) tmp перемещается из anchor, что означает, что anchor уже не является ссылкой 3) tmp может быть безопасно заимствован из-за того, что он отбрасывается, как только заканчивается итерация цикла – Fabian Knorr 23 June 2016 в 09:18
2

Самое удивительное, вот, что я изначально забыл anchor = tmp; в ветке else, и rustc поднял для него ошибку ... в любом случае, да, идея состоит в том, что вы не можете повторно назначить anchor, пока он заимствован , поэтому мы передаем ссылку на tmp, а затем заимствуем tmp, чтобы назначить anchor. – Matthieu M. 23 June 2016 в 09:23
3

Это можно на самом деле написать достаточно кратко, потому что мы можем вызвать is_some() на anchor, прежде чем перемещать его. Я отредактировал ваш пост. – Fabian Knorr 23 June 2016 в 09:35
4

Вот версия вашего решения без временных или распаковки: play.rust-lang.org/… – oli_obk - ker 23 June 2016 в 10:01
5

@FabianKnorr: Мне не нравится использовать unwrap, где я могу избежать этого, потому что, хотя он безопасен, он также является источником (потенциального) сбоя. – Matthieu M. 23 June 2016 в 11:55