Реально реализовать АВЛ-дерево в БД?

← →
partizan (2006-08-07 19:55) [0]

Нужно реализовать структуру типа АВЛ-дерева в тадлице БД (postgreSQL),
а все операции - функциями на языке сервера.

Более подробное описание задачи тут: http://delphimaster.net/view/1-1154964112/

← →
tesseract © (2006-08-07 21:51) [1]

что такое АВЛ? Не припомню что-то, хотя бакнелла перичитывал.

Если тебе нужны nested sets - соединённые множества. Идея есть в статьях на сайте. Кроме того есть модуль на перл+ SQL запросы.

Google dfv gjvj;tn

← →
Мефисто (2006-08-07 22:03) [2]

> что такое АВЛ? Не припомню что-то, хотя бакнелла перичитывал.

Значит не читал ;)

Это бинарные деревья

← →
tesseract © (2006-08-07 23:01) [3]

> [2] Мефисто (07.08.06 22:03)

Чего-то таких не помню. Возможно переработал. Но для задачи нужны nested sets.

← →
Мефисто (2006-08-07 23:05) [4]

Не красно-черное ли дерево случаем нужно?

← →
tesseract © (2006-08-08 10:16) [5]

> Мефисто (07.08.06 23:05) [4]

зачем они?

http://www.webscript.ru/stories/04/09/01/8197045

← →
Romkin © (2006-08-08 10:26) [6]

Млин. Ну и нафига? Структура данных в программе и в реляционных таблицах - разные вещи. Почему ты решил, что реализация дерева будет выгодной?

← →
Alex Konshin © (2006-08-08 10:30) [7]

Глупости. AVL дерево-то зачем?
Если это в базе, то почему не спросить count для записей, у которых твой "ранг" меньше искомого?

← →
tesseract © (2006-08-08 10:47) [8]

>> Alex Konshin © (08.08.06 10:30) [7]

Нужна такая структура, которая позволяла бы быстро вычислить порядковый номер определенного ел-та (у ел-та с наибольшим рангом порядковый номер - 1 ), другими словами количество елементов, у которых ранг больше заданного. Новые елементы добавляются всегда с наибольшим рангом (на 1-е место). Удаляться может любой елемент. Так же любой елемент может "поднятся" на 1-е место

ИМХО имеються в виду древовидные структуры данных, только не можем поянть.

← →
NeyroSpace © (2006-08-08 15:08) [9]

Сделать можно, а иногда даже и нужно.
Вот тут подробно описано, правда на FireBird:
http://ibase.ru/develop.htm#books

Имхо, базам - базово :) БД для того и выдумали, чтобы производить добавление/удаление/поиск информации тупо и не задумываясь об ABL или еще каких-нибудь деревьях. А если тебя по каким-то причинам стандартные механизмы БД не устраивают - то ты реализуешь понравившийся тебе АТД сам, ручками.

Впихать, точнее прикрутить АВЛ к БД можно разве что в поиске...
гы-гы-гы, ведь для поиска эта структура и была создана... :)
(IMHO дикость, поиск по базе должен и без того быть быстрым, это
накладно как с точки зрения машинного времени, так и с точки зрения
времени разработки ПО)

Cash © (08.08.06 22:29) [11]
> IMHO дикость, поиск по базе должен и без того быть быстрым
Ну конечно же, поиск по индексированному полю будет происходить быстрее чем при использовании АВЛ-деревьев, хранящихся к тому же в базе данных. Но автор же не справшивает плохо это будет работать или хорошо. Он просит помочь реализовать. Может, в вузе или при приеме на работу такое задание дали, а может поспорил с кем.

← →
partizan (2006-08-10 17:03) [13]

> Если это в базе, то почему не спросить count для записей,
> у которых твой "ранг" меньше искомого?

Потому, что в базе несколько миллионов записей - будет долго.ю

> Почему ты решил, что реализация дерева будет выгодной?

Потому, что при такой реализации можно быстро вычислять количество записей, у которых "ранг" меньше искомого

> Сделать можно, а иногда даже и нужно.
> Вот тут подробно описано, правда на FireBird:
> http://ibase.ru/develop.htm#books

Спасибо, гляну

Реально реализовать АВЛ-дерево в БД? Найти похожие ветки