Блог пользователя wackloner

Автор wackloner, 11 лет назад, По-русски

Всем привет. Совсем недавно я, наконец, познакомился с такой замечательной структурой, как дерамида. В теории я понял ее практически отлично. Но вот когда дело дошло до реализации, я понял, что не все так хорошо. Долгое время я думал, что знаю все нужные аспекты Java для ОП, но, как оказалось, не все.

Вот то, что я смог написать сам — http://pastie.org/5084738 Это, вроде, самая "нубская" реализация Декартова Дерева. В теории я знаю о том, как можно избавится от приоритетов, о переходе от явного ключу к неявному, но я хочу пройти через все этапы усовершенствований, дабы понимать, что к чему.

Так, много слов, а сути нет. На данном этапе я хочу модифицировать функции add() и remove(), чтобы они использовали по одной операции split()/**merge()**, а не по три. Ясно, как это делается:

Add(x) — спускаемся по дереву поиска, пока не найдем вершину с приоритетом меньшим, чем у добавляемый вершины, посплитим ее по x, и поставим получившиеся l и r как l и r добавляемой вершины, ее же поставим на место найденной

Remove(x) — спускаемся по дереву, находим искомую вершину, мерджим ее l и r, ставим результат на место этой вершины, вуаля

На примере remove() покажу, в чем, собственно, моя проблема. Вот как, по сути, она должна выглядеть:

void remove(int x) {
	Node t = root;
	while (t.x != x)
		t = x < t.x ? t.l : t.r;
	t = merge(t.l, t.r);
}

Но это не работает в силу того, что в данном случае t — лишь одна из ссылок на вершину дерева и, меняя ее, я не меняю само дерево, я лишь меняю эту ссылку. И вот, я не знаю, как правильно это реализовать. То же самое с add().

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

  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Вот мой быдлокод девятимесячной давности (я написал все это в качестве решения задачи НОД 2010 с Тимуса).

P.S. Если нужна более приличная реализация — могу скинуть. Правда, когда я писал дерамиду прилично, я писал ее по неявному ключу и при этом персистентную.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Спасибо за код, теперь стало ясно, как это получше сделать. Странно, что не додумался сам)

    А по неявному ключу — конечно, скинь, я сейчас как раз к этому перейду, так что будет интересно посмотреть на уже рабочий вариант.

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Как раз там еще неявные приоритеты. Вот код.

      • »
        »
        »
        »
        11 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        А как лучше передавать пары деревьев? Объектом или массивом? Или тут как кому удобнее?

        • »
          »
          »
          »
          »
          11 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          Без разницы, т.к. это явно не узкое место.

          • »
            »
            »
            »
            »
            »
            11 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Я сам не тестил, но, по-моему, не очевидно, что НЕ узкое.

            Создание объектов в Java — это таки overhead.

            И если у меня будет ~4logN обращений к памяти, if-ов и рекурсивных вызовов — это одно, а если столько же созданий объектов — другое.

            Разве нет?

            • »
              »
              »
              »
              »
              »
              »
              11 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Но я же писал про создание объекта для возвращения результата из сплита, а он создается только один раз.

              Если же говорить про персистентную дерамиду, где действительно при каждом запросе создается O(log N) новых объектов — здесь уже никуда не денешься. Выделение объектов заранее не даст никакой выгоды; можно, конечно, написать все на массивах, но смысла в этом я особо не вижу — лучше уж сразу писать на сишке.

              • »
                »
                »
                »
                »
                »
                »
                »
                11 лет назад, # ^ |
                  Проголосовать: нравится 0 Проголосовать: не нравится

                Казалось бы, новый объект создаётся каждый раз при выходе из split, а split вызывается O(глубина дерева) раз.

  • »
    »
    11 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    Маленькое замечание: не пишите так сплит, что на каждом его вызове создаётся новый объект, достаточно создать один на самом нижнем шаге рекурсии, а дальше его изменять. Иначе вы НОД 2010 на Джаве точно не сдадите :)

    Вот так заходит за 0.343: http://pastie.org/5084951

    • »
      »
      »
      11 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Вы не поверите, но именно тот код, который я скинул, зашел на Тимусе за 0.375с :).

      Да, и я уже сказал, что это мой старый быдлокод, сейчас я пишу все по-нормальному, код я выложил выше.

      • »
        »
        »
        »
        11 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        Да, я сам тестанул, и так заходит, странно, я когда-то сказочно пихал :(

        UPD А, я понял что пихал. Я в мердже ещё новую вершину создавал, как на хабре. Так точно делать не стоит.

»
11 лет назад, # |
Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

Попробуйте нечто такое:

public void remove(int x){
	rootNode = remove(x,rootNode);
}

private Node remove(int x, Node node){
	if (node.x == x){
		return merge(node.l, node.r); // Если node - удаляемая вершина, то она "схлопнется" и вместо себя наверх возвратит дерамиду, образованную из ее дочерних ветвей.
	}
	
	if (x < node.x){
		node.l = remove(x,node.l); //Удаляем ключ из левого поддерева, и если дочерняя вершина окажется удаляемой, то данным присвоением она будет заменена
	}else{
		node.r = remove(x,node.r); // --||--
	}
	return node; // а это для всех остальных ключей, что бы не разрушить нашу исходную дерамиду.
}

UPD: Упс.. Оказывается уже ответили. Был на англ. версии сайта — не видел русские коментарии)