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

← →
@!!ex © (2008-09-23 19:50) [0]

есть бинарное дерево.
ветка либо содержит ссылку на две другие ветки, либо значение.
значение - это строка. может принимать "wildcard" или любое другие значение(список заранее не известен, количество тоже).
у ветки должна быть функция, которая возвращает true, если количество уникальных значений("wildcard" не считается) 2 и больше, и соответственно false, если значение только одно.

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

← →
@!!ex © (2008-09-23 20:06) [1]

Столкнулся с идиотской проблемой.
есть 4 переменных
p1_1,p1_2,p2_1,p2_2

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

← →
@!!ex © (2008-09-23 20:33) [2]

сделал вот так:
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
не работает...

← →
Zeqfreed © (2008-09-23 22:03) [3]

Я так понимаю, что функция достаточно часто вызывается? Есть, наверное, смысл хранить список всех значений из дерева и при добавлении узла в дерево выполнять проверку по сортированному списку.

← →
tesseract © (2008-09-23 22:59) [4]

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

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

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

← →
tesseract © (2008-09-23 23:00) [5]

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

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

← →
Zeqfreed © (2008-09-23 23:20) [6]

> tesseract © (23.09.08 23:00) [5]

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

← →
@!!ex © (2008-09-23 23:23) [7]

Оно не то что не уопрядоченное... его в принципе нельзя упорядычевать...

← →
Zeqfreed © (2008-09-23 23:25) [8]

> @!!ex © (23.09.08 23:23) [7]

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

← →
@!!ex © (2008-09-23 23:26) [9]

вот так - работает(вроде):
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 файл. хорошо еще, что они не в байткоде...

← →
KilkennyCat © (2008-09-23 23:43) [10]

я с деревьями работать не умею... но я б его на матрицу наложил бы и по ней играючи пробежался б.

← →
MBo © (2008-09-24 05:05) [11]

Возможно, для этой цели лучше использовать дерево, в котором только уникальные ключи. А если нужно несколько элементов с одним ключом, то держать их в одном узле (в списке, например)

← →
@!!ex © (2008-09-24 09:30) [12]

Да не мой код. :)
поэтому структуру данных менять не реально, да и дерево со своей задачей прекрасно справляется.

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

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

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

>AndreyV
Да, действительно

> [14] AndreyV © (24.09.08 10:41)
> Зачем заносить?
> Достаточно сохранить первый елемент и сравнивать текущий
> с ним.

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

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

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

Примерно это и делается в [9]

помогите составить алгоритм сравнения элементов бинарного дерева Найти похожие ветки