Drzewa przeszukiwań binarnych

14.12.2009 - Michał Karpiński
Trudność

Dodawanie elementu

Wszystkie operacje, które dotychczas wykonywaliśmy na drzewie BST nie zmieniały jego struktury, natomiast w tym rozdziale pokażę procedurę INSERT, która zmienia zbiór dynamiczny reprezentowany przez drzewo BST.

Dodanie nowego elementu nie powinno być trudnym zadaniem. Oczywistym jest, iż nowy element wstawimy w „puste miejsce gdzieś na dole drzewa”. Pytanie, które od razu się nasuwa to: jak do tego pustego miejsca dotrzeć?

Odpowiedź chyba nie powinna nikogo zaskoczyć: wystarczy skorzystać z własności drzewa BST i - zaczynając od korzenia - jeśli wartość nowego elementu jest mniejsza od wartości węzła, do którego dodajemy element, to nowy element dodamy do jego lewego poddrzewa. W przeciwnym przypadku krok powtarzamy dla prawego poddrzewa. Algorytm iteracyjny przedstawia się następująco:

Z definicji wynika, że należy też rozpatrzyć przypadek, w którym dodajemy element do drzewa pustego.

Czas wykonania procedury INSERT, podobnie jak poprzednio poznanych podstawowych operacji na drzewie BST, jest zależny od wysokości drzewa i wynosi O(h).

Usuwanie elementu

W przeciwieństwie do wstawiania, usuwanie elementu nie jest już takie proste. Przypadki, które należy rozpatrzeć przedstawia poniższy rysunek.

Zakładamy, że posiadamy wskaźnik do elementu z, który chcemy usunąć z danego drzewa BST. W pierwszym przypadku element z nie posiada żadnych synów. Wtedy wystarczy ustawić w ojcu z-eta wskaźnik na z jako NULL. W drugim przypadku usuwany element ma jednego syna. Tutaj trzeba ustawić wskaźnik ojca z-eta - który wcześniej wskazywał na z - na syna z-eta. I w końcu, gdy usuwany element ma dwóch synów, trzeba usuwany element zamienić z jego następnikiem ( nazwijmy go y ). Następnik może mięć maksymalnie tylko jednego syna, którego dołączamy w miejsce następnika.

Czas działania procedury DELETE wynosi O(h).

4.25
Twoja ocena: Brak Ocena: 4.3 (4 ocen)

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com