Drzewiec (informatyka)
Drzewiec – forma binarnego drzewa poszukiwań pozwalająca na wyszukiwanie binarne wśród kluczy. Po każdej sekwencji wstawień i usunięć kluczy kształt drzewa wyraża się zmienną losową z jednakowym prawdopodobieństwem dystrybucji, jak przy drzewach losowych; w szczególności, z dużym prawdopodobieństwem, jego wysokość jest proporcjonalna do logarytmu ilości kluczy tak, że każde wyszukiwanie, wstawianie lub usuwanie trwa przez czas logarytmiczny.
Drzewiec został po raz pierwszy przedstawiony przez Cecilię Aragon i Raimunda Seidela w 1989 roku[1][2]. Nazwa ta jest zbitką wyrazów „drzewo” i „kopiec”.
Opis
[edytuj | edytuj kod]
Jest to drzewo, w którym każdy klucz posiada losowo wybrany priorytet. Strukturę drzewa zadaje wymóg utrzymania porządku kopcowego (według priorytetów kluczy). Na każdej ścieżce, od korzenia do liścia, kolejno przeglądane priorytety muszą maleć. W ten sposób korzeń drzewca jest wierzchołkiem o najwyższym priorytetem (co przekłada się na fakt, że każdy wierzchołek jest wierzchołkiem o największym priorytecie w drzewie zawieszonym w tym wierzchołku).
Operacje
[edytuj | edytuj kod]Drzewce obsługują następujące podstawowe operacje:
- Do wyszukiwania wartości klucza stosujemy standardowy binarny algorytm wyszukiwania w drzewie binarnych wyszukiwań, ignorując priorytety.
- Aby wstawić nowy klucz x do drzewca, generujemy losowy priorytet g dla x. Wyszukujemy x w drzewcu i tworzymy nowy wierzchołek jako liść w miejscu, które wskaże binarne przeszukiwanie. Następnie, o ile x nie jest korzeniem i ma większy priorytet niż jego rodzic h (a więc zaburzona jest własność kopca), wykonujemy rotacje pomiędzy x i h.
- Aby usunąć węzeł x z drzewca:
- Jeśli x jest liściem drzewa, usuwamy go.
- Jeśli x ma jedno dziecko (z), usuwamy x z drzewa, a z czynimy dzieckiem dotychczasowego rodzica dla x (lub korzeniem drzewa, jeśli x nie miał rodzica).
- Jeśli x ma dwoje dzieci, wybieramy dziecko (z) o wyższym priorytecie. Następnie rotujemy z-x tak, żeby dziecko wynieść wyżej. Dzięki temu, że wybraliśmy dziecko o wyższym priorytecie, porządek kopcowy zostaje zachowany. Potarzamy operację tak długo, aż dojdziemy z wierzchołkiem x do któregoś z powyższych przypadków[3].
Przypisy
[edytuj | edytuj kod]- ↑ Cecilia R. Aragon, Raimund Seidel, Randomized Search Trees - Proc. 30th Symp. Foundations of Computer Science (FOCS 1989), Washington, D.C.: IEEE Computer Society Press, 1989, s. 540–545, DOI: 10.1109/SFCS.1989.63531, ISBN 0-8186-1982-1 (ang.).
- ↑ Raimund Seidel, Cecilia R. Aragon. Randomized Search Trees. „Algorithmica”. 16 (4/5), s. 464–497, 1996. DOI: 10.1007/s004539900061. (ang.).
- ↑ Michał Karpiński: Drzewce | Wrocławski Portal Informatyczny. informatyka.wroc.pl, 2010-10-03. [dostęp 2016-06-19].