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

    Помогите составить полнейший список операций, которые можно производить над ДДП.
    Анализируя ДДП и лазая по различным форумам понял, что встречаются достаточно специфические операции/алгоритмы, о которых формально нигде не говорится!
    Вот прикидочный список "моих" операций:
    ExpandedWrap disabled
      1. Добавление узла в ДДП
      2. Удаление узла из ДДП по ключу
      3. Поиск узла в ДДП по ключу
      4. Обход ДДП в прямом порядке (узел - влево - вправо)
      5. Обход ДДП в симметричном порядке (влево - узел - вправо)
      6. Обход ДДП в обратном порядке (влево - вправо - узел)
      7. Подсчет количества листьев в ДДП
      8. Подсчет количества неполных узлов в ДДП
      9. Подсчет количества полных узлов в ДДП
      10. Подсчет общего количества узлов в ДДП
      11. Нахождение узла с минимальным/максимальным ключом
      12. Балансировка ДДП(*)
      13. Удаление всех узлов из ДДП (очистка дерева)
      14. Определение высоты ДДП (корень располагается на уровне №1)
      15. Визуализация ключей узлов ДДП на экране, соблюдая иерархию уровней
      16. Получение количества узлов в ДДП на заданном уровне/всех уровнях
      17. Поуровненевый вывод ключей узлов ДДП ("горизонтальный" обход)
      18. Получение значения ключа корня ДДП
      19. Удаление дубликатных узлов в ДДП (удаление узлов, имеющих совпадающие ключи)
      20. Разбиение ДДП на два ДДП по ключу (в одном дереве ключи < key, в другом - >= key)
      21. Слияние двух ДДП
      22. Определение статуса заданного узла (лист, неполный, полный)
      23. Определение родительского узла для заданного узла (корень - исключение)
      24. Подсчет количества вхождений вершины с заданным ключом


    Небольшие уточнения:
    1. Лист - узел, у которого левая и правая ссылка указывают в NULL. Неполный узел - узел, имеющий либо левого, либо правого сына. Полный узел - узел, имеющий обоих потомков.
    2. Не имеет смысла указывать операцию, которая будет находить среднее значение ключей, т к это "разновидность" поиска МИН/МАКС значения и пр. Т е операция должна принципиально обрабатывать ДДП по-другому
    3. Зачем мне это нужно? Хочу разобраться с ДДП фундаментально, т к скоро предстоит с ними плотная работа.
    4. Операцию "Балансировка ДДП" поставил под звездочкой, т к балансировать ДДП ведь не имеет вроде смысла, т к тогда лучше использовать AVL!
    Сообщение отредактировано: FasterHarder -
      ИМХО:

      1) Пункты 7-10 являются версиями пункта 16.
      2) Не упомянуты:
      - Перенос (перемещение) узла.
      - Формирование абсолютного/относительного пути узла.
        Нахождение минимального общего предка двух узлов

        Цитата
        Операцию "Балансировка ДДП" поставил под звездочкой, т к балансировать ДДП ведь не имеет вроде смысла, т к тогда лучше использовать AVL!


        Самобалансирующихся деревьев много видов. А здесь можно указать задачу создания сбалансированного дерева из сортированного массива.
          Цитата Akina @
          - Перенос (перемещение) узла.

          Akina, а можешь пояснить чуть детальней алгоритм, т е куда перемещается выбранный узел?

          Цитата Akina @
          - Формирование абсолютного/относительного пути узла.

          Отличная операция! Причем можно создать 2 варианта: от корня до узла и от узла до корня (но это детали реализации, т к в одном случае рекурсия на спуске, в др. на возврате)

          Цитата MBo @
          Нахождение минимального общего предка двух узлов

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

          Цитата MBo @
          Самобалансирующихся деревьев много видов.

          имхо, нельзя ДДП делать самобалансирующимся, т к по определению этот вид деревьев не обладает таким свойством. Я имел в виду под балансировкой, когда пользователь берет ДДП и запускает его балансировку принудительно(причем можно сохранить ДДП ДО балансировки, потом отбалансировать, проверить, что все ок и восстановить первоначальный вид ДДП). Не уверен, но вроде в АВЛ проверка при балансировке идет тогда, когда разрыв в этажах становится 2 уровня, в произвольно взятом ДДП разрыв может быть произвольным...
            Цитата FasterHarder @
            можешь пояснить чуть детальней алгоритм, т е куда перемещается выбранный узел?

            Я имел в виду не одиночный узел, а всё поддерево от указанного узла до листьев.
            На место существующей Null-ссылки листа или неполного узла.
            Ну и более сложный вариант - взаимное перемещение (обмен) двух узлов.
            Сюда же можно добавить и копирование ветви в указанное место.

            Цитата FasterHarder @
            можно создать 2 варианта: от корня до узла и от узла до корня

            Не вижу особой применимости второго варианта.

            Цитата FasterHarder @
            имхо, это достаточно сложная операция

            Элементарная. Для обоих узлов строится полный путь, ищется максимальная начальная общая подстрока (или, для варианта пути от узла к корню - конечная), которая конвертируется в полный путь общего узла (возможно, потребуется усечение, если субключи в узле ветвления имеют общую начальную подстроку), после чего определяется собственно узел.
            Сообщение отредактировано: Akina -
              >есть вопрос: минимальный предок, это предок с минимальным ключом, да, или др. признак?
              Нет, это самый ближний узел, являющийся родителем обоих, верхняя точка кратчайшего пути

              >нельзя ДДП делать самобалансирующимся, т к по определению этот вид деревьев не обладает таким свойством
              По какому определению? Самобалансирующиеся деревья - подвиды двоичных деревьев.
              Сообщение отредактировано: MBo -
                Цитата Akina @
                Я имел в виду не одиночный узел, а всё поддерево от указанного узла до листьев.
                На место существующей Null-ссылки листа или неполного узла.
                Ну и более сложный вариант - взаимное перемещение (обмен) двух узлов.
                Сюда же можно добавить и копирование ветви в указанное место.


                Как-нибудь я построю дерево ДДП (прил.картинку) и посмотрим на картинке, т к тут куча нюансов, типа, а всегда ли возможно такое перемещение или, а единственен ли способ такого перемещения и пр.

                Цитата Akina @
                Не вижу особой применимости второго варианта.

                Ну, здесь ведь симметричный взгляд на этот путь! Может потребоваться генеалогическое дерево от суперпредка до текущего "человека" или наоборот, в зависимости от условия задачи! По этой операции все предельно понятно.

                Цитата Akina @
                Элементарная

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

                Цитата MBo @
                По какому определению? Самобалансирующиеся деревья - подвиды двоичных деревьев.

                Ну, например в ВИКИ) Там ведь в определении не говорится о том, что ДДП - самобалансирующиеся + приводится список базовых операций. Но с др. стороны там упоминается балансировка.
                MBo, мне кажется мы с тобой начали спор на пустом месте (спорить даже не хочу, т к проиграю явно), т к я не против балансировки как таковой, но, если посмотреть СТАНДАРТНОЕ ДДП, то его строят не балансируя.
                  Цитата FasterHarder @
                  Там ведь в определении не говорится о том, что ДДП - самобалансирующиеся + приводится список базовых операций.
                  Это не означает, что ты не можешь добавлять свои операции.

                  Вообще, иногда требуется оптимизация ДДП по заданным вероятностям (частотам) появления ключей. Но этот алгоритм используется только для построения оптимального дерева поиска, которое однажды сгенерированное уже не меняется. Обычно такое дерево в готовом виде вписывается в программу.
                  Оптимальное дерево, как правило не является сбалансированным.
                  Сообщение отредактировано: amk -
                    Вопрос!
                    Если ДДП уже построен, причем разрыв в уровнях будет равен 10, то его МОЖНО отбалансировать или уже НЕТ? Разумеется, речь идет о балансировке на внутренней памяти, т е используя только повороты. Где читал про АВЛ, например, то там балансировка сразу происходит, когда разница в уровнях становится 2.

                    amk, так напиши пару новых операций над ДДП, раз уж в теме.
                      Цитата FasterHarder @
                      amk, так напиши пару новых операций над ДДП, раз уж в теме.
                      Да я ДДП давно уже не пользуюсь. Мне хэш-таблиц хватает.
                        Скрытый текст
                        Цитата amk @
                        Да я ДДП давно уже не пользуюсь. Мне хэш-таблиц хватает.

                        Отлично! По хэш-таблицам у меня есть масса вопросов (в др.теме спрошу), особенно по открытой адресации!
                        А создание хорошей хэш-функции для сложных данных - вообще за рамками рациональног! Там ведь столько тончайших настроек и все нужно учесть.
                          Цитата Akina @
                          Ну и более сложный вариант - взаимное перемещение (обмен) двух узлов.

                          Вот построено бинарное дерево поиска (см. прил.файл).
                          Приведи, плиз, пример, как будут перемещаться взаимно узлы + по какому правилу
                          Прикреплённая картинка
                          Прикреплённая картинка
                            Цитата FasterHarder @
                            Приведи, плиз, пример, как будут перемещаться взаимно узлы + по какому правилу

                            Вот конечное состояние.
                            Прикреплённая картинка
                            Прикреплённая картинка
                              Цитата Akina @
                              Вот конечное состояние.

                              так, а как 70 оказалась в ЛЕВОМ поддереве корня 50?
                              Числа, которые больше или равны ключу попадают вправо, а, если меньше, то влево
                                FasterHarder
                                Пардон, я уже успел забыть, что у тебя не просто дерево, а ДДП...
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0516 ]   [ 20 queries used ]   [ Generated: 29.03.24, 04:59 GMT ]