[java] binary search tree przeszukiwanie

mam sobie klasyczne BST, z tym że zamiast samych intów zawiera ono pary string + double, musze napisać metode ktora zwraca true jesli w drzewku znajduje sie para o danym stringu. jak to zrobic? drzewko jest budowane na podstawie wartosci double. mam coś takiego:

Kod:

public boolean search(String s) { if (current.compareKeys(s)) { System.out.println("yup"); return true; } if (right != null) right.search(s); if (left != null) left.search(s); System.out.println("nope"); return false; }

Kod:

///METODA COMPARE KEYS Z KLASY PAIR KTORA PRZECHOWUJE String key i dou public boolean compareKeys(String s) { if (key.equals(s)) { return true; } return false; }

tylko że to przeszukuje cale drzewko, i nawet jesli znajdzie moj klucz to i tak zwroci na koncu false, to przykładowy output:

Kod:

nope nope yup nope nope nope nope nope nope

nie moge tez zastosowac klasycznego przeszukiwania drzewek, tutaj przyklad w nie-javie z wiki:

Kod:

define BST_TREE_SEARCH (Node, Key): if (Node == NULL) or (Node->Key == Key) return Node if Key < Node->Key return BST_TREE_SEARCH (Node->Left, Key) return BST_TREE_SEARCH (Node->Right, Key)

bo liczy sie tam wartosc klucza, a w moim przypadku jest to nieistotne

mecze się nad tym już którąś godzine, a jestem pewien ze rozwiązanie jest jakieś mega proste. nakierujcie mnie proszę!

edit. moglbym zrobic np zmienna found i zrobic cos takiego

Kod:

boolean found = false; public boolean search3(string s) { found = false; root.search2(s); return found; }

a w search2 dodac to, ze jesli znajdzie moj klucz to zmienia wartosc found na true, ale chyba da sie to rozwiazac jakos inaczej?

No ale w sumie nic nam nie daje fakt, że jest to bst. Zrób zwykłego dfsa bez rekurencji i będziesz miał wszystko w jednej metodzie ;d

A jakby sprawdzić w searchu:
if oba dzieci: return left.search || right.search
elif tylko lewe: return left.search
elif tylko prawe: return right.search
else: return false;

Cytuj:

Absherr napisał

No ale w sumie nic nam nie daje fakt, że jest to bst. Zrób zwykłego dfsa bez rekurencji i będziesz miał wszystko w jednej metodzie ;d

A jakby sprawdzić w searchu:
if oba dzieci: return left.search || right.search
elif tylko lewe: return left.search
elif tylko prawe: return right.search
else: return false;

Kod:

public boolean search(String s) { if (current.compareKeys(s)) { System.out.println("yup"); return true; } if (right != null && left != null) return right.search(s) || left.search(s); else if (left == null) return right.search(s); else if (right == null) return left.search(s); else return false; }

wypierdala nullpointera w sumie nie wiem czemu, zaraz sprawdze dfs

Kod:

public boolean search(String s) { if (current.compareKeys(s)) { System.out.println("yup"); return true; } if (right != null && left != null) return right.search(s) || left.search(s); else if (left == null) return right.search(s); else if (right == null) return left.search(s); else return false; }

Nullpointer? nie mam pojęcia czemu ;/

Może tak:

Kod:

public boolean search(String s) { if (current.compareKeys(s)) { System.out.println("yup"); return true; } if (right != null && left != null) return right.search(s) || left.search(s); else if (left != null) return left.search(s); else if (right != null) return right.search(s); else return false; }

@down
No brawo Szerloku ;d

Cytuj:

Absherr napisał

Kod:

public boolean search(String s) { if (current.compareKeys(s)) { System.out.println("yup"); return true; } if (right != null && left != null) return right.search(s) || left.search(s); else if (left == null) return right.search(s); else if (right == null) return left.search(s); else return false; }

Nullpointer? nie mam pojęcia czemu ;/

no a jak left == null && right == null?

@Terr ; zdradź mi co robisz? ;)

Cytuj:

Absherr napisał

Kod:

public boolean search(String s) { if (current.compareKeys(s)) { System.out.println("yup"); return true; } if (right != null && left != null) return right.search(s) || left.search(s); else if (left == null) return right.search(s); else if (right == null) return left.search(s); else return false; }

Nullpointer? nie mam pojęcia czemu ;/

Może tak:

Kod:

public boolean search(String s) { if (current.compareKeys(s)) { System.out.println("yup"); return true; } if (right != null && left != null) return right.search(s) || left.search(s); else if (left != null) return left.search(s); else if (right != null) return right.search(s); else return false; }

@down
No brawo Szerloku ;d

ooo królu złoty, teraz działa, dzięki!

cusz, nie pomyslalem o przypadku kiedy left i right są nullami

a robie to: @LordCompi ;
http://www.ii.uni.wroc.pl/~prz/2014z...a/zad/zad4.pdf

Kolega z IIUWr?

Kursy są lepsze z Hansem. Polecam ;).

IMHO dobrym pomysłem byłoby napisanie 'generycznej' implementacji BST i przekazywanie strategii porównywania jako parametr konstruktora drzewa. Możesz w tym celu wykorzystać klasy sparametryzowane.

Pozdrawiam
Killavus