![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
amaraoА вот я тут делал какое-то упражнение на LC, и обнаружил, что я не умею деревья. Всё понимаю, кроме того, как определять в какую ветку вставлять. Я понимаю зачем, я понимаю как работают bst, и даже понимаю как b-tree перебалансируется (и почему ему это можно делать).
А вот как в обычное дерево вставлять элементы так, чтобы получилось сбалансированное дерево, а не длинный странный список с небольшими ответвлениями - не понимаю.
Я сейчас говорю про простейшее двоичное дерево без выкрутасов и удалений. Просто вставлять так, чтобы дерево было более-менее равномерно заполнено.
Разумеется, я сейчас пойду и почитаю, но сначала я хочу осознать проблему.
Когда нам надо вставить новый элемент и мы находимся в ноде, в которой есть None в одном из направлений, всё понятно - мы туда и вставляем, потому что это самое близкое к root направление (выбирая между вставить ниже в полного соседа или вставить в другую половину "тут-и-сейчас" очевидно, что "тут-и-сейчас" даст локально оптимальнее решение).
Но когда у нас есть элемент слева и элемент справа, то мы должны выбрать куда вставлять...
Стоп. А в чём смысл куда-либо вставлять, если мы не можем найти элемент "просто так"? Получается, что "просто так деревьев" не бывает, и должна быть причина для выбора вставления влево или вправо.
На самом деле, моя задача была более узкая - у меня есть вектор с элементами, у которых есть one-to-one описание структуры дерева и мне надо его воспроизвести. Пустые элементы в списке отмечены как null. То есть мне нужно этот список хитро сканировать и обходить (на самом деле, конструировать) дерево в том порядке, как сказали.
И чуть раньше у меня была задача про in-order, которую я не понял. Кажется, тут какое-то слепое пятно у меня.
Это какая-то известная нотация для записывания деревьев в список, или мне свою надо придумать? Я сейчас попробую подумать над правилами обработки списка, может быть я сам до чего-то очевидного догадаюсь...
Пока инсайт: абстрактных сферических в вакууме деревьев не существует (особенно, на вставление и/или удаление). Дерево может быть "просто дерево" на какие-то операции с уже существующим деревом, но мы не можем построить дерево без правил его построения, то есть правила построения дерева обязательны и нет никакого "правила по-умолчанию".
А вот как в обычное дерево вставлять элементы так, чтобы получилось сбалансированное дерево, а не длинный странный список с небольшими ответвлениями - не понимаю.
Я сейчас говорю про простейшее двоичное дерево без выкрутасов и удалений. Просто вставлять так, чтобы дерево было более-менее равномерно заполнено.
Разумеется, я сейчас пойду и почитаю, но сначала я хочу осознать проблему.
Когда нам надо вставить новый элемент и мы находимся в ноде, в которой есть None в одном из направлений, всё понятно - мы туда и вставляем, потому что это самое близкое к root направление (выбирая между вставить ниже в полного соседа или вставить в другую половину "тут-и-сейчас" очевидно, что "тут-и-сейчас" даст локально оптимальнее решение).
Но когда у нас есть элемент слева и элемент справа, то мы должны выбрать куда вставлять...
Стоп. А в чём смысл куда-либо вставлять, если мы не можем найти элемент "просто так"? Получается, что "просто так деревьев" не бывает, и должна быть причина для выбора вставления влево или вправо.
На самом деле, моя задача была более узкая - у меня есть вектор с элементами, у которых есть one-to-one описание структуры дерева и мне надо его воспроизвести. Пустые элементы в списке отмечены как null. То есть мне нужно этот список хитро сканировать и обходить (на самом деле, конструировать) дерево в том порядке, как сказали.
И чуть раньше у меня была задача про in-order, которую я не понял. Кажется, тут какое-то слепое пятно у меня.
Это какая-то известная нотация для записывания деревьев в список, или мне свою надо придумать? Я сейчас попробую подумать над правилами обработки списка, может быть я сам до чего-то очевидного догадаюсь...
Пока инсайт: абстрактных сферических в вакууме деревьев не существует (особенно, на вставление и/или удаление). Дерево может быть "просто дерево" на какие-то операции с уже существующим деревом, но мы не можем построить дерево без правил его построения, то есть правила построения дерева обязательны и нет никакого "правила по-умолчанию".
no subject
Date: 2022-12-16 08:25 am (UTC)Это для binary search tree. Дерево с заданными правилами.
А просто "для дерева" правил нет. Двоичное дерево означает всего лишь разветвление на 2 бранча, в нём нет правил.
... Или есть? Вот это я и буду читать.
no subject
Date: 2022-12-16 02:12 pm (UTC)Но это не очень интересный факт, потому, что "просто дерево" ни за чем не нужно.
Деревья используются для хранения и быстрого извлечения данных. Рискну сказать, что они больше ни для чего не нужны.
no subject
Date: 2022-12-16 03:17 pm (UTC)Ну, практичность меня сейчас не интересует, я задачки на leetcode делаю, качаю одновременно Rust и структуры данных. Вот дошёл до реального слепого пятна, плавно разбираю.
"Просто дерево" мне нужно для того, чтобы написать тесты к своему коду (мне нужно по заданному представлению списка значений из теста воспроизвести дерево).
А в самом LC есть задачки типа "определить, что дерево симметричное". А какое это дерево не сказано, то есть его надо просто обходить.
no subject
Date: 2022-12-16 04:21 pm (UTC)Leetcode и все эти задачи 100% имеют смысл даже и как самоцель. По крайней мере, в 2022-2023 году...