Drzewce

03.10.2010 - Michał Karpiński
TrudnośćTrudnośćTrudność

O drzewcach bardziej szczegółowo

Rozpoczniemy od poznania budowy węzła w drzewcu. Z każdym węzłem $ x $ związane są następujące informacje:

  • $ key[x] $ – klucz (lub wartość) węzła $ x $
  • $ left[x] $ – lewy syn węzła $ x $
  • $ right[x] $ – prawy syn węzła $ x $
  • $ parent[x] $ – ojciec $ x $-a
  • $ priority[x] $ – priotytet węzła $ x $

Należy pamiętać, że jeśli x jest korzeniem drzewca, to znaczy, że nie posiada ojca. W takim przypadku przypisujemy atrybutowi $ parent[x] $ wartość $ NULL $ (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ł $ x $ nie będący liściem spełnia następujące zależności:

  • $ key[x] $ > $ key[left[x]] $
  • $ key[x] $ < $ key[right[x]] $
  • $ priority[x] \ge priority[left[x]] $
  • $ priority[x] \ge priority[right[x]] $

Operacje na drzewcach

Jak 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:

  • wstawiamy element do drzewca tak, jakbyśmy wstawiali go do drzewa BST
  • przywracamy priorytetom własność kopca, którą mógł zaburzyć priorytet nowo wstawionego elementu

Rozważmy prosty przykład:

Na rysunku powyżej użyliśmy zwykłej procedury $ Insert $ 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ą.

5
Twoja ocena: Brak Ocena: 5 (2 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com