бинарное дерево

[Pengu1n]

Хай пипл! Может кто-нибудь сталкивался с этим зверем? а то дали задание написать на паскале базу данных используя эту хрень, ничего не объяснили а литературы 2 отсвеченых листочка подкинули , препод у нас урод уродом...
Где бы раздобыть нормальное объяснение этой структуры, в инете исходники нашел, а толку с них

[dr-evil]

дык все просто....
от листа =) идет 2 листа...
и т.д. наподобие дерева катологов... где в каждом каталоге 2 подкаталога....
увы мои исходники на паскале умерли... а др. нету

[Makc]

Pengu1n
У меня на сайте есть этот компонент - Tree
http://msp.bip.ru/programming/delphi_components/036.zip
P>S> если скаже что ссылка мертвая, то зайди на сайт и попробуй скчать оттуда.

[aleh]

Двоичное дерево строится на принципах:
1) дерево строится из элементов-узлов
2) у каждого элемента-узла может быть два под-узла (но не больше, поэтому дерево и называется двоичным
3) что меньше -- налево, что больше -- направо
*) Как следствие, в одном дереве не могут существовать два элемента с одинаковым значением (PRIMARY KEY)

Двоичное (иначе бинарное) дерево применяется для быстрого поиска. Если в дереве содержится N элементов, то в худшем случае поиск занимает N итераций, а в лучшем -- log2(N). Чтобы всегда иметь только лучшие показатели, дерево должно быть сбалансировано. Тут тебе нужно уяснить что такое красно-чёрные деревья.

Решение в лоб:
1) создаётся массив записей R[]
2) у записи выбирается ключевое поле (или набор полей) R.key
3) создатся массив индексов/номеров записей I[], только при движении по этому массиву от начального элемента до конечного должно соблюдатся правило R[I[i]].key < R[I[i+1]].key (можно использовать и не строгое неравенство, если допускается нексолько ключей с одинаковым значением)
4) При поиске, вставке, изменениии нужно быстро пробегать по массиву I[] методом половинного деления (поиск по двоичному дереву) и дальше по смыслу...
-- главный недостаток -- необходимо очень сильно двигать элементы массива I[] при изменении, добавлении, удалении ключа, это очень ресурсоёмкая операция.

В любом случае, без сбалансированного дерева нормальную БД построить нереально. (Хотя мир клином не сошёлся на бинароном дереве, есть ещё и троичные и под фибоначи и хэш и ...)

[melk]

(пишу на С++, поэтому сори за неточности)
1) Создается структура, либо класс, описывающая один узел.
2) Пишутся функции для работы с деревом. При этом каждый узел есть поддерево и может ничем не отличаться(кроме содержимого) от главного дерева. Для варианта без класса придется использовать глобальную переменную указатель на вершину дерева, либо всюду передавать локальную.

Отступление:
У каждого узла есть не >2 потомков, а он соответственно является их родителем.
Также иногда встречается название "дядя". Конечные узлы без потомков называют "внешними" или "листами" их антиподы - "внутренние" узлы.

Чтобы запихать дерево в массив его вершины нумеруются начиная с верха.
Номера потомков - 2*N и 2*N+1, где N - ноиер текущего узла. Вроде этого:
1
/ \
2 3
/ \ / \
4 5 6 7
Для бинарного дерева проще всего написать рекурсивные функции. Как правило такая функция обрабатывает значение в текущем узле и вызвает себя для 2 потомков от очередности этих трех действий зависит тип обхода дерева.

Если в силу некоторых причин рекурсивные функции писать нельзя/неоптимально пишутся итеративные, но тогда придется самому в цикле бегать по всему дереву и сохранять пройденный путь(либо завести указатель на родителя).

[TiamaT]

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

[melk]

представь себе сколько на до рекурсий для того, чтоб стэк заплющило в сбалансированном дереве? У меня такое только в графе случалось, да и то при количестве вершин > 10000

[ArchiMage]

melk
a prichem tut stack k derevu?
stack eto LIFO a derevo eto derevo

[joker99]

Имеется ввиду stack программы.
Каждый вызов функции заносит в стек программе аддрес возвращения и параметры вызова функции. Так как стек программы ограничен, то слишком глубокая рекурсия приведё к stack overflow

[ArchiMage]

joker99
а... не вьехал вчера, уставший был


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

[TiamaT]

представь себе сколько на до рекурсий для того, чтоб стэк заплющило в сбалансированном дереве? У меня такое только в графе случалось, да и то при количестве вершин > 10000

Когда я писал в свое время BSP buider для игрушки у меня и больше вершин бывало :-)