powered by simpleCommunicator - 2.0.61     © 2026 Programmizd 02
Целевая тема:
Создать новую тему:
Автор:
Закрыть
Цитировать
Форумы / Java [игнор отключен] [закрыт для гостей] / Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
24 сообщений из 24, страница 1 из 1
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39229552
MAULER
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Есть некое дерево Tree.

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

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

Я изобретаю велосипед или есть другое решение?
...
Рейтинг: 0 / 0
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39229618
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39229657
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Код: 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
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39229808
MAULER
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39229818
Фотография Blazkowicz
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MAULERцелая наука с этими деревьями.
Ну, есть более простые решения.
Отсортировать дерево и искать детей двоичным поиском.
Либо использовать LinkedHashSet для хранения списка детей.

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

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



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

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

Возможно он хочет некий хеш-поиск или некие гарантии быстроты для рандомного 1-го аргумента в addNode
но не знает как его сделать.
...
Рейтинг: 0 / 0
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39229834
Фотография Petro123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MAULERЯ изобретаю велосипед или есть другое решение?
деревья и списки бывают разные.
Чтобы не делать велосипед - бери библиотечное дерево. Там должно быть API с всякими вкусностями.
...
Рейтинг: 0 / 0
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39229837
Фотография Petro123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
mayton,
ему сюда
Задачка для собеседования : ArrayList vs LinkedList (1...23,24,25,26)
только про дерево.
Пока непонятно что он хочет.
...
Рейтинг: 0 / 0
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39229904
MAULER
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39229908
MAULER
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
эх... табуляция пропала, там отступы должны быть, демонстрирующие "дерево"
...
Рейтинг: 0 / 0
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39229913
Фотография Petro123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39229916
Фотография Petro123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MAULERв одном поле которой хранятся листья и ветви одного дерева:
не понял. Дай схему таблы.
...
Рейтинг: 0 / 0
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39229921
Фотография Petro123
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MAULERчитая последовательно записи таблицы
если я правильно понял данный изврат в модели.
То одноразово загрузи своё дерево в оперативку или в другую правильную таблицу и потом всё остальное для работы.
...
Рейтинг: 0 / 0
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39229983
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
MAULERэх... табуляция пропала, там отступы должны быть, демонстрирующие "дерево"
Хабрахабр различает 4 способа хранения деревьев в БД.
+Я бы еще добавил бесконечное число структур данных в ЯП
которые по смыслу есть деревья.
+Файловую систему можно вполне рассматривать как дерево.

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

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

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

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

Обязательно прочту.
...
Рейтинг: 0 / 0
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39230683
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonВозможно он хочет некий хеш-поиск
Имея построенное дерево пытаться сделать хеш поиск мягко говоря странно.
С другой стороны дерево может быть не упорядочено внутри узла.
Там да можно городить все, что угодно. :)
Всего-то переделать так, чтоб наследники хранились не в списке, а в HashMap. :)
...
Рейтинг: 0 / 0
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39230751
Фотография mayton
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
Сергей АрсеньевmaytonВозможно он хочет некий хеш-поиск
Имея построенное дерево пытаться сделать хеш поиск мягко говоря странно.
С другой стороны дерево может быть не упорядочено внутри узла.
Там да можно городить все, что угодно. :)
Всего-то переделать так, чтоб наследники хранились не в списке, а в HashMap. :)
Я где-то читал что файловые системы ext3/ext4 предварительно хешируют
имена в директориях для более быстрого доступа.
...
Рейтинг: 0 / 0
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39230830
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
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
Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
    #39230832
Сергей Арсеньев
Скрыть профиль Поместить в игнор-лист Сообщения автора в теме
Участник
maytonЯ где-то читал что файловые системы ext3/ext4 предварительно хешируют
Так это и есть внутри узла. И они там дерево строят, обычно. Ибо хеш на все случаи жизни плохо подбирается.
...
Рейтинг: 0 / 0
24 сообщений из 24, страница 1 из 1
Форумы / Java [игнор отключен] [закрыт для гостей] / Иерархическое дерево Tree. Есть ли способ создать ветку без предварительного перебора?
Найденые пользователи ...
Разблокировать пользователей ...
Читали форум (0):
Пользователи онлайн (0):
x
x
Закрыть


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