Drzewa BST, wyszukiwanie liniowe i binarne. Porównanie szybkości.

Oto wersja poprawiona tego artykułu + zastosowanie drzew.
Przepraszam za poprzedni poważny błąd.

Przedstawiam porownanie szybkosci działania przeszukiwania liniowego, binarnego (wersji rekurencyjnej i iteracyjnej) oraz wyszukiwania w drzewie BST.

Podczas badań uwzględnione zostały dwa elementy: czas wykonania algorytmu i ilość porównań potrzebnych do wyszukania elementu. Ze względu na to, że czas działania algorytmu jest niezauważalny, został on wykonany w pętli 100000 razy. Otrzymany wynika został podzielny przez ilość wywołań danego algorytmu.

Przypadek 1

Tablica złożona z 10000 elementów, wypełniona wartościami z zakresu od ?10 do 20 (niewielka rozpiętość zakresu danych wejściowych).
Szukany element to 12000 znajdujący się na ostatniej pozycji.

Wyszukiwanie w drzewie BST:
Czas: 0.0056 ms
Ilość porównań: 2

Wyszukiwanie liniowe:
Czas: 0.0871 ms
Ilość porównań: 20000

Wyszukiwanie binarne:
Czas (wersja rekurencyjna): 0.0178 ms
Ilosc porównań: 28

Czas (wersja iteracyjna): 0.0000 ms
Ilość porównań: 42

Przypadek 2

Tablica złożona z 10000 elementów, wypełniona wartościami z zakresu od ?10 do 20. Szukany element to 12000 znajdujący się w środku tablicy.

Wyszukiwanie w drzewie BST:
Czas: 0.0021 ms
Ilość porównań: 3

Wyszukiwanie liniowe:
Czas: 0.0435 ms
Ilość porównań: 10000

Wyszukiwanie binarne:
Czas (wersja rekurencyjna): 0.0179 ms
Ilosc porównań: 2

Czas (wersja iteracyjna): 0.0000 ms
Ilość porównań: 3

Przypadek 3

Tablica złożona z 10000 elementów, wypełniona wartościami z zakresu
od ?32000 do 32000 (duża rozpiętość zakresu danych wejściowych).
Szukany element to 32001 znajdujący się na ostatniej pozycji.

Wyszukiwanie w drzewie BST:
Czas: 0.0002 ms
Ilość porównań: 14

Wyszukiwanie liniowe:
Czas: 0.0871 ms
Ilość porównań: 20000

Wyszukiwanie binarne:
Czas (wersja rekurencyjna): 0.0177 ms
Ilosc porównań: 28

Czas (wersja iteracyjna): 0.0000 ms
Ilość porównań: 42

Przypadek 4

Tablica złożona z 10000 elementów, wypełniona wartościami z zakresu
od ?32000 do 32000 (duża rozpiętość zakresu danych wejściowych).
Szukany element to 32001 znajdujący się w środku tablicy.

Wyszukiwanie w drzewie BST:
Czas: 0.0002 ms
Ilość porównań: 13

Wyszukiwanie liniowe:
Czas: 0.0435 ms
Ilość porównań: 10000

Wyszukiwanie binarne:
Czas (wersja rekurencyjna): 0.0174 ms
Ilosc porównań: 2

Czas (wersja iteracyjna): 0.0000 ms
Ilość porównań: 3

Przypadek 5

Tablica złożona z 10000 elementów, wypełniona jednakowymi elementami o wartości 1.
Szukany element to 2 znajdujący się na ostatniej pozycji.

Wyszukiwanie w drzewie BST:
Czas: 0.0001 ms
Ilość porównań: 2

Wyszukiwanie liniowe:
Czas: 0.0870 ms
Ilość porównań: 20000

Wyszukiwanie binarne:
Czas (wersja rekurencyjna): 0.0123 ms
Ilosc porównań: 28

Czas (wersja iteracyjna): 0.0000 ms
Ilość porównań: 42

Przypadek 6

Tablica złożona z 10000 elementów, wypełniona jednakowymi elementami o wartości 1.
Szukany element to 2 znajdujący się w środku.

Wyszukiwanie w drzewie BST:
Czas: 0.0000 ms
Ilość porównań: 2

Wyszukiwanie liniowe:
Czas: 0.0433 ms
Ilość porównań: 10000

Wyszukiwanie binarne:
Czas (wersja rekurencyjna): 0.0119 ms
Ilosc porównań: 2

Czas (wersja iteracyjna): 0.0000 ms
Ilość porównań: 3

---

Implementacja operacji wykonywanych na drzewach BST (binary search tree - binarne drzewa poszukiwac).

#include <stdio.h>
#include "table.h"
#include <time.h>

#define N 10000 //liczba elementow tablicy wczytywanej z pliku i rozmieszczanej w drzewie BST

typedef struct BST{
  int data;
  struct BST *left;
  struct BST *right;
} bst;

bst *create(int data); //przydzielenie pamieci dla nowego wezla 
bst *insert(bst *root, bst *new); //wstawianie wezla do drzewa
void ShowTree(bst *root); //wyswietlenie calego drzewa w porzadku InOrder
bst *search(bst *root, int data, unsigned long *l_por); //wyzukiwanie wezla o podanym kluczu
bst *min(bst *root); //wyszukiwanie elementu najmniejszego 
bst *max(bst *root); //wyszukiwanie elementu najwiekszego
bst *delete(bst *root, int data); //usuniecie wezla z drzewa
bst *succ(bst *root, int data); //nastepnik 
bst *pred(bst *root, int data); //poprzednik
bst *parent(bst *root, bst *syn); //wyznacza adres rodzica syna 'syn'

int main(void)
{
  bst *root, *new, *s;
  int tab[N];
  long i;
  clock_t start, stop;
  float alg_time;
  unsigned long l_porownan = 0;

  root = NULL;
/*  OpenTable("tab.dat",tab,N);
  tab[(N/2)-1] = 32001;
  for (i = 0; i < N; ++i) 
    root = insert(root,create(tab[i]));
  ShowTree(root);
  start = clock();
//  for (i = 0; i < 100000; ++i)
    s = search(root,32001,&l_porownan);
  stop = clock();
  alg_time = (stop - start) / CLK_TCK;
  alg_time /= 10000;
  printf("\nszukany el.: %d\n", s->data);
  printf("\nCzas wykonania alg...: %f\n", alg_time);
  printf("\nLiczba wykonanych porownan: %lu\n", l_porownan);*/
  ShowTree(root);
  return 0;
}

/********************************************************************************
 * Funkcja przydziela pamiec na nowy element i wypelnia go podanymi danymi	*
 * Zwraca natomiast adres nowego elementu					*
 * data - jakies dane, mozna to traktowac jak klucz				*
 *******************************************************************************/
bst *create(int data) 
{
  bst *tmp; //pomocniczy wskaznik, przechowuje adres pamieci przydzielnej dla nowego elementu

  tmp = (bst *) malloc(sizeof(*tmp));
  if (tmp == NULL) {
    printf("\nBrak wolnej pamieci ...\n");
    return NULL;	
  }
  tmp->data = data;
  tmp->right = NULL;
  tmp->left = NULL;
  return tmp;
}

/********************************************************
 * Funkcja wstawia element do drzewa			*
 * Zwraca adres na korzen nowego drzewa			*
 * root - wskaznik na korzen drzewa			*
 * new - wskaznik na dodawanay element			*
 *******************************************************/
bst *insert(bst *root, bst *new)
{
  bst *tmp;
  bst *ret = root; //przechowuj adres korzenia aby nie zmienic wskaznika na poczatek drzewa
	
  if (root == NULL) 
    return new;
  else 
    while (root != NULL) {
      tmp = root;
      if (root->data >= new->data)
        root = root->left;
      else
        root = root->right;
    }
  if (tmp->data >= new->data)
    tmp->left = new;
  else
    tmp->right = new;
  return ret; 
}

/********************************************************
 * Funckcja wyswietla cale drzewo w porzadku InOrder	*
 * root - wskaznik na korzen drzewa			*
 *******************************************************/
void ShowTree(bst *root)
{
  if (root == NULL) 
    return;
  ShowTree(root->left);
  printf("\n%d\n", root->data);
  ShowTree(root->right);
  return;	
}

/************************************************************************
 * Funckja wyszukuje w drzewie elementu o podanej wartosci lub kluczu	*
 * Zwraca adres tego elementu						*
 * root - wskaznik na korzen drzewa					*
 * data - dane lub klucz						*
 * l_por - liczba wykonanych porownan w trkacie wyszukiwania		*
 ***********************************************************************/
bst *search(bst *root, int data, unsigned long *l_por)
{
  if (root == NULL || data == root->data) {
    *l_por += 1;
    return root;
  }
  *l_por += 1; 
  if (data < root->data)  
    return search(root->left,data,l_por);
  else
    return search(root->right,data,l_por);
}

/****************************************************************
 * Funkcja znajduje w drzewie element o najmniejszym kluczu	*
 * Zwraca adres tego elementu					*
 * root - wskaznik na korzen					*
 ***************************************************************/
bst *min(bst *root)
{
  while (root->left != NULL)
    root = root->left;
  return root;
}

/****************************************************************
 * Funckja znaduje w drzewie element o najwiekszym kluczu	*
 * Zwraca adres tego elementu					*
 * root - wskaznik na korzen					*
 ***************************************************************/
bst *max(bst *root)
{
  while (root->right != NULL)
    root = root->right;
  return root;
}

/****************************************************************
 * Funckja usuwa z drzewa wezel o podanym kluczu		*
 * Zwraca adres wstawionego elementu na miejsce usunietego 	*
 * root - wskaznik na korzen					*
 * data - dane lub klucz usuwanego elementu			*
 ***************************************************************/
bst *delete(bst *root, int data)
{
  bst *del; //adres elementu do usuniecia
  bst *x, *y; //pomocnicze wskazniki
  unsigned long l = 0;
  bst *parent_x, *parent_y; //wskazniki na rodzicow

  del = search(root,data,&l);
  if (del->left == NULL || del->right == NULL) //przypadek pierwszy
    y = del;
  else
    y = succ(root,del->data);
  if (y->left != NULL) //przypadek drugi
    x = y->left;
  else
    x = y->right;
  if (x != NULL) {
    parent_x = parent(root,x);
    parent_y = parent(root,y);
    parent_x = parent_y;
  }
  if (parent(root,y) == NULL)
    root = x;
  else if (y == parent(root,y)->left)
    (parent(root,y)->left) = x;
  else
    (parent(root,y)->right) = x;
  if (y != del)
    del->data = y->data;
  return y;
}

/********************************************************************************
 * Funkcja wyznaczajaca nastepnika danego elementu				*
 * Zwraca adres tego elementu							*
 * root - wskaznik na drzewo							*
 * data - klucz lub dane elementu ktorego nastepnika bedziemy wyznaczac		*
 *******************************************************************************/
bst *succ(bst *root, int data)
{
  bst *x, *y;
  unsigned long l = 0;

  x = search(root,data,&l);
  if (x->right != NULL)
    return min(x->right);
  y = parent(root,x);
  while (y != NULL && x == y->right) {
    x = y;
    y = parent(root,y);
  }
  return y;
}

/********************************************************************************
 * Funckja wyznaczajaca poprzednika danego elementu				*
 * Zwraca adres na ten element							*
 * root - wskaznik na korzen							*	
 * data - dane lub klucz elementu, ktorego porzednika bedziemy wyznaczac	*
 *******************************************************************************/
bst *pred(bst *root, int data)
{
  bst *x, *y;
  unsigned long l = 0;

  x = search(root,data,&l);
  if (x->left != NULL)
    return min(x->left);
  y = parent(root,x);
  while (y != NULL &&  x == y->left) {
    x = y;
    y = parent(root,y);
  }
  return y;
}

/********************************************************
 * Funkcja wyznaczajaca rodzica danego elementu		*
 * Zwraca adres do rodzica				*
 * root - wskaznik na drzewo				*
 * syn - element ktorego rodzica bedziemy wyznaczac	*
 *******************************************************/
bst *parent(bst *root, bst *syn)
{
  bst *tmp;
  
  while (root != syn) {
    tmp = root;
    if (root->data >= syn->data)
      root = root->left;
    else
      root = root->right;
  }
  return tmp;
}

Wyszukiwanie liniowe:

#include <stdio.h>
#include <time.h>
#include "table.h"
#include <time.h>

#define N 10000 //liczba elementow tablicy 

long search(int tab[], long size, int x, unsigned long *l_por);

int main(void)
{
  int tab[N], x = 2, i; //x - szukany element
  clock_t start, stop;
  float alg_time;
  long indeks;
  unsigned long l_porownan = 0;

  OpenTable("tab.dat",tab,N);
  PrintTable(tab,N,col);
  tab[N-1] = x; //ustawiam szukany element na srodku tablicy, zeby zbadac rozne przypadki
  start = clock(); //odczytanie aktualnego czasu
  /* 
   * zbadanie czasu wykonania odbywa sie w petli (trzeba usunac komentarz)
   * jesli chcemy zbadac ilosc wykonanych porownan trzeba usunac petle czyli dac jako komentarz
  */
//  for (i = 0; i < 100000; ++i) 
    indeks = search(tab,N,x,&l_porownan);
  stop = clock(); //odczytanie czasu po wykonaniu algorytmu
  alg_time = (stop - start) / CLK_TCK; //obliczenie czasu
  alg_time /= 10000; //czas w sekundach
  printf("\nIndeks szukanego elementu: %d\n", indeks);
  printf("\nCzas wykonywania algorytmu: %f\n", alg_time);
  printf("\nLiczba wykonanych porownan: %lu\n", l_porownan);
}

/*************************************************************
 * funkcja wyszukuje w tablicy indeks elementu x             *
 * tab[] - wksaznik do pierwszego elementu tablicy           *
 * x - szukany element                                       *
 * *l_por - wskaznik do elementu przechowujacego liczbe      *
 *          wykonanych porownan				     *
 ************************************************************/
long search(int tab[], long size, int x, unsigned long *l_por)
{
  long i;

  for (i = 0; i < size; ++i) { //jedno porownanie - i < size
    *l_por += 2;
    if (tab[i] == x) //drugie porownanie
      return i;
  }
}

Wyszukiwanie binarne:

#include <stdio.h>
#include "table.h"
#include <time.h>

#define N 10000 //liczba elementow w tablicy

int searchrek(int *ptab, int l, int p, int x, unsigned long *l_por); //wyszukiwanie rekurencyjnie
int searchiter(int *ptab, int l, int p, int x, unsigned long *l_por); //wyszukiwanie iteracyjnie
void zamien(int *l, int *p); //zamiana miejscami dwoch elementow
void sort(int *ptab); //sortowanie tablicy (ustawienie elementow niemalejaco)

int main(void)
{
  int tab[N], *ptab = tab, x = 2, indeks;
  clock_t start, stop;
  float alg_time;
  long i;
  unsigned long l_porownan = 0;

  OpenTable("tab.dat",tab,N); //wczytanie tablicy z pliku
  tab[N-1] = x; //ustawienie szukanego elementu
  sort(tab); //posotowanie tablicy
  start = clock();
  //for (i = 0; i < 100000; ++i)
    indeks = searchrek(ptab,0,N-1,x,&l_porownan);
  printf("\nans = %d\n", indeks);
  stop = clock();
  alg_time = (stop - start) / CLK_TCK;
  alg_time /= 10000;
  printf("\nTime rec.: %f\n", alg_time);
  printf("\nLiczba wykonanych porownan: %lu\n", l_porownan);
  start = clock();
  //for (i = 0; i < 100000; ++i)
    indeks = searchiter(ptab,0,N-1,x,&l_porownan);
  printf("\nans = %d\n", indeks);
  stop = clock();
  alg_time = (stop - start) / CLK_TCK;
  alg_time /= 10000;
  printf("\nTime iter.: %f\n", alg_time);
  printf("\nLiczba wykonancyh porownan: %lu\n", l_porownan);
  return 0;
}

int searchrek(int *ptab, int l, int p, int x, unsigned long *l_por)
{
  int m;

  *l_por += 1;
  if (l > p)
    return -1;
  m = (l+p) / 2;
  *l_por += 1;
  if (x == *(ptab+m))
    return m;
  else if (x < *(ptab+m)) {
    *l_por += 1; 
    return searchrek(ptab,l,m-1,x,l_por);
  }
  else
    return searchrek(ptab,m+1,p,x,l_por);
}

void zamien(int *l, int *p)
{
  int tmp;

  tmp = *l;
  *l = *p;
  *p = tmp;
}

void sort(int *ptab)
{
  int i, j;

  for (i = 0; i < N-1; ++i)
    for (j = 0; j < N-1; ++j)
      if (*(ptab+j) > *(ptab+(j+1)))
        zamien(ptab+j,ptab+(j+1));
}

int searchiter(int *ptab, int l, int p, int x, unsigned long *l_por)
{
  int m;

  m = (l+p) / 2;

  while (l <= p && x != *(ptab+m)) {
    *l_por += 1;
    if (x < *(ptab+m)) {
      *l_por += 1;
      p = m - 1;
    }
    else
      l = m + 1;
    m = (l+p) / 2;
  }
  *l_por += 1;
  if (x == *(ptab+m))
    return m;
  else
    return -1;
}

Z otrzymanych wyników od razu można zauważyć słabość przeszukiwania liniowego. Widać, że jest to najwolniejszy algorytm i w swoim działaniu wykonuje największą liczbę porównań. Podczas takiego przeszukiwania porównujemy każdy element z szukanym i nie mamy tutaj żadnej struktury posiadającej pewne własności dzięki, którym wyszukiwanie mogłoby odbywać się w krótszym czasie i wymagałoby mniej porównań. Jednak jest to algorytm prosty i szybki w implementacji. Kiedy mamy problem, w którym operujemy niewielką ilością danych lepiej wybrać prosty i szybki do napisania algorytm. Nikt chyba nie tworzyłby specjalnie drzewa BST dla 100 elementów i wykonywał operacje wyszukiwania w tym drzewie. Przeszukiwanie liniowe dobrze jest również stosować wtedy gdy nie mamy żadnych informacji na temat struktury przeszukiwanych danych lub ich składowaniu w pamięci. Algorytm ten jest klasy O(n) ? [1]. Czas trwania algorytmu i ilość porównań zmieniają się w sposób liniowy. Jeżeli umieścimy szukany element na środku tablicy to ilość porównań i czas będą dwa razy mniejsze niż w przypadku gdy element znajdowałby się na końcu tablicy, co widać z otrzymanych wyników. Widać również, że algorytm wyszukiwania liniowego jest niezależny na dane tzn. zakres wartości, czy częste powtarzanie się elementów.
W przypadku wyszukiwania binarnego od razu możemy stwierdzić, że wersja rekurencyjna jest wolniejsza pod względem czasowym od wersji iteracyjnej. Fakt ten wynika z ?właściwości rekurencji? (konieczność odstawiania na stos przy każdym wywołaniu funkcji pewnych informacji pozwalających wrócić do poprzedniego stanu, tzw. ramka stosu. Jednak wersja iteracyjna wymaga większej ilości porównań. Wynika to z derekursywacji rekurencji, co jest związane z zastosowaniem pętli, a co za tym idzie większej liczby porównań. Jeżeli szukany element znajduje się w środku tablicy to od razu go znajdujemy i algorytm wykonuje minimalną dla tego przypadku liczbę porównań. Algorytm ten jest klasy O(log2N) = [2], a o jego sile może świadczyć fakt, że dla N równego miliard, liczba porównań w przypadku pesymistycznym wynosi log2N = 30. W naszych wynikach widać również algorytm ten nie jest odporny na zakres wartości.
Jeżeli spojrzymy na wyniki otrzymane dla drzew BST to od razu widać, że algorytm wyszukiwania w drzewach BST jest najlepszy. Nie wynika to do końca z faktu tego algorytmu, ale ze struktury danych jaką tworzą drzewa. Poprzez odpowiednie ustawienie elementów mamy szybki dostęp do szukanego elementu przy najmniejszej liczbie porównań w porównaniu do pozostałych algorytmów. Wynika to z faktu, że elementy mniejsze znajdują się na lewo od swojego rodzica, a większe na prawo. Dlatego też można zauważyć, że w przypadku drzew duże znaczenie mają dane wejściowe, a mianowicie ich zakres i częstość występowania. Od razu widać, że im większy zakres tym szybciej znajdujemy nasz element bo od razu odrzucamy pewną część danych. W przypadku gdy nasze wartości są z wąskiego zakresu wówczas część naszego drzewa może przeobrazić się w listę. Dlatego stosuje się pewne odmiany drzew (np. drzewa czerwono ? czarne). Podstawowe operacje na drzewach wymagają czasu proporcjonalnego do wysokości drzewa ? [3]. W drzewie binarnym o n węzłach operacje takie w przypadku pesymistycznym działają w czasie ?(lg n).
Podsumowując wyszukiwanie w drzewach BST jest najszybsze i wymaga najmniejszej ilości porównań do znalezienia naszego elementu.
Drzewa BST mają szerokie zastosowanie - [1]:

Reprezentowanie wyrażeń arytmetycznych ? [1]: element drzewa oprócz standardowych wskaźników posiada dwa pola ? operatora i danych. Po napisaniu odpowiednich funkcji obsługujących taką strukturę można wyrazić dowolnie skomplikowane wyrażenie arytmetyczne oraz wykonywać różne operacje jak np. różniczkowanie.
USS ? Uniwersalna Struktura Słownikowa ? [1]: funkcje sprawdzające poprawność ortograficzną wprowadzanych informacji (arkusze kalkulacyjne, edytory tekstu).
Drzewa pozycyjne ? [3]: do reprezentowanie wszystkich możliwych kombinacji funkcji logicznej i jej minimalizacji

1. Literatura:

[1] ? P. Wróblewski, Algorytmy struktury danych i techniki programowani, Helion 2003
[2] ? D. Harel, Rzecz o istocie informatyki, WNT 2001
[3] ? T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Wprowadzenie do algorytmów, WNT 2004