Здравствуйте, _Lestat_, Вы писали:

_L_>Я хоть и computer science окончил, тем не менее мне вот что интересно стало. Имя файла свернули в хэш. Функцию сравнения для дерева сделали сами с сортировкой сначала по имени файла, а потом строке. (Дерево кстати сбалансированное, оно это потом балансировать будет). С точки зрения работы алгоритмов совершенно пофигу какое у нас условие сортировки и какие данные мы сортируем и с каким условием? Пусть даже у нас там будет десять условий в функции сортировки? Все равно ведь искать мы будем потом согласно тому же алгоритму?

Ну, во-первых, там не хэш, а регистрационный номер имени файла.
Если тебе важно, чтобы эти номера шли в определённом порядке, — собери все имена файлов, отсортируй и скорми реестру имён.

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

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

Для двоичного дерева поиска, разумеется, нам всё равно, какое условие сортировки. Лишь бы оно удовлетворяло аксиоматике строгого порядка, то есть обладало свойствами транзитивности (x<y<z => x<z), антикоммутативности (x<y <=> y>x) и (анти)рефлексивности (x=x).
Но из всего бесконечного многообразия таких условий проще всего взять лексикографическое: сравнение первых элементов (номеров файлов), затем в случае равенства сравнение вторых элементов (номеров строк).
Кроме всего прочего, это и для тебя удобно: регионы одного файла оказываются сгруппированными вместе и упорядоченными по номерам строк.

Естественно, что у существующего экземпляра дерева условие жёстко зафиксировано. И, как следствие, порядок обхода тоже заранее известен. Это инвариант дерева. Чтобы поменять условие сортировки, нужно заодно перестроить всё дерево. Так проще сделать новое дерево с новым условием и перетащить старые данные туда.


Если тебе, помимо поиска по ключу (файл,строка) хочется искать ещё как-то — то здесь есть 3 варианта
0. осознать тщетность этого хотения и отказаться
1. завести параллельно ещё один контейнер, в котором те же самые элементы упорядочены иным, нужным тебе способом (естественно, что эти вторичные ключи не могут изменяться! либо, при изменении ключа нужно сперва удалить элемент из контейнера, а затем изменить ключ и вставить элемент обратно)
2. линейный обход с проверкой условия