Drzewa wyszkiwań binarnych
Są to drzewa binarne, w których każdy wierzchołek x ma wskaźnik na ojca, syna lewego, syna prawego, klucz k i być może inne informacje. Drzewa binarne mają własność: wszystkie wierzchołki w lewym poddrzewie mają klucze niewiększe niż klucz ojca, wszystkie wierzchołki w prawym poddrzewie mają klucze niemniejsze niż klucz ojca. Przykłady: pierwszy, drugi.
Różne funkcje na drzewach wyszukiwań binarnych:
Stwórz program, który stworzy "na sztywno" nieduże drzewo z paroma wierzchołkami (można ręcznie podwiązywać). Następnie przetestuj na nim poniższe procedury:
- Inorder-Tree-Walk (wypisującą klucze wierzchołków)
- Tree-Search (zwraca wierzchołek), następnie wypisz klucz tego wierzchołka jeśli jest niepusty
- Min i Max, które po podaniu wierzchołka wyszukują element najmniejszy i największy w poddrzewie tego wierzchołka (potem wypisz klucze)
- Successor i Predecessor - po podaniu x, wyszkują następnik i poprzednik elementu (czyli elementmniejszy od x który jest największy, i element większy od x, który jest najmniejszy).
Chcielibyśmy, aby drzewa BST były jakoś rysowane, co przyda nam się do weryfikacji działania procedur. Rysowanie drzewa na konsoli za pomocą znaczków nie jest zbyt profesjonalne. Naszym zadaniem będzie napisanie procedury Draw-Tree(T), która dla podanego drzewa (maksymalnie wysokości 3) wygeneruje plik html z rysunkiem tego drzewa.
Jak to jest możliwe? Ściągnij przykłady i otwórz je w edytorze tekstu: pierwszy, drugi. Jak widać, drzewa można osadzić na stronie html jako obrazek svg, który tworzy się wpisując odpowiednie komendy. Poeksperymentuj z dodawaniem i kasowaniem komend. Zajrzyj też na tutorial i interaktywne przykłady.