Низкие ветвистые деревья

    Под сим поэтическим названием скрывается идея удобного представления древовидных структур данных и практической его реализации. Может, что-то подобное где-то уже было, но я не встречал; и тут мой приятель Эдуард Аверюшкин предложил интересную идею, которую я попытался развить.


    Классическое представление дерева сущностей (например, меню разделов сайта, главное меню в программах) довольно удобно и наглядно в случае «высокого» дерева с не слишком глубокой вложенностью элементов. Будь то выпадающее меню (как главное строковое меню программ) или раскрывающееся (как в левой панели популярных файловых менеджеров), всё довольно удобно и наглядно. А что если дерево низкое и развесистое? У каждого родителя детей мало, зато вложенность достигает, скажем, 10. Или 50…


    Низкие ветвистые деревья



    Тогда в случае раскрывающегося меню мы получаем огромные отступы по горизонтали. В случае выпадающего… Рай для мазохиста.


    Давайте представим это в виде лестницы в довольно узком помещении. В случае «высоких деревьев» у нас получаются очень узкие, но высокие ступени, и тогда всё довольно неплохо. В случае же «низких деревьев» мы просто упрёмся в стену на всё ещё большой высоте.


    Итак, вывод очевиден. Спиральная реализация. Но как это перенести на плоскость? Минус одно измерение. Здесь нам придётся пожертвовать одновременным раскрытием нескольких ветвей. Может (да и наверняка), существует лучшее решение, но я не математик, а то, о чём я пишу, хоть как-то решает задачу — тоннель.


    Пример реализации


    Реализовать захотелось на более-менее практическом примере. Возьмём некую базу данных по ресторанам с определённым общим набором признаков (тэгов), организованных в дерево.


    Например, такое
    • Дороговизна
      • Дешёвый
      • Средний
      • Дорогой

    • Курение
      • Для некурящих
      • Смешанный
        • Один курящий зал
        • Раздельные залы

      • Для курящих

    • Звук
      • Музыка
        • Живая музыка
        • Музыка в записях

      • Громко
      • Тихо

    • Можно с детьми


    Дерево для иллюстрации данной статьи не слишком удачное из-за малой вложенности элементов, но для примера сойдёт; это не существенно, как будет видно дальше — можно сделать какую угодно глубину без особого ущерба для удобства навигации по дереву.


    Допустим, у нас есть задача спроектировать систему поиска ресторанов по этом тэгам. Например, среднестатистическая богатая семья деревни Подвыхухолевка решила на выходных пойти в ресторан, коих в деревне насчитывается 351 штука. Семья привередливая, каждый член её с характером, но после долгих обсуждений со скандалами они решили, что хотят в дорогой ресторан, с раздельными залами для курящих и некурящих, с громкой живой музыкой и в полном составе — мама, папа и пять детей от разных браков. Простите. Понесло.


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


    Дерево тэгов


    Рассмотрим чуть подробнее сами тэги. У каждого есть (помимо очевидных родителя, братьев, детей и пр. id) два важных признака:


    1. virtual — означает, что этот тэг является лишь контейнером (папкой) и в поиске не участвует (нельзя добавить в фильтр);
    2. replaces — перечень других тэгов, которые данный тэг заменяет; к примеру, тэги «Для курящих» и «Можно с детьми» несколько малосовместимы; тогда при добавлении в фильтр данного тэга, из фильтра выпадают те, которые он “replaces”.

    Вот XML-пример нашего дерева
    <?xml version="1.0" ?>
    <tags>
        <tag id="1" name="Дороговизна" virtual="1">
            <tag id="11" name="Дешёвый" replaces="12 13" />
            <tag id="12" name="Средний" replaces="11 13" />
            <tag id="13" name="Дорогой" replaces="11 12" />
        </tag>
        <tag id="2" name="Курение" virtual="1">
            <tag id="21" name="Для некурящих" replaces="221 222 23" />
            <tag id="22" name="Смешанный" virtual="1">
                <tag id="221" name="Один курящий зал" replaces="21 23 222 4" />
                <tag id="222" name="Раздельные залы" replaces="21 23 221" />
            </tag>
            <tag id="23" name="Для курящих" replaces="21 221 222 4" />
        </tag>
        <tag id="3" name="Звук" virtual="1">
            <tag id="31" name="Музыка" replaces="311 312">
                <tag id="311" name="Живая музыка" replaces="31" />
                <tag id="312" name="Музыка в записях" replaces="31" />
            </tag>
            <tag id="32" name="Громко" />
            <tag id="33" name="Тихо" />
        </tag>
        <tag id="4" name="Можно с детьми" replaces="23 221" />
    </tags>
    


    Ну и XML-ка ресторанов
    <?xml version="1.0" ?>
    <items>
        <item id="1" name="Первый ресторан" tags="13 221 311 312 32 33 4" />
        <item id="2" name="Второй ресторан" tags="11 23 32 33" />
        <item id="3" name="Третий ресторан" tags="12 21 311 32 4" />
    </items>
    


    Опять же, реализация демонстрационная. Можно JSON-ом, можно хоть голосовой записью с системой распознавания речи.


    Клиентская часть — тоннель


    Далее, каждый житель деревни может зайти со своего айпада (вся Подвыхухолевка накрыта высокоскоростной Wi-Fi-сетью) на специальный сайт, на котором увидит что-то похожее на это (по ссылке живой пример; прошу прощения за некоторую сырость воплощения — это демонстрационный прототип, который ещё в разработке; SVG + JS + CSS):


    Поиск по ресторанамКликабельно, ссылка на живой пример


    • Для того, чтобы добавить в поисковой фильтр тэг, надо перетащить его в центр.
    • При перетаскивании в центр «виртуального» тэга просто открываются его дети; невиртуального — и открываются его дети (если есть), и сам он добавляется в фильтр.
    • При простом клике (тапе) на тэге открываются его дети (если есть).
    • При перетаскивании тэга «вовне» закрываются его дети.
    • Выбранные тэги в центре можно удалить оттуда, перетащив их вовне.

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


    Таким образом достигается цель — при дереве, в котором немного братьев одного уровня (в окружность много не влезет), мы имеем практически неограниченные возможности представления очень развесистого, глубокого дерева без потери наглядности.


    Буду рад комментариям, предложениям и критике.

    Поделиться публикацией
    AdBlock похитил этот баннер, но баннеры не зубы — отрастут

    Подробнее
    Реклама
    Комментарии 20
    • +5
      Бррр. Такое ощущение что вы придумали какую-то свою терминологию, которая постоянно сбивает с толку. Интуитивно кажется что низкое ветвистое дерево — это дерево с малой глубиной вложенности, зато с большим количеством веток. То же самое меню сайта. Много веток (поддеревьев) — поэтому ветвистое. Небольшая глубина вложенности — поэтому дерево низкое.

      Высокое дерево — это наоборот дерево с большой вложенностью (википедия тут со мной согласна:
      Height of node — The height of a node is the number of edges on the longest path between that node and a leaf.
      Height of tree — The height of a tree is the height of its root node.)

      А вы поменяли эти два термина местами, из-за чего читать статью очень тяжело.
      • 0
        М… Может, вы и правы. Вообще, аналогия с высотой тут как-то неочевидна. Я имел в виду под ветвистостью именно разделение на разные ветви, а не их количество. Но скорее соглашусь с вами.
      • 0
        Если мы все равно жертвуем показом нескольких ветвей — может лучше переключать списками?

        Клик по элементу списка -> переместились во внутренний список, поменяли заголовок.

        • 0
          Может, я неправильно понял… Вы имеете в виду обычное представление? Построчное, как в файл-менеджере? Если да, то я же написал, в чём по моему мнению проблема. Не в высоте самого списка, а в ширине. Либо, если подразделы выделять не отступами, а ещё как-то, то всё равно вся наследственность выглядит не наглядно. Представьте себе глубину вложенности эдак в 20 уровней.
          • +1
            Да, я имел ввиду без отступов. Просто поклацал демку — она кажется без инструкции неочевидной.

            Как с такими секторами решить проблему, когда секторов штук 10-15?
            • 0
              Случайно ответил в основную ветку. 10-15 ещё не беда. Можно заменить текст пиктограммами. А вот уже этак с 20-30 — читайте статью внимательнее: «Таким образом достигается цель — при дереве, в котором немного братьев одного уровня (в окружность много не влезет), мы имеем практически неограниченные возможности представления очень развесистого, глубокого дерева без потери наглядности.»
              • 0
                Никто не мешает при раскрытии дочернего уровня сдвигать его заголовок на уровень родительского (коль уж он больше не нужен). Получается примерно тот же тоннель, только вдоль стеночки.
                • 0
                  Не совсем. Кто сказал, что родительский больше не нужен? К примеру, человек может выбрать «живую музыку», а потом решить, что ему, в общем, всё равно, какая именно — живая или нет, и выбрать просто музыку. Кроме того. С этим тоннелем, имхо, нагляднее представлены также все братья родительского элемента. А списком получится просто простыня (прошу прощения за тавтологию :)
                  • 0
                    А. Или вы имеете в виду что-то столбцов, обозначающих уровень вложенности, в каждом из которых вертикально расположены братья на этом уровне? И с перемоткой по горизонтали? Если так — тоже вариант. Почему нет? Просто мне показалось так интереснее.
          • 0
            10-15 ещё не беда. Можно заменить текст пиктограммами. А вот уже этак с 20-30 — читайте статью внимательнее: «Таким образом достигается цель — при дереве, в котором немного братьев одного уровня (в окружность много не влезет), мы имеем практически неограниченные возможности представления очень развесистого, глубокого дерева без потери наглядности.»
            • 0
              А может стоит сделать по-порядку выбор, а не все «контейнеры (папки)» показывать сразу? И начать со взаимоисключающих?
              Я о тех, что кардинально меняют дальнейшую выборку.
              (Курение) и (Дети) => Если выбрать Курение — то сразу отпадают все что с детьми…
              В классической версии это Ваш секс?: «мужчина» или «женщина»?

              Например в данной выдаче «дороговизна» без реальных цифр бессмысленна.
              А для курящих, для некурящих, смешанный — можно упростить до [checkbox] «У нас не курят». Тут какая — та не состыковка (путаница). «Смешанный» — один курящий зал — это о том, что одно помещение из 5 в котором курят или все вместе сидят и курильщики и не курильщики?))

              Ну это я про интерфейс. И как я понял это не меню, а фильтр.

              Напишите о своей задаче Лебедеву или Горбунову) они вам быстро накидают правильный интерфейс.
              • 0
                Курение) и (Дети) => Если выбрать Курение — то сразу отпадают все что с детьми…
                А если человек передумает? Потом к «детям» будет сложно вернуться. Сначала убрать «курение» и т.д.
                Например в данной выдаче «дороговизна» без реальных цифр бессмысленна. А для курящих, для некурящих, смешанный — можно упростить до [checkbox] «У нас не курят». Тут какая — та не состыковка (путаница). «Смешанный» — один курящий зал — это о том, что одно помещение из 5 в котором курят или все вместе сидят и курильщики и не курильщики?))
                Это просто пример для иллюстрации самого принципа визуального представления древовидной структуры — дерева, у которого мало братьев одного уровня и глубокая вложенность. Рестораны — только пример! :)
                И как я понял это не меню, а фильтр.
                Опять же. Это — и то, и другое. Просто визуальное представление дерева на примере фильтра.
                • 0
                  Очень сложное представление. Если это для интерфейса — то не применимо.

                  Я понимаю, что это просто пример.
                  В данном случае как раз и нужно отталкиваться от реального мира и потребностей с конкретными фактами/данными, чтобы можно было понять пользу и простоту представления информации в таком графическом виде.
                  Помещаем данные в такой интерфейс и потом пытаемся понять, удобно ли? Есть ли согласованность? Да и просто провести тесты по времени, как быстро человек взаимодействует с каждым из них. Сравниваем классическое представление и «новое». В классическом виде это все подается в группировках, по приоритетам людей (по спросу) — GroupBox, радиокнопки и чекбоксы.

                  В итоге, если это для человека — то сложно. Если для программиста — то ему подавайте пожалуйста xml, json, древо.

                  Пожалуйста, докажите, что это удобный инструмент визуализации древовидных данных с глубокой вложенностью. Понимаете, хранение данных удобное для программиста редко когда бывает удобно так же для конечного пользователя, смотрящего в интерфейс, построенный на основе этих данных и вложенности. Как раз таки если строить базу от потребностей человека (потребителей) — то можно сразу оптимизировать ее производительность, не перегружая излишней вложенностью и связями).
                  • 0
                    Что ж я вечно промахиваюсь и отвечаю в корень ветки… :) Дублирую сюда:
                    Сравниваем классическое представление и «новое». В классическом виде это все подается в группировках, по приоритетам людей (по спросу) — GroupBox, радиокнопки и чекбоксы.
                    Понимаете, идея была именно в представлении меню, а не поиска-фильтра-сервиса. То, что я сверху накрутил фильтр, наверно, и вводит в заблуждение. Наверно, зря объединил в статье две разные вещи — идею представления меню с большой вложенностью, но с немногими братьями и этот фильтр. Для идеи представления именно меню чекбоксы и радиокнопки как-то ни к чему.
                    Понимаете, хранение данных удобное для программиста редко когда бывает удобно так же для конечного пользователя
                    Тут-то как раз удобство программиста ни при чём. Я и XML отлично читаю. Но в принципе, с тем, что сам пример не слишком удачен, согласен. Я и в статье написал «Дерево для иллюстрации данной статьи не слишком удачное». Подберу дополнительно ещё один пример понагляднее. Благо достаточно просто подсунуть другой XML-файл.
                    • 0
                      Как вариант — можно подгрузку нескольких вариантов сделать (несколько примеров).

                      Уж очень хочется понять все таки) на живом примере. Спасибо за проделанную работу
                      • 0
                        И можно пожалуйста кратко еще раз, для чего это все делается? Вложенность 10-50?
                        Просто в примере вложенность 3-5. Кому это нужно, что это даст человеку. Грубо говоря в каких задачах требуется такой функционал.
                        • 0
                          Да, в примере было лень выдумывать длинную «рыбу». Всё это делалось не под конкретный проект. Просто довольно часто встречаются такие меню. Как я уже писал в статье, я веб-разработчик. Вы бы видели, какие карты сайта порой предоставляют заказчики. Понятно, что конкретно эта реализация для сайтов не слишком-то подходит. Скорее, это всё — просто результат отвлечённых размышлений о том, как можно визуализировать удобнее подобные деревья. Сейчас с ходу пример не нарою, но для второго примера постараюсь подобрать вполне конкретный вариант.
                          • 0
                            Я просто сам SEO-специалист + webmaster и Python-ист, поэтому и не понимаю, как это может быть применимо к сайтам.
                            В работе, иногда, строю по сео графы. И если небольшой граф — то визуализирую, а если большой — то считаю нужные для меня параметры).
                            Но я понять вообще не могу где может быть в сайтах вложенность больше 7-10…
                            И с картой сайта играюсь и с логами сервера. Но проблем с пониманием как то не было)) А тут подвис, и пытаюсь понять для чего ваша идея…
                            И давайте определим, КАРТА САЙТА — xml или html представление?))
                            • 0
                              Но я понять вообще не могу где может быть в сайтах вложенность больше 7-10…
                              К сожалению, бывает. Правда, обычно удаётся клиента образумить. Но, опять же, я написал, что сайты просто натолкнули на мысль. К сайтам это малоприменимо.
                              И давайте определим, КАРТА САЙТА — xml или html представление?))
                              Вне зависимости от представления. Структура разделов. Основная. Естественно, бывают ещё разные небольшие менюхи.
                • 0
                  Сравниваем классическое представление и «новое». В классическом виде это все подается в группировках, по приоритетам людей (по спросу) — GroupBox, радиокнопки и чекбоксы.
                  Понимаете, идея была именно в представлении меню, а не поиска-фильтра-сервиса. То, что я сверху накрутил фильтр, наверно, и вводит в заблуждение. Наверно, зря объединил в статье две разные вещи — идею представления меню с большой вложенностью, но с немногими братьями и этот фильтр. Для идеи представления именно меню чекбоксы и радиокнопки как-то ни к чему.
                  Понимаете, хранение данных удобное для программиста редко когда бывает удобно так же для конечного пользователя
                  Тут-то как раз удобство программиста ни при чём. Я и XML отлично читаю. Но в принципе, с тем, что сам пример не слишком удачен, согласен. Я и в статье написал «Дерево для иллюстрации данной статьи не слишком удачное». Подберу дополнительно ещё один пример понагляднее. Благо достаточно просто подсунуть другой XML-файл.

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.