algorytm.org

Drzewa Poszukiwań Binarnych (BST)

Baza Wiedzy
wersja offline serwisu przeznaczona na urządzenia z systemem Android
Darowizny
darowiznaWspomóż rozwój serwisu
Nagłówki RSS
Artykuły
Implementacje
Komentarze
Forum
Bookmarki






Sonda
Implementacji w jakim języku programowania poszukujesz?

Drzewa Poszukiwań Binarnych (BST)
Ocena użytkowników:***** / 60
SłabyŚwietny 
Wpisany przez Michał Knasiecki, 16 sierpnia 2005 19:23

Drzewo BST (binary search tree) jest drzewem binarnym. Oprócz pola wartości drzewo BST posiada jeszcze dwa pola: L i P, wskazujące odpowiednio na lewy i prawy następnik. Drzewo BST ma szczególną własność:
  • jeżeli element drzewa znajduje się w lewej gałęzi to jest mniejszy od swego poprzednika
  • jeżeli element drzewa znajduje się w prawej gałęzi to jest większy od swego poprzednika

Oto przykładowe drzewo BST:
drzewo BST

Przeszukiwanie drzewa:
  • Wzdłużne - preorder: korzeń, lewe poddrzewo, prawe poddrzewo.
  • Poprzeczne - inorder: lewe poddrzewo, korzeń, prawe poddrzewo.
  • Wsteczne - postorder: lewe poddrzewo, prawe poddrzewo, korzeń.
Dodwanie elementów:
Jeśli drzewo BST jest puste (korzeń=nil) należy wstawić element (nie porównujemy go z innymi), w przeciwnym wypadku porównujemy wartość elementu z następnikami każdego węzła (zaczynając od korzenia). Jeżeli wartość elementu jest niewiększa od wartości porównywanego wierzchołka to przechodzimy do lewego następnika, w przeciwnym razie przechodzimy do prawego następnika. Krok ten powtarzamy aż znajdziemy dla naszego elementu odpowiedznie miejsce, tzn. gdy następnik, do którego powinniśmy iść jest pusty (nil). Następnie wstawiamy element jako odpowiedni następnik (prawy, jeśli element jest większy od węzła, lewy jeśli niewiększy).

Usuwanie elementów:
Jeżeli usuwany element nie ma następników to można zwolnić przydzieloną mu pamięć. Jeśli element do usunięcia ma jeden następnik należy go połączyć (następnik) z poprzednikiem usuwanego elementu. Jeśli element ma dwa następniki można go usunąć na dwa sposoby:
  • połączyć poprzednik elementu z wierzchołkiem o najmniejszej wartości z prawego poddrzewa usuwanego
  • połączyć poprzednik elementu z wierzchołkiem o największej wartości z lewego poddrzewa
Usuwanie drzewa:
Można to zrobić na dwa sposoby: od końca, schodząc za każdym razem od korzenia lub od korzenia. Ta druga metoda jest znacznie szybsza, wymaga jednak zastosowania stosu, na którym umieszczamy następniki usuwanego elementu. Po usunięciu elementu zdejmujemy ze stosu następny do usunięcia, umieszczamy na stosie jego następniki itd...

Implementacje
AutorJęzyk
programowania
KomentarzOtwórzPobierzOcena
Bartosz BednarczykC/C++Plik nagłówkowy - C++
.cpp
.cpp
***** / 10
Rafał GawlikC/C++
.cpp
.cpp
***** / 61
Michał KnasieckiDelphi/PascalBorland Delphi 5
.pas
.pas
***** / 14
Łukasz GuzJava
.java
.java
***** / 14
Marek RynarzewskiPhpBST + dodatkowe funkcje
.php
.php
***** / 1
 
Dodaj własną implementację tego algorytmu
  • Zaloguj się na stronie
Plik:
Język
programowania:
Komentarz:
  By móc dodać implementacje zaloguj się na stronie

Poprawiony: 30 sierpnia 2012 14:38
Komentarze
photo
0 # mazi 2010-01-29 21:04
jak bym chcial usunac wierzcholek 8 to jakie drzewa bym otrzymal
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+5 # Piotrek 2010-02-11 00:45
Zastępuje się wtedy ósemkę siódemką lub dziesiątką, tak jak jest to napisane w artykule.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+3 # majki90 2012-05-29 13:22
Wydaje mi się że wkradł się tu pewien błąd. Mianowicie Cytat:
Jeżeli usuwany element nie ma następników to można zwolnić przydzieloną mu pamięć. Jeśli element do usunięcia ma jeden następnik należy go połączyć (następnik) z poprzednikiem usuwanego elementu. Jeśli element ma dwa następniki można go usunąć na dwa sposoby:
a powinno być Cytat:
Jeżeli usuwany element nie ma potomków to można zwolnić przydzieloną mu pamięć. Jeśli element do usunięcia ma jednego potomka należy go połączyć (potomka) z poprzednikiem usuwanego elementu. Jeśli element ma dwóch potomków można go usunąć na dwa sposoby:
Każdy element ma chyba co najwyżej jednego następnika (poprzednika).
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
-6 # mateunho 2012-09-02 11:10
Cytuję definicję:
Oprócz pola wartości drzewo BST posiada jeszcze dwa pola: L i P, wskazujące odpowiednio na lewy i prawy następnik. Drzewo BST ma szczególną własność:
jeżeli element drzewa znajduje się w lewej gałęzi to jest mniejszy od swego poprzednika
jeżeli element drzewa znajduje się w prawej gałęzi to jest większy od swego poprzednika

Cytuję majki90:
Każdy element ma chyba co najwyżej jednego następnika (poprzednika).

Gwoli jasności: następnik = potomek, poprzednik = rodzic, więc zamienne używanie równoważnych określeń nie jest błędem.
Odpowiedz | Odpowiedz z cytatem | Cytować
photo
+5 # boro 2013-01-17 20:29
Następnik to węzeł, którego klucz ma wartość bezpośrednio większą od wartości zadanego klucza - nie koniecznie musi być bezpośrednim potomkiem węzła.

Analogicznie w przypadku poprzednika.
Odpowiedz | Odpowiedz z cytatem | Cytować
Dodaj komentarz