Operacje Drzewce obsługują następujące podstawowe operacje: Do wyszukiwania wartości klucza stosuje się 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. Powtarzamy operację tak długo, aż dojdziemy z wierzchołkiem x do któregoś z powyższych przypadków.
Przypisy
Kategoria:Drzewa (informatyka)