Мастера DELPHI (документация, исходники, скачать)

Основная («Начинающим»)/ Базы / WinAPI / Компоненты / Сети / Media / Игры / Corba и COM / KOL / FreePascal / .Net / Прочее / RSDN.ORG

« предыдущая ветвь | форум | следующая ветвь »

помогите составить алгоритм сравнения элементов бинарного дерева

@!!ex © (2008-09-23 19:50:00)
есть бинарное дерево.
ветка либо содержит ссылку на две другие ветки, либо значение.
значение - это строка. может принимать "wildcard" или любое другие значение(список заранее не известен, количество тоже).
у ветки должна быть функция, которая возвращает true, если количество уникальных значений("wildcard" не считается) 2 и больше, и соответственно false, если значение только одно.

Тоесть прдеположим дерево вида:
*
| \
* *
| \ | \
wildcard a a b
должно вернуть true
*
| \
* *
| \ | \
wildcard a a a
false
и так далее..
Я видимо совсем устал, вообще не могу придумать, как это сделать...

@!!ex (2008-09-24 11:41:00) [1]
Примерно это и делается в [9]

AndreyV (2008-09-24 11:35:00) [2]
> [16] @!!ex © (24.09.08 11:26)
> > [14] AndreyV © (24.09.08 10:41)
> > Зачем заносить?
> > Достаточно сохранить первый елемент и сравнивать текущий
>
> > с ним.
>
> недостаточно. первый элемент может быть wildcard

Первый, который не wildcard.

@!!ex (2008-09-24 11:26:00) [3]
> [14] AndreyV © (24.09.08 10:41)
> Зачем заносить?
> Достаточно сохранить первый елемент и сравнивать текущий
> с ним.

недостаточно. первый элемент может быть wildcard

MBo (2008-09-24 11:09:00) [4]
>AndreyV
Да, действительно

AndreyV (2008-09-24 10:41:00) [5]
> [13] MBo © (24.09.08 10:04)
> Ну тогда обход ветки с занесением данных в какую-либо структуру
> типа множества - бинарное дерево поиска, хэш-таблица, при
> небольших размерах - (сортированный) массив

Зачем заносить?
Достаточно сохранить первый елемент и сравнивать текущий с ним.

MBo (2008-09-24 10:04:00) [6]
Ну тогда обход ветки с занесением данных в какую-либо структуру типа множества - бинарное дерево поиска, хэш-таблица, при небольших размерах - (сортированный) массив

@!!ex (2008-09-24 09:30:00) [7]
Да не мой код. :)
поэтому структуру данных менять не реально, да и дерево со своей задачей прекрасно справляется.

MBo (2008-09-24 05:05:00) [8]
Возможно, для этой цели лучше использовать дерево, в котором только уникальные ключи. А если нужно несколько элементов с одним ключом, то держать их в одном узле (в списке, например)

KilkennyCat (2008-09-23 23:43:00) [9]
я с деревьями работать не умею... но я б его на матрицу наложил бы и по ней играючи пробежался б.

@!!ex (2008-09-23 23:26:00) [10]
вот так - работает(вроде):
function Node:getItems() if self[_p].mElement then return self[_p].mElement,self[_p].mElement else local p1_1,p1_2 = self[_p].mChildren[1]:getItems() local p2_1,p2_2 = self[_p].mChildren[2]:getItems() if p1_1 == 'wildcard' then return p2_1,p2_2 end if p2_1 == 'wildcard' then return p1_1,p1_2 end if p1_1 ~= p1_2 then return p1_1,p1_2 end if p1_1 ~= p2_1 then return p1_1,p2_1 end return p1_1,p2_2 end end -- function Node:haveMoves() assert(not self[_p].mElement,'haveMoves for root node') if self[_p].mChildren[1]:isLeaf() and self[_p].mChildren[2]:isLeaf() then return true end local p1_1,p1_2 = self:getItems() return p1_1~=p1_2 and p1_1~='wildcard' and p1_2~='wildcard' end
То, что тут используется бинарное дерево - не самоцель, просто так получилось, что структура в итоге оказалась бинарным деревом. больше суток это курочил, только несколько часов назад понял что это за структура...

P.S.
Вообще очень увлекательное занятие - править lua скрипты зашитые в exe файл. хорошо еще, что они не в байткоде...

Zeqfreed (2008-09-23 23:25:00) [11]
> @!!ex © (23.09.08 23:23) [7]

Тогда оно является практически бессмысленным.
Мои варианты — либо дополнительный список, либо упорядоченная копия дерева.

@!!ex (2008-09-23 23:23:00) [12]
Оно не то что не уопрядоченное... его в принципе нельзя упорядычевать...

Zeqfreed (2008-09-23 23:20:00) [13]
> tesseract © (23.09.08 23:00) [5]

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

tesseract (2008-09-23 23:00:00) [14]

> при добавлении узла в дерево выполнять проверку по сортированному
> списку.

Само дерево должно иметь подобную функциональность. И упорядичивание имеено на запись. Написано в любой книжке по алгоритмике.

tesseract (2008-09-23 22:59:00) [15]

> есть бинарное дерево.

Сделай его самоупорядочиваемым. Красно-чёрные деревтя теб в помощь.

ЗЫ: Практическое применение несамоупорядочивающихся бинарных деревьев для меня загадка.

Zeqfreed (2008-09-23 22:03:00) [16]
Я так понимаю, что функция достаточно часто вызывается? Есть, наверное, смысл хранить список всех значений из дерева и при добавлении узла в дерево выполнять проверку по сортированному списку.

@!!ex (2008-09-23 20:33:00) [17]
сделал вот так:
function Node:getItems() if self[_p].mElement then return self[_p].mElement,self[_p].mElement else local p1_1,p1_2 = self[_p].mChildren[1]:getItems() local p2_1,p2_2 = self[_p].mChildren[2]:getItems() if p1_1 == 'wildcard' then return p2_1,p2_2 end if p2_1 == 'wildcard' then return p1_1,p1_2 end if p1_1 ~= p1_2 then return p1_1,p1_2 end if p1_1 ~= p2_1 then return p1_1,p2_1 end return p1_1,p2_2 end end ----- function Node:haveMoves() assert(not self[_p].mElement,'haveMoves for root node') local p1_1,p1_2 = self:getItems() return p1_1~=p1_2 and p1_1~='wildcard' and p1_2~='wildcard' end
не работает...

@!!ex (2008-09-23 20:06:00) [18]
Столкнулся с идиотской проблемой.
есть 4 переменных
p1_1,p1_2,p2_1,p2_2

нужно переменным r1,r2 присовить две из этих переменных, так чтобы по возможности они были разными и среди них не было wildcard.

Наверх

	« предыдущая ветвь \| форум \| следующая ветвь »