Подходящая структура данных дерева

Question

Я читал о структуре данных дерева, чтобы смоделировать проблему. Мне нужно создать представление памяти данных, которое очень похоже на представление папки/файла в файловой системе (я не подразумеваю, что фактический файл хранится на диске, но структура, подобная исследователю). Дерево может быть не более 10 глубин. В промежуточных узлах может быть только умеренное количество детей (скажем, 10), но могут быть тысячи листовых узлов. [Это похоже на тысячи файлов в папке и файле - листовой узел)

Некоторые мысли

• Двоичное дерево не может работать в качестве одного узла может в лучшем случае имеют лишь 2 детей. (скажем, мы можем иметь 3 подпапки)
• Реализация очень общего дерева может быть неэффективной, поскольку мои данные могут быть заказаны. Как и левый брат, он меньше/меньше правых. Надеюсь, это позволит эффективно обходить друг друга.
• B-tree звучит очень близко, но он настаивает на необходимости балансировки. В моем случае глубина будет не более 10, но не обязательно всей этой ветви (например, c:/windows, C:/MyDoc ../ A/B/C)

Please помогите с вашим опытом. Должен ли я настраивать дерево или любую подходящую структуру данных (не означающую специфику языка программирования)

Answer 1

У вас есть два разных типа узлов: файлы и папки.

Узел папки содержит набор (или карту) детей, где сами дети могут быть файлами или папками.

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

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

Answer 2

Одним из способов сделать это было бы использовать двоичное дерево двоичных деревьев. Например:

Node 
    Node* Children; 
    Node* Left; 
    Note* Right; 

И корень дерева является Node*.

Это обеспечивает легкий обход и быструю установку и удаление узла. Конечно, вы знаете путь к тому уровню, на котором хотите вставить узел, или путь к узлу, который вы хотите удалить. Но поскольку вы указываете, что хотите модель, похожую на Explorer, я предполагаю, что поиск определенного уровня не создает проблемы.

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

Без дополнительной информации о том, что вы пытаетесь моделировать, это лучшее, что я могу сделать.

Answer 3

Используйте две отдельные структуры данных:

1. Двоичное дерево поиска для поиска
2. и общего бинарного дерева для представления

и связать эти два вместе.

Примечание:

• В общем дереве поместить папки первыми в порядке и поместить все файлы в BST, как последний узел.

Или Использование:

Node: 
    Node* Left_Most_Child_Folder; 
    Node* Right_Sibling_Folder; 
    BST_Node* Files_Root; 

Answer 4

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

Например, вы можете реализовать Linux как файловую систему, где папка представляет собой файл, который записывает указатели на другие файлы/папки, которые он содержит. В то же время вы поддерживаете дерево B +, в котором каждый указатель на файл является листом. Состояние баланса дерева B + не имеет никакого отношения к тому, как пользователь организует папки.