Drzewce
03.10.2010 - Michał Karpiński
O drzewcach bardziej szczegółowoRozpoczniemy od poznania budowy węzła w drzewcu. Z każdym węzłem związane są następujące informacje:
Należy pamiętać, że jeśli x jest korzeniem drzewca, to znaczy, że nie posiada ojca. W takim przypadku przypisujemy atrybutowi wartość (czyli: nic). Wykonujemy podobny zabieg, gdy dany węzeł nie posiada prawego lub lewego syna. Mamy już wystarczającą ilość informacji, aby móc formalnie zdefiniować strukturę drzewca. Drzewiec jest to ukorzenione drzewo binarne, w którym każdy węzeł nie będący liściem spełnia następujące zależności:
Operacje na drzewcachJak już zostało wspomniane: na drzewcach można wykonywać takie same operacje jak na zwykłym drzewie BST. Oprócz wyszukiwania, wstawiania i usuwania danego elementu zajmować się też będziemy rozdzielaniem i scalaniem drzewców. Z powyżej wymienionych procedur pominiemy wyszukiwanie elementu o podanym kluczu, gdyż jest ona identyczna z procedurą wyszukiwania dla drzew BST. Procedura "Insert"Na początek zajmiemy się wstawianiem nowego elementu do drzewca. Losujemy priorytet dla nowego węzła przed rozpoczęciem wstawania. Należy pamiętać, że wszystkie własności drzewca podane w definicji muszą zostać zachowane po wstawieniu nowego elementu, dlatego procedurę wstawiania będziemy wykonywali w dwóch krokach:
Rozważmy prosty przykład: Na rysunku powyżej użyliśmy zwykłej procedury do umieszczenia węzła o wartości 7 i priorytecie 0.98 w drzewcu. Po wstawieniu elementu na odpowiednie miejsce zachowana jest własność drzewa BST, ale zwróćmy uwagę na węzeł o kluczu 5. Jego priorytet wynosi 0.54 i jest zdecydowanie mniejszy od priorytetu nowo dodanego syna. Z tej obserwacji wynika, że po wstawieniu nowego elementu, drzewo z rysunku przestało być poprawnie zbudowanym drzewcem. Należy wykonać drugi krok procedury wstawiania, czyli przywrócenie priorytetom własności kopca. Nie możemy jednak tak po prostu zamienić ze sobą syna z ojcem, gdyż zburzy to własność BST. Nasuwa się pytanie: Czy istnieje operacja na węzłach, która zmieni strukturę drzewa BST nie zaburzając przy tym porządku inorder?Okazuje się, że taka operacja istnieje i nazywa się rotacją. (2 ocen) |
Copyright © 2008-2010 Wrocławski Portal Informatyczny
design: rafalpolito.com