Гость
Целевая тема:
Создать новую тему:
Автор:
Форумы / Java [игнор отключен] [закрыт для гостей] / Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора? / 24 сообщений из 24, страница 1 из 1
05.05.2016, 07:01
    #39229552
MAULER
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
Есть некое дерево Tree.

Каким образом можно создать (к примеру) ветвь root\Companies\Oracle\Java без перебора item-ов этого дерева? При условии что, структура root\Companies уже существует?

Или мне придется встать на root , затем итератором пройтись сверху вниз, проверить не равен ли текущий элемент "Companies", и если равен, то создать item "Oracle", а затем item "Java" ?

Я изобретаю велосипед или есть другое решение?
...
Рейтинг: 0 / 0
05.05.2016, 10:04
    #39229618
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
MAULER,

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

Во-вторых существует масса способов представления дерева.
Например:
https://en.wikipedia.org/wiki/Trie
https://en.wikipedia.org/wiki/Y-fast_trie
https://en.wikipedia.org/wiki/Heap_(data_structure)
и прочие.

Разные способы оптимизированы под разные операции. Если поиск и вставка являются у вас узким местом, то стоит искать соответственно структуру оптимизированную под эту задачу.
...
Рейтинг: 0 / 0
05.05.2016, 10:34
    #39229657
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
Код: java
1.
2.
3.
4.
5.
6.
7.
public interface MAULERAppendableTree<T>{
      // Classic Tree Interface
      .....
      
      // Advanced Mauler-s interface methods
      void appendNodeToLastActivePosition(T node);
}
...
Рейтинг: 0 / 0
05.05.2016, 12:57
    #39229808
MAULER
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
BlazkowiczMAULER,

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

Во-вторых существует масса способов представления дерева.
Например:
https://en.wikipedia.org/wiki/Trie
https://en.wikipedia.org/wiki/Y-fast_trie
https://en.wikipedia.org/wiki/Heap_(data_structure)
и прочие.

Разные способы оптимизированы под разные операции. Если поиск и вставка являются у вас узким местом, то стоит искать соответственно структуру оптимизированную под эту задачу.

целая наука с этими деревьями.
...
Рейтинг: 0 / 0
05.05.2016, 13:01
    #39229818
Blazkowicz
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
MAULERцелая наука с этими деревьями.
Ну, есть более простые решения.
Отсортировать дерево и искать детей двоичным поиском.
Либо использовать LinkedHashSet для хранения списка детей.

Но сложно что-то конкретное советовать, не понимая зачем оно вообще понадобилось.
...
Рейтинг: 0 / 0
05.05.2016, 13:14
    #39229831
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
Я себе так понимаю его вопрос. Он хочет сделать

Код: java
1.
addNode("root\Companies", "Oracle\Java");



при этом гарантировать что для поиска узла Companies не надо будет бегать линейным поиском.

Вопрос странный. Можно получить 1 раз узел Companies (любым способом) и спокойно дальше себе
толкать листья в ветки в него.

Возможно он хочет некий хеш-поиск или некие гарантии быстроты для рандомного 1-го аргумента в addNode
но не знает как его сделать.
...
Рейтинг: 0 / 0
05.05.2016, 13:15
    #39229834
Petro123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
MAULERЯ изобретаю велосипед или есть другое решение?
деревья и списки бывают разные.
Чтобы не делать велосипед - бери библиотечное дерево. Там должно быть API с всякими вкусностями.
...
Рейтинг: 0 / 0
05.05.2016, 13:18
    #39229837
Petro123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
mayton,
ему сюда
Задачка для собеседования : ArrayList vs LinkedList (1...23,24,25,26)
только про дерево.
Пока непонятно что он хочет.
...
Рейтинг: 0 / 0
05.05.2016, 14:18
    #39229904
MAULER
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
Petro123,

Задачка простая для понимания и сложновато (для меня) реализуема.
Есть таблица в одном поле которой хранятся листья и ветви одного дерева:

root\Companies\Oracle\Java
root\Companies\Oracle\Primavera
root\Companies\Microsoft
root\Companies\Microsoft\Windows
root\Companies\Borland
root\Companies\Borland\Pascal
...

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

root
Companies
Oracle
Java


После прочтения второй записи:

root
Companies
Oracle
Java
Primavera


и т.д.

причем, в результате "парсинга" записи надо "пропускать" уже созданные пункты дерева, и создавать новые.

Надеюсь понятно объяснил.
...
Рейтинг: 0 / 0
05.05.2016, 14:20
    #39229908
MAULER
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
эх... табуляция пропала, там отступы должны быть, демонстрирующие "дерево"
...
Рейтинг: 0 / 0
05.05.2016, 14:26
    #39229913
Petro123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
MAULERЕсть таблица
)) а раньше нельзя было сказать?
MAULERнадо построить дерево читая последовательно записи таблицы.
Код: java
1.
2.
3.
4.
SELECT 
FROM tree t
START WITH t.parent_id is null
CONNECT BY PRIOR id = t.parent_id;


API субд для деревьев рассматриваем?
...
Рейтинг: 0 / 0
05.05.2016, 14:29
    #39229916
Petro123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
MAULERв одном поле которой хранятся листья и ветви одного дерева:
не понял. Дай схему таблы.
...
Рейтинг: 0 / 0
05.05.2016, 14:32
    #39229921
Petro123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
MAULERчитая последовательно записи таблицы
если я правильно понял данный изврат в модели.
То одноразово загрузи своё дерево в оперативку или в другую правильную таблицу и потом всё остальное для работы.
...
Рейтинг: 0 / 0
05.05.2016, 15:22
    #39229983
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
MAULERэх... табуляция пропала, там отступы должны быть, демонстрирующие "дерево"
Хабрахабр различает 4 способа хранения деревьев в БД.
+Я бы еще добавил бесконечное число структур данных в ЯП
которые по смыслу есть деревья.
+Файловую систему можно вполне рассматривать как дерево.

А с твоих слов совершенно (!) непонятно на чем основана у тебя
модель хранения. Я говорю хранения потому-что представленеи
мы уже как-бе обсудили.
...
Рейтинг: 0 / 0
05.05.2016, 15:32
    #39230007
Petro123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
maytonнепонятно на чем основана у тебя
модель хранения.
на слешах и одинаковости строк между ними))
Почти FAT32
...
Рейтинг: 0 / 0
05.05.2016, 18:36
    #39230264
MAULER
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
Petro123,

На самом деле, хранить дерево в таком виде поидумал я.
Что то более-менее путное пока в голову не приходит.
По факту у меня на gwt фреймворке написан мини-редактор, который умеет городить деревья
Произвольной вложенности. И такое вот дерево из памяти надо както перенести в таблицу базы. Пихать xml в таблицу - не вариант, т.к есть перспектива поиска ...

Вот пока придумал хранить так ну и читать также.
...
Рейтинг: 0 / 0
05.05.2016, 18:47
    #39230277
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
MAULERНа самом деле, хранить дерево в таком виде поидумал я.
Ты придумал Materialized Path ?
...
Рейтинг: 0 / 0
05.05.2016, 18:53
    #39230282
MAULER
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
maytonMAULERНа самом деле, хранить дерево в таком виде поидумал я.
Ты придумал Materialized Path ?

На момент придумывания я этого не знал
...
Рейтинг: 0 / 0
05.05.2016, 19:01
    #39230288
Petro123
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
MAULERНа момент придумывания я этого не знал
и не узнаешь никогда. Так как ты не читал что тут все тебе написали....как хранят деревья.
Удачи!
...
Рейтинг: 0 / 0
05.05.2016, 19:08
    #39230291
MAULER
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
Petro123,

Обязательно прочту.
...
Рейтинг: 0 / 0
06.05.2016, 11:36
    #39230683
Сергей Арсеньев
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
maytonВозможно он хочет некий хеш-поиск
Имея построенное дерево пытаться сделать хеш поиск мягко говоря странно.
С другой стороны дерево может быть не упорядочено внутри узла.
Там да можно городить все, что угодно. :)
Всего-то переделать так, чтоб наследники хранились не в списке, а в HashMap. :)
...
Рейтинг: 0 / 0
06.05.2016, 12:26
    #39230751
mayton
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
Сергей АрсеньевmaytonВозможно он хочет некий хеш-поиск
Имея построенное дерево пытаться сделать хеш поиск мягко говоря странно.
С другой стороны дерево может быть не упорядочено внутри узла.
Там да можно городить все, что угодно. :)
Всего-то переделать так, чтоб наследники хранились не в списке, а в HashMap. :)
Я где-то читал что файловые системы ext3/ext4 предварительно хешируют
имена в директориях для более быстрого доступа.
...
Рейтинг: 0 / 0
06.05.2016, 13:32
    #39230830
Сергей Арсеньев
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
MAULERпричем, в результате "парсинга" записи надо "пропускать" уже созданные пункты дерева, и создавать новые.
Так это почти любое дерево умеет. Даже такое.
Код: java
1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
public class HashTreeElement (
  public class HashTreeElement {

 public final HashMap<String,HashTreeElement> children = new HashMap<String,HashTreeElement>();
 public final String key;

 public HashTreeElement(final String path) {
  int i = path.indexOf("\\");
  key = (i<0)?path:((i==0)?"":path.substring(0,i));
  if ((i>=0)&((i+1)<path.length())) {
   HashTreeElement child = new HashTreeElement(path.substring(i+1));
   children.put(child.key,child);
  }
 }

 public void add(final String path) {
  int i = path.indexOf("\\");
  String newKey = null;
  String childPath= null;
  if (i<0) {
   newKey=path;
  } else {
   newKey    = (i==0)?"":path.substring(0,i);
   childPath = path.substring(i+1);
   i = childPath.indexOf("\\");
   String childKey = (i<0)?childPath:((i==0)?"":childPath.substring(0,i));
   HashTreeElement child = this.children.get(childKey);
   if (child==null) {
    this.children.put(childKey,new HashTreeElement(childPath));
   } else {
    if (childPath.length()>(i+1)) {
     child.add(childPath);
    } 
   }
  }

//  if (!key.equals(newKey)) throw new Exception("new Tree root!");
 }
  
 public String toString(final int lvl) {
    StringBuffer res2 =new StringBuffer("\n");
    for (int i=0;i<=lvl;i++) {
     res2.append("...->");
    }
    StringBuffer res =new StringBuffer(key);
    boolean suff= true;
    for (HashTreeElement t:children.values()) {
      res.append(suff?"->":res2.toString()).append(t.toString(lvl+1));
      suff=false;
    }
    return res.toString();
 }

 public static void main(String[] args) {
  HashTreeElement root = null;
  for (String s : args) {
   if (root==null) {
    root = new HashTreeElement(s);
   } else {
    root.add(s);
   }
  }
  System.out.println(root.toString(0));
 }
}
)
...
Рейтинг: 0 / 0
06.05.2016, 13:34
    #39230832
Сергей Арсеньев
Участник
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
maytonЯ где-то читал что файловые системы ext3/ext4 предварительно хешируют
Так это и есть внутри узла. И они там дерево строят, обычно. Ибо хеш на все случаи жизни плохо подбирается.
...
Рейтинг: 0 / 0
Форумы / Java [игнор отключен] [закрыт для гостей] / Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора? / 24 сообщений из 24, страница 1 из 1
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


Просмотр
0 / 0
Close
Debug Console [Select Text]