![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
Деревья, часть 2
Dec. 16th, 2022 11:26 amПродолжаю раскапывать своё незнание.
В предыдущей части я обнаружил, что в общем случае, для дерева не существует "обобщённой" операции вставки, у каждого типа дерева своё правило вставки.
А сегодня я задумался про обход деревьев, и понял, что я вообще не думал про этот вопрос. Я уже нашёл какую-то методичку, так что рассуждения будут не "с нуля", но методичка невнятная и на русском, так что подумать самому всё таки можно.
Три простых рекурсивных варианта описывают pre/post/in-order. Дерево (обыкновенное двоичное дерево) состоит из left, value, right (где left/right - это два поддерева, а value - это сохраняемое значение).
Когда мы начинаем рекурсивно работать с заданным узлом дерева, у нас есть возможность менять порядок, в котором мы ...
А вот тут давайте проговорим, что "мы делаем". Для значения (value) - это операция над значением (которая его меняет или сравнивает, или даже хотя бы просто читает), условно говоря "скалярная операция". А вот для поддерева (левого или правого) единственная доступная операция - это рекурсия, то есть "нырнуть" в поддерево.
то есть код выглядит так:
{ dive(right), dive(left), do_somehing(value) }
(это set, неупорядоченное множество операций).
Упорядочивание этих операций очень важно, потому что две из них рекурсивные и одна не рекурсивная, и порядок выполнения операций может сильно изменить "маршрут" по дереву.
Итак, первый вариант:
left, value, right. Этот порядок называется - in-order. Мы сначала стремимся влево (всё время ныряя глубже, глубже и глубже), потом, достигнув левого листа (то есть узла без левого потомка), мы возвращаемся обратно, смотрим на значение (это тривиально в контексте одного узла, но не тривиально в контексте дерева, поскольку эта операция выполняется снова и снова), и ныряем в правое дерево.
Второй вариант - value, left, right. Насколько я понял, это называется pre-order, и он означает, что мы всё время смотрим на самое просто достижимое значение (тут-и-сейчас) - value, а только потом разглядываем значения. Если мы занимаемся поиском (то есть обход дерева может быть не полным), то это позволяет остановиться раньше (если искомое значение в корне, то мы найдём его в первую же операцию, без "ныряния" в левое поддерево).
Если же мы выполняем какую-то in-pace операцию над каждым значением (+1 всем, либо сериализация), то порядок обхода становится не важным с точки зрения числа операций.
И, наконец, есть вариант left, right, value. Мне пока трудно понять какие интересные свойства у такого дерева. Просто признаю, что он есть.
Далее, в литературе упоминается "обход в ширину". Насколько я понимаю, при таком обходе, дерево обходится слоями. Сначала корень (value), потом dive(left, 1), внутри которого обрабатывается value на этом уровне, возврат на нулевой уровень, dive (right, 1), value на этом уровне, возврат, потом dive(left, 2) (который в свою очередь делает dive (left, 1) и dive (right, 1), потом dive (right,2) -> dive(left, 1), dive (right, 2).
Такой вариант обхода требует либо много раз проходить по дереву туда/сюда dive(left, 1), dive(left, 2), dive(left, 424242) потребует много-много-много раз пройти левое дерево, либо... Либо там есть какой-то алгоритм, которого я не знаю.
Например, для сканирования n'ого уровня нам надо посетить 2^n узлов. Мы (находясь на n-1 уровне) выделяем вектор на 2^n значений, сканируем наш (текущий) вектор из 2^(n-1) значений, и заполняем этот вектор ссылками на узлы n'ого уровня. Ещё мы что-то делаем со значениями value на нашем n-1 уровне. После чего переходим к n'ому уровню, которому надо посеить 2^(n+1) узлов..
... часть узлов может не содержать потомков, а часть может содержать. На самом деле, это просто: мы не включаем в обход пустоту, то есть в целом, если мы используем саморастущий вектор, то мы просто идём по предыдущему вектору, и делаем push для всех потомков.
Окей, хорошо. В каждый момент времени нам надо столько памяти, сколько есть на текущем и следующем уровне.
Кажется, я придумал обход в ширину.
Теперь мне нужно научиться из литкодового описания деревьев [1,2,null, 3, 4, null, null, 5, 6] строить дерево, для этого нужно придумать, что именно этот null кодирует и как его интерпретировать.
В предыдущей части я обнаружил, что в общем случае, для дерева не существует "обобщённой" операции вставки, у каждого типа дерева своё правило вставки.
А сегодня я задумался про обход деревьев, и понял, что я вообще не думал про этот вопрос. Я уже нашёл какую-то методичку, так что рассуждения будут не "с нуля", но методичка невнятная и на русском, так что подумать самому всё таки можно.
Три простых рекурсивных варианта описывают pre/post/in-order. Дерево (обыкновенное двоичное дерево) состоит из left, value, right (где left/right - это два поддерева, а value - это сохраняемое значение).
Когда мы начинаем рекурсивно работать с заданным узлом дерева, у нас есть возможность менять порядок, в котором мы ...
А вот тут давайте проговорим, что "мы делаем". Для значения (value) - это операция над значением (которая его меняет или сравнивает, или даже хотя бы просто читает), условно говоря "скалярная операция". А вот для поддерева (левого или правого) единственная доступная операция - это рекурсия, то есть "нырнуть" в поддерево.
то есть код выглядит так:
{ dive(right), dive(left), do_somehing(value) }
(это set, неупорядоченное множество операций).
Упорядочивание этих операций очень важно, потому что две из них рекурсивные и одна не рекурсивная, и порядок выполнения операций может сильно изменить "маршрут" по дереву.
Итак, первый вариант:
left, value, right. Этот порядок называется - in-order. Мы сначала стремимся влево (всё время ныряя глубже, глубже и глубже), потом, достигнув левого листа (то есть узла без левого потомка), мы возвращаемся обратно, смотрим на значение (это тривиально в контексте одного узла, но не тривиально в контексте дерева, поскольку эта операция выполняется снова и снова), и ныряем в правое дерево.
Второй вариант - value, left, right. Насколько я понял, это называется pre-order, и он означает, что мы всё время смотрим на самое просто достижимое значение (тут-и-сейчас) - value, а только потом разглядываем значения. Если мы занимаемся поиском (то есть обход дерева может быть не полным), то это позволяет остановиться раньше (если искомое значение в корне, то мы найдём его в первую же операцию, без "ныряния" в левое поддерево).
Если же мы выполняем какую-то in-pace операцию над каждым значением (+1 всем, либо сериализация), то порядок обхода становится не важным с точки зрения числа операций.
И, наконец, есть вариант left, right, value. Мне пока трудно понять какие интересные свойства у такого дерева. Просто признаю, что он есть.
Далее, в литературе упоминается "обход в ширину". Насколько я понимаю, при таком обходе, дерево обходится слоями. Сначала корень (value), потом dive(left, 1), внутри которого обрабатывается value на этом уровне, возврат на нулевой уровень, dive (right, 1), value на этом уровне, возврат, потом dive(left, 2) (который в свою очередь делает dive (left, 1) и dive (right, 1), потом dive (right,2) -> dive(left, 1), dive (right, 2).
Такой вариант обхода требует либо много раз проходить по дереву туда/сюда dive(left, 1), dive(left, 2), dive(left, 424242) потребует много-много-много раз пройти левое дерево, либо... Либо там есть какой-то алгоритм, которого я не знаю.
Например, для сканирования n'ого уровня нам надо посетить 2^n узлов. Мы (находясь на n-1 уровне) выделяем вектор на 2^n значений, сканируем наш (текущий) вектор из 2^(n-1) значений, и заполняем этот вектор ссылками на узлы n'ого уровня. Ещё мы что-то делаем со значениями value на нашем n-1 уровне. После чего переходим к n'ому уровню, которому надо посеить 2^(n+1) узлов..
... часть узлов может не содержать потомков, а часть может содержать. На самом деле, это просто: мы не включаем в обход пустоту, то есть в целом, если мы используем саморастущий вектор, то мы просто идём по предыдущему вектору, и делаем push для всех потомков.
Окей, хорошо. В каждый момент времени нам надо столько памяти, сколько есть на текущем и следующем уровне.
Кажется, я придумал обход в ширину.
Теперь мне нужно научиться из литкодового описания деревьев [1,2,null, 3, 4, null, null, 5, 6] строить дерево, для этого нужно придумать, что именно этот null кодирует и как его интерпретировать.