Элемент вставляется дважды (в оба поддерева).причина неизвестна - PullRequest
Новая
       11

Элемент вставляется дважды (в оба поддерева).причина неизвестна

0 голосов
/ 27 марта 2012

Я написал функцию, которая вставляет элемент в дерево, а затем возвращает новое дерево.Он принимает форму: 

% insert(Element, OldTree, NewTree)
?-insert(2, tree(nil, 5, nil), T).

и, по идее, должен возвращать: 

T = tree(tree(nil, 2, nil) 5, nil)

Проще говоря, эти два добавляются в левое поддерево, а nils добавляются для созданияэто бинарный.Тем не менее, в моем имплантации, оба добавляются к левому и правому поддереву.Условия всегда нарушаются;если 2 было 6, оно все равно добавляется к обоим поддеревьям, а не только к правым.

Я просматривал этот код в течение часа и не могу найти ошибку.Может ли свежая пара глаз скользить через это? 

tree(Left, Root, Right).

insert(Item, Oldtree, Newtree).

%tree is empty
insert(Element, Empty, tree(Empty, Element, Empty)):-!.

%tree isn't empty. if NewItem is less than Root, we put it on the left subtree
insert(NewItem, tree(LeftSubtree, Root, RightSubtree), tree(NewLeftSubtree, Root, RightSubtree)):-
        NewItem < Root,
    !,
        insert(NewItem, LeftSubtree, NewLeftSubtree).

%else
insert(NewItem, tree(LeftSubtree, Root, RightSubtree), tree(LeftSubtree, Root, NewRightSubtree)):-
    NewItem > Root,
    !,
        insert(NewItem, RightSubtree, NewRightSubtree).

1 Ответ

1 голос
/ 27 марта 2012

Прежде всего, не делайте этого: 

tree(Left, Root, Right).

Это определяет tree как (довольно бесполезный) предикат. Вам не нужно объявлять типы данных в Прологе.

Далее 

insert(Item, Oldtree, Newtree).

определяет insert/3 как предикат, который всегда будет успешным. Вам не нужен этот пункт. 

insert(Element, Empty, tree(Empty, Element, Empty)):-!.

не делает то, что, как вы думаете, делает; Empty - переменная, поэтому она соответствует чему угодно.

Наконец, вместо всей сложной логики вырезания используйте if-then-else: 

insert(X, tree(L0,Y,R0), tree(L,Y,R)) :-
    (X < Y ->
        % insert into left subtree
    ; X > Y ->
        % insert into right subtree
    ;
        % equals case
    ).
...