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.

Zobacz też: inne znaczenia słowa „drzewiec”.

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

Drzewiec z alfabetycznymi kluczami i liczbowym porządkiem kopcowym

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

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].