Бинарные деревья (деревья поиска)

← →
Николай1984 (2006-10-30 08:48) [0]

Задача о поиске текста.
Дан текст. Построить из слов бинарное дерево поиска по следующему принципу:"Чем чаще встречается слово в тексте тем ближе должно к корню должно храниться это слово, чем реже тем ближе к листьям". При добавлении слова нужно, чтобы с учетом частоты его появления менялось дерево (слово переводилось ближе к корню).

Вопрос в следующем, что делать со словами у которых частота появления одинакова? и какое слово взять за корень дерева? Мне непонятно. Подскажите, кто что может, Буду очень благодарен.
Зарание спасибо.

← →
KilkennyCat © (2006-10-30 09:03) [1]

> что делать со словами у которых частота появления одинакова?

Исппользовать еще одно правило. Например, алфавитный порядок.

> и какое слово взять за корень дерева?

любое. потом поменять.

← →
MBo © (2006-10-30 09:44) [2]

можно использовать простые бинарные деревья (BST), красно-черные (RB)или AVL. Автоматическую подстройку обеспечивают т.н. скошенные деревья (splay tree)

← →
Alex Konshin © (2006-10-30 11:56) [3]

Это задача из лабораторной или из реальной жизни? Потому как для реальной жизни она абсолютно бессмыслена. Постановка задачи некорректна.

Если это дерево поиска слова, то оно должно быть упорядочено по самим словам, а не по частоте его встречи в тексте. То есть, ключ поиска - слово, а не частота. И не надо пытаться путать мух с котлетами. Принцип поиска в бинарном дереве - сравнил ключ и пошел или влево, или вправо. Пытаться трансформировать дерево с учетом частоты - неблагодарное занятие, оно просто неокупится, более того, оно скорее всего замедлит поиск на порядки, потому что дерево будет сильно несбалансировано. Я уж не говорю о сложности реализации самой идеи в принципе.

Если требуется ускорить поиск, то копать нужно не в эту сторону.
Предлагаю сделать ключ двойным. Первое поле - CRC32 (или любая другая хорошая хешфункция). Второе поле - само слово. Когда нужно найти (или добавить) слово, то сначала вычисляем хеш от этого слова. При сравнении ключей сначала сравниваются хеши, и только если они равны, то сравниваются и сами слова. Таким образом мы в большинстве случаев избавляемся от самой дорогостоящей операции во всем этом поиске - от сравнения строк.

Реализации AVL деревьев есть у меня на сайте.

PS: И после этого люди еще сомневаются в необходимости систематического матматического образования...

← →
Ketmar © (2006-10-30 13:14) [4]

кстати: а что вы скажете об FNV hash?

← →
MBo © (2006-10-30 13:40) [5]

>Пытаться трансформировать дерево с учетом частоты - неблагодарное занятие

splay tree как раз для этого и предназначено, с его использованием, например, можно Хаффмана строить.

← →
Alex Konshin © (2006-10-30 14:02) [6]

> MBo © (30.10.06 13:40) [5]
> >Пытаться трансформировать дерево с учетом частоты - неблагодарное занятие
>
> splay tree как раз для этого и предназначено, с его использованием,
> например, можно Хаффмана строить.

Охотно верю, что можно, только это неразумно. Если это именно дерево поиска, то несомненно лучше, чтобы оно было сбалансированным. А Хаффмана лучше уже отдельно строить. Иначе ни то, ни другое хорошо получаться не будет. Как я и говорил, не стоит путать мух с котлетами.

По-большому счету нужно знать, что человек хочет сотворить. Скорее всего он просто неправильно формализует задачу.

← →
KilkennyCat © (2006-10-30 14:14) [7]

> [6] Alex Konshin © (30.10.06 14:02)

формулирует :)

← →
Alex Konshin © (2006-10-30 14:24) [8]

> KilkennyCat © (30.10.06 14:14) [7]
> > [6] Alex Konshin © (30.10.06 14:02)
> формулирует :)

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

← →
Николай1984 (2006-10-30 15:20) [9]

Задача сформулирована верно, это задание по лабораторной работе
Целиком списал с распечатки.
Сижу уже неделю толку ни какого.
Может кто чтонибуть подскажет!

> [8] Alex Konshin © (30.10.06 14:24)

Гм... в этом случае, согласен. Но мне кажется, что формализация - это вышесказанное и постановка самой задачи в том числе.
И если задача иная, чем в сабже - тогда идеально подходит. В противном случае, если задача именно эта, уже ясна, настаиваю на своей поправке :)

> [9] Николай1984 (30.10.06 15:20)
> Задача сформулирована верно, это задание по лабораторной
> работе

Когда я тупел в институте, я пользовался методичками (это книжечки такие, не девушки :) )... дабы делать задания на уровне института :)
Неужто их (методичек) уж больше нет?

Бинарные деревья (деревья поиска) Найти похожие ветки