2-3 дерево , алгоритмы

[FasterHarder]

Всем хай! Сходу к делу!

Решил познакомиться с 2-3 деревом и СХОДУ при изучении пошли непонятки, т к в разных источниках по-разному описываются практически даже определения.
Вот пример 2-3 дерева.

Прикреплённая картинка

И вот еще 1 пример 2-3 дерева.

Прикреплённая картинка

И какой-то из источников точно лжет!).
--------------------------------------------
Хотелось бы для начала понять такой момент: справедливо ли утверждение, что для поиска ЛЮБОГО узла, заданного своим ключом, надо спускаться до самого нижнего уровня, т е до листьев? Если, да, то рис. №1 правилен, а №2 ложный.
К слову, бинарное дерево поиска хранит искомые ключи на любых уровнях, а не только на листовом. А еще говорят, что 2-3 деревья более совершенные, чем бинарные. Но если в 2-3 дереве ключи лежат ТОЛЬКО на нижнем уровне, то это как бы вообще разные структуры данных получается.

Нашел примеры поиска элемента в 2-3 дереве по ключу, и там есть такая фраза, что поиск продолжается, пока не вышли НА ЛИСТ. Это лишний подтверждает, что рис. №1 корректен, а №2 нет?
-----------------------------
И такой момент. В бинарке есть правило: в левом поддереве все элементы с ключами СТРОГО меньше текущего корня, а в правом БОЛЬШЕ (или равно, если допустимы дубликаты). В 2-3 дереве 3 направления: левое, центральное и правое. И тут тоже разночтения в источниках.
Источник, откуда взят рис.1 говорит, что в левое попадают ключи <= ключу левого родителя, в центральное < .. <=, а в правое >
Лучше на примере покажу, есть узел с двумя ключами (40; 80), тогда:
- в левое: key <= 40
- центральное: 40 < key <= 80
- правое: key > 80
Это верно?? (к слову, в двоичном дереве немного не так, но, возможно, это нестрогое требование для бинарок).
В др.источниках дают другое правило, например, для примера (40; 80) пишут, что в левое поддерево попадают ключи СТРОГО меньше 40 и т.д.

спс., буду признателен за любые ответы

[Akina]

Цитата FasterHarder @ 22.05.22, 01:34

справедливо ли утверждение, что для поиска ЛЮБОГО узла, заданного своим ключом, надо спускаться до самого нижнего уровня, т е до листьев?

Абсолютно правильно.

Цитата FasterHarder @ 22.05.22, 01:34

Если, да, то рис. №1 правилен, а №2 ложный.

Хуже. В общем случае оба... ну не то чтобы ложны, а просто демонстрируют один из частных случаев.

Цитата FasterHarder @ 22.05.22, 01:34

В 2-3 дереве 3 направления: левое, центральное и правое. И тут тоже разночтения в источниках.

Для границ - граница диапазона слева (в области "меньше чем") нестрогая, а справа соответственно строгая. И соответственно для значений - наоборот, значение узла может быть больше либо равно минимальному значению узла справа и всегда больше максимального значения узла слева.

[FasterHarder]

Цитата Akina @ 22.05.22, 13:36

Абсолютно правильно.

о, как! Значит, только в одном источнике правильно об этом написали (из тех источников, что просмотрел)

но я сейчас запутался ппц как)
в 99% источниках, когда ищут ключ, то поиск обрывают (return), как только встретился искомый ключ на ЛЮБОМ уровне, а не только на листовом.
Или тут я не понимаю, что речь не об этом немного, а о том, что для поиска нужного ключа требуется просмотреть ВСЕ узлы 2-3 дерева, поэтому придется спускаться до листового уровня. Или все-таки речь о том, что, если искомый ключ есть, то его нужно брать ТОЛЬКО с листового уровня?

еще такой момент. Когда говорят про 2-3 дерево, ведь подразумевают единственную структуру данных, т е нет ведь разных версий 2-3 дерева, например, простое 2-3 дерево или поисковое 2-3 дерево. 2-3 дерево единственно (поисковое как бы) и не имеет модификаций, верно?
------------------------------
вернемся к этому 2-3 дереву

Прикреплённая картинка

Например, надо найти узел с ключом = 80. Это значение лежит не на листовом уровне, поэтому поиск прекратится, как только оно будет найдено, так ведь?
С др.стороны, если это дерево неправильное, то мой вопрос уже не имеет смысла) и др.вопрос: а почему оно неправильное?
А вообще, есть какое-то концептуальное различие между ЛИСТЬЯМИ и НЕ листьями, кроме количества сыновей (у листьев их 0) и проявляется ли это различие при поиске, например?
-----------------------
вообще у меня задача на 2-4 дерево (ужс), но для начала надо хотя бы чуть-чуть понять 2-3 дерево. Информации даже про 2-3 дерево катастрофически мало + она противоречивая, про 2-4 дерево - вообще полный мрак (на хитхабе всего 1 исходник на С и тысячи, например, про бинарные деревья). Давно уже шерстю забугорные сайты про 2-3 деревья и нашел вроде хороший сайт, где куча полезной инфы про структуры данных и там позиционируют себя как экспертов в Structure Data, но их пример 2-3 дерева был таким:

Прикреплённая картинка

Это ведь НЕПРАВИЛЬНО, т к 50 нужно вставлять "по центру", а не слева.

Хочется хотя бы понять на комиксах, как все-таки правильно формируется 2-3 дерево при добавлении узлов, а также, как устроен поиск.

Добавлено 22.05.22, 14:10
насчет этого:

Цитата Akina @ 22.05.22, 13:36

Для границ - граница диапазона слева (в области "меньше чем") нестрогая, а справа соответственно строгая. И соответственно для значений - наоборот, значение узла может быть больше либо равно минимальному значению узла справа и всегда больше максимального значения узла слева.

вроде тут правильно понимаю, т е:

Цитата FasterHarder @ 22.05.22, 01:34

есть узел с двумя ключами (40; 80), тогда:
- в левое: key <= 40
- центральное: 40 < key <= 80
- правое: key > 80

хотя может и нет), но это пока ладно, потихоньку допойму, наверное...

[FasterHarder]

а вот и пример поиска, когда спускаются СТРОГО до листового уровня:

Прикреплённая картинка

интересно, даже нет проверки на == заданному ключу, просто спускаются ВНИЗ по 2-3 дереву до листового уровня и возвращают ЛИСТ в качестве ответа.
Т е после вызова этой функции придется проверить, есть в этом узле заданный ключ, что ли. Хм..

[Majestio]

Цитата FasterHarder @ 22.05.22, 14:06

С др.стороны, если это дерево неправильное

Стало интересно, зашел в построитель и построил дерево с данными цифрами - ровно так и построилось, как на рисунке.

Цитата FasterHarder @ 22.05.22, 14:06

А вообще, есть какое-то концептуальное различие между ЛИСТЬЯМИ и НЕ листьями, кроме количества сыновей (у листьев их 0) и проявляется ли это различие при поиске, например?

Мне кажется - хороший ответ есть в вики, а именно в перечислении свойств такого дерева есть пункт четко про листья:

Цитата

Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 поля.

[FasterHarder]

Цитата Majestio @ 22.05.22, 15:50

Мне кажется - хороший ответ есть в вики

это понятно
у меня даже исходник есть под 1К строк кода (с которым потихоньку разбираюсь)
но всякие нюансы с этим листовым уровнем при поиске и пр.

ГЛОБАЛЬНО, мне понятно, что такое 2-3 дерево (и даже 2-4, т к оно чуть "ширее"), но тут в деталях все проблемы...

[Akina]

Цитата FasterHarder @ 22.05.22, 14:06

нет ведь разных версий 2-3 дерева

Ну как же нет-то? когда два твои рисунка в исходном посте демонстрируют два принципиально разных дерева. Первый рисунок демонстрирует дерево, допускающее дубликаты, тогда как второй рисунок дубликатов не содержит. Принципиально это или просто значения такие попались - неизвестно. Также неизвестна и задача - если дубликаты допустимы, то ищется любой элемент с заданным значением или все таковые.

Если дубликатов нет, все значения уникальны - то да, как нашли, так и стоп. Если есть и нужен хоть какой - то опять как нашли, так и стоп. А если нужны все дубли - то будь любезен прогуляться до донышка. И, поскольку это наиболее общий вариант, то и говорят, что в общем случае следует опуститься в самый низ и исследовать все листы (что, впрочем, не утверждает, что требуемые значения будут взяты именно с нижнего уровня).

Да, чисто ремаркой следует добавить, что формально все значения в дереве должны быть уникальны. Не при сравнении - при сравнении они могут быть и равны, а принципиально они должны быть различимы. Например, в твоём самом первом рисунке имеется две двойки. Это разные двойки, а не одна и та же двойка. Например, одна из них покрашена красным, другая синим - но обе они двойки и равны, но в то же время различимы. И дерево соответственно может быть построено двумя способами, при одном красная двойка наверху, при другом внизу. Но поскольку мы оперируем только значениями, то с точки зрения построения дерева это одно и то же дерево.

Сообщение отредактировано: Akina - 23.05.22, 04:40

[FasterHarder]

Akina, спс за развернутое пояснение
Majestio, спс за онлайн-построитель - удобная штука для проверки

Двоичные деревья поиска при одинаковых входных данных ВСЕГДА имеют одинаковую топологию.
2-3 деревья вроде аналогично
А вот 2-3-4 деревья, наверное, нет. Пример. На вход подают ключи: 20, 30, 40, 50.
При добавлении первых трех, будет 1 узел (корень, по сути): [ 20, 30, 40 ]
При вставке 50 надо расщеплять и возможны вроде такие варианты:
[ 20 ]
[ 10 ] [ 30, 40 ]

или
[ 30 ]
[ 10, 20 ] [ 40 ]

И еще такой вопрос общего характера по 2-3 деревьям. Существует ли конкретная задача, когда просто идеально подходят именно 2-3 деревья, не бинарные, не 2-4, не 3-6 и т.д., а именно 2-3 tree?

спс

[Akina]

Цитата FasterHarder @ 24.05.22, 08:58

При вставке 50 надо расщеплять и возможны вроде такие варианты

Ну очень формально да. А на практике расщепление - это всегда на две части.

Цитата FasterHarder @ 24.05.22, 08:58

Существует ли конкретная задача, когда просто идеально подходят именно 2-3 деревья

Да. Статистически именно 2-3 дерево обеспечивает минимизацию количества сравнений (оптимум - это когда соотношение количества значений к количеству нод равно e=2.718..). ЕМНИП...

Сообщение отредактировано: Akina - 24.05.22, 09:18

[FasterHarder]

Akina, спс за пояснения.

в целом немного разобрался с операциями в этом дереве, закодировать быстро, а главное правильно не смогу, но куда копать и как - уже понятнее.
ИМХО: деревья и графы - самые интереснейшие структуры данных, хотя кто их знает, этих структур "триллиарды"). С др. стороны ведь вроде считается, что ВСЕ есть граф так или иначе...

[FasterHarder]

Раз уж здесь вопросы по n-m-.. деревья, то хочется уточнить еще такой момент.

В инете видел буквально 1 упоминание 1-2 дерева.
Правильно ли я понимаю следующие моменты:
1. 1-2 дерево - очень похоже на бинарное дерево поиска , но есть нюансы...
2. 1-2 дерево - почти сбалансированное бинарное дерево поиска ( кстати, такие ведь деревья называются AVL вроде )
3. Ключевое отличие 1-2 дерева от AVL-дерева в том, что у 1-2 дерева ВСЕ листья ( до единого ) лежат НА ОДНОМ УРОВНЕ ( самом нижнем ), а у AVL допустим перекос на 1.

Т е к 1-2 дереву ближе всего ( из семейства древовидных ) стоит именно AVL-дерево?
-------------------------
Доп. вопрос ( для ради любопытства ): а есть деревья, которые как AVL, но не бинарные, а, например, 2-3, т е типа 2-3-AVL дерево? Или это все растет из B-деревьев, но у этих сильноветвящихся деревьев все листья находятся на одном уровне...

p.s. где-то здесь рядом еще "гуляет" термин ИСД ( идеально сбалансированное дерево )

Сообщение отредактировано: FasterHarder - 09.06.22, 03:32