На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
  
> 2-3 дерево , алгоритмы
    Всем хай! Сходу к делу!

    Решил познакомиться с 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 и т.д.

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

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

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

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

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

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

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

        но я сейчас запутался ппц как)
        в 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 дерево при добавлении узлов, а также, как устроен поиск.

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


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


        хотя может и нет), но это пока ладно, потихоньку допойму, наверное...
          а вот и пример поиска, когда спускаются СТРОГО до листового уровня:
          Прикреплённая картинка
          Прикреплённая картинка

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

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

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

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

            Цитата
            Все листовые вершины находятся на одном уровне (на нижнем уровне) и содержат 1 или 2 поля.
              Цитата Majestio @
              Мне кажется - хороший ответ есть в вики

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

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

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

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

                Да, чисто ремаркой следует добавить, что формально все значения в дереве должны быть уникальны. Не при сравнении - при сравнении они могут быть и равны, а принципиально они должны быть различимы. Например, в твоём самом первом рисунке имеется две двойки. Это разные двойки, а не одна и та же двойка. Например, одна из них покрашена красным, другая синим - но обе они двойки и равны, но в то же время различимы. И дерево соответственно может быть построено двумя способами, при одном красная двойка наверху, при другом внизу. Но поскольку мы оперируем только значениями, то с точки зрения построения дерева это одно и то же дерево.
                Сообщение отредактировано: Akina -
                  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?

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

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

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

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

                      в целом немного разобрался с операциями в этом дереве, закодировать быстро, а главное правильно не смогу, но куда копать и как - уже понятнее.
                      ИМХО: деревья и графы - самые интереснейшие структуры данных, хотя кто их знает, этих структур "триллиарды"). С др. стороны ведь вроде считается, что ВСЕ есть граф так или иначе...
                        Раз уж здесь вопросы по 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 -
                        0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                        0 пользователей:


                        Рейтинг@Mail.ru
                        [ Script execution time: 0,1219 ]   [ 21 queries used ]   [ Generated: 28.03.24, 17:32 GMT ]