binarne drzewo wyszukiwania (BST) jest drzewem w którym wszystkie węzły podążają za niżej wymienionymi właściwościami-
-
wartość klucza lewego podprzepędu jest mniejsza niż wartość klucza nadrzędnego (głównego) węzła.
-
wartość klucza prawej podstrony jest większa lub równa wartości klucza węzła nadrzędnego (głównego).,
tak więc BST dzieli wszystkie swoje pod-drzewa na dwa segmenty; pod-drzewo lewe i pod-drzewo prawe i może być zdefiniowane jako −
left_subtree (keys) < node (key) ≤ right_subtree (keys)
Reprezentacja
BST jest zbiorem węzłów ułożonych w sposób, w którym zachowują właściwości BST. Każdy węzeł ma klucz i powiązaną wartość. Podczas wyszukiwania pożądany klucz jest porównywany z kluczami w BST i jeśli zostanie znaleziony, zostanie pobrana powiązana wartość.,
poniżej znajduje się obrazkowa reprezentacja BST −
obserwujemy, że klucz węzła głównego (27) ma wszystkie klucze o mniejszej wartości po lewej stronie i klucze o wyższej wartości po prawej stronie.
podstawowe operacje
poniżej znajdują się podstawowe operacje drzewa −
-
Search − przeszukuje element w drzewie.
-
Insert-wstawia element w drzewie.
-
pre-order Traversal − Trawersuje drzewo w sposób przedpremierowy.
-
in-order Traversal − Trawersuje drzewo w sposób uporządkowany.,
-
Post-order Traversal − Trawersuje drzewo w sposób post-order.
węzeł
definiuje węzeł posiadający pewne dane, odwołujący się do jego lewego i prawego węzła potomnego.
struct node { int data; struct node *leftChild; struct node *rightChild;};
operacja wyszukiwania
gdy element ma być przeszukiwany, zacznij wyszukiwanie od węzła głównego. Wtedy jeżeli dane są mniejsze od wartości klucza, wyszukaj element w lewym poddrzewie. W przeciwnym razie wyszukaj element w prawym poddrzewie. Postępuj zgodnie z tym samym algorytmem dla każdego węzła.,
algorytm
operacja wstawiania
za każdym razem, gdy element ma być wstawiony, najpierw zlokalizuj jego właściwą lokalizację. Rozpocznij wyszukiwanie od węzła głównego, następnie jeśli dane są mniejsze niż wartość klucza, wyszukaj pustą lokalizację w lewym poddrzewie i wstaw dane. W przeciwnym razie wyszukaj pustą lokalizację w prawym poddrzewie i wstaw dane.