Proste zastosowania drzew BST


Tematy pokrewne   Podrozdziały
Drzewa
Podstawowe pojęcia dotyczące drzew
Przechodzenie drzew binarnych – DFS: pre-order, in-order, post-order
Przechodzenie drzew binarnych – BFS
Badanie drzewa binarnego
Prezentacja drzew binarnych
Kopiec
Drzewa wyrażeń
Drzewa poszukiwań binarnych – BST
Tworzenie drzewa BST
Równoważenie drzewa BST – algorytm DSW
Proste zastosowania drzew BST
Drzewa AVL
Drzewa Splay
Drzewa Czerwono-Czarne
Kompresja Huffmana
Zbiory rozłączne – implementacja za pomocą drzew
  Sortowanie
Kolejka priorytetowa

Drzewa BST (ang. Binary Search Tree – Drzewo Poszukiwań Binarnych) są zwykle stosowane w aplikacjach, gdzie należy szybko wyszukiwać różne dane. Dobrze skonstruowane drzewo BST pozwala znaleźć dane w czasie O(log n). Oczywiście podobny czas uzyskamy stosując tablicę i algorytm wyszukiwania binarnego, jednakże tablice nie pozwalają na łatwe dołączanie i usuwanie elementów, ponieważ zajmują ciągły blok pamięci (wstawienie nowego elementu wymaga rozsunięcia elementów tablicy, co zajmuje czas). Drzewo BST jest natomiast strukturą dynamiczną, w której można tworzyć i usuwać efektywnie elementy.

Poniżej podajemy kilka wybranych zastosowań drzew BST.

 

Sortowanie

Drzewo BST można wykorzystać do stworzenia prostego algorytmu sortującego. Działa on w dwóch krokach. Najpierw z danych wejściowych budujemy odpowiednie drzewo BST (dane nie powinny być w żaden sposób uporządkowane, inaczej otrzymamy zdegenerowane drzewo BST i efektywność sortowania spadnie). Następnie drzewo przechodzimy algorytmem inorder i wyprowadzamy na wyjście dane przechowywane w odwiedzanych węzłach. Dane te będą uporządkowane rosnąco.

 

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program odczytuje z wejścia liczbę n, a następnie n liczb. Z odczytanych liczb tworzy drzewo BST. Utworzone drzewo przechodzi algorytmem inorder, wypisując na wyjście klucze kolejno odwiedzanych węzłów.

Przykładowe dane:

29
14 23 16 27 24 17 10 2 29 5 22 7 25 1 11 13 8 15 21 6 9 26 19 28 3 20 12 18 4

 

Lazarus
// Sortowanie BST
// Data: 5.05.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program bst;

// Typ węzłów drzewa BST
//----------------------
type
  PBSTNode = ^BSTNode;
  BSTNode  = record
    left,right : PBSTNode;
    key   : integer;
  end;

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
procedure DFSRelease(v : PBSTNode);
begin
  if v <> nil then
  begin
    DFSRelease(v^.left);   // usuwamy lewe poddrzewo
    DFSRelease(v^.right);  // usuwamy prawe poddrzewo
    dispose(v);            // usuwamy sam węzeł
  end;
end;

// Procedura wstawia do drzewa BST węzeł o kluczu k
//-------------------------------------------------
procedure insertBST(var root : PBSTNode; k : integer);
var
  w,p : PBSTNode;
begin

  new(w);                // Tworzymy dynamicznie nowy węzeł

  w^.left  := nil;       // Zerujemy wskazania synów
  w^.right := nil;
  w^.key := k;           // Wstawiamy klucz

  p := root;             // Wyszukujemy miejsce dla w, rozpoczynając od korzenia

  if p = nil then        // Drzewo puste?
    root := w            // Jeśli tak, to w staje się korzeniem
  else
    while true do        // Pętla nieskończona
      if k < p^.key then // W zależności od klucza idziemy do lewego lub
      begin              // prawego syna, o ile takowy istnieje 
        if p^.left = nil then // Jeśli lewego syna nie ma,
        begin
          p^.left := w;  // to w staje się lewym synem
          break;         // Przerywamy pętlę while
        end
        else p := p^.left;
      end
      else
      begin
        if p^.right = nil then // Jeśli prawego syna nie ma,
        begin
          p^.right := w;  // to w staje się prawym synem
          break;          // Przerywamy pętlę while
        end
        else p := p^.right;
      end;
end;

// Rekurencyjna procedura inorder
//-------------------------------
procedure inorderBST(v : PBSTNode);
begin
  if v <> nil then
  begin
    inorderBST(v^.left);   // przechodzimy lewe poddrzewo
    write(v^.key,' ');     // odwiedzamy węzeł
    inorderBST(v^.right);  // przechodzimy prawe poddrzewo
  end;
end;

//**********************
//*** PROGRAM GŁÓWNY ***
//**********************

var
  i,n,x : integer;
  root  : PBSTNode;     // korzeń drzewa BST

begin

  root := nil;          // Tworzymy puste drzewo BST

  read(n);              // Czytamy liczbę elementów

  for i := 1 to n do
  begin
    read(x);            // Czytamy kolejne elementy
    insertBST(root,x);  // i umieszczamy je w drzewie BST
  end;

  writeln;

  inorderBST(root);     // Przechodzimy drzewo algorytmem inorder

  DFSRelease(root);     // Usuwamy drzewo BST z pamięci

end.
Code::Blocks
// Sortowanie BST
// Data: 5.05.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>

using namespace std;

// Typ węzłów drzewa BST

struct BSTNode
{
  BSTNode * left, * right;
  int key;
};

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
void DFSRelease(BSTNode * v)
{
  if(v)
  {
    DFSRelease(v->left);   // usuwamy lewe poddrzewo
    DFSRelease(v->right);  // usuwamy prawe poddrzewo
    delete v;              // usuwamy sam węzeł
  }
}

// Procedura wstawia do drzewa BST węzeł o kluczu k
//-------------------------------------------------
void insertBST(BSTNode * & root, int k)
{
  BSTNode * w, * p;

  w = new BSTNode;           // Tworzymy dynamicznie nowy węzeł

  w->left = w->right = NULL; // Zerujemy wskazania synów
  w->key = k;                // Wstawiamy klucz

  p = root;                  // Wyszukujemy miejsce dla w, rozpoczynając od korzenia

  if(!p)                     // Drzewo puste?
    root = w;                // Jeśli tak, to w staje się korzeniem
  else
    while(true)              // Pętla nieskończona
      if(k < p->key)         // W zależności od klucza idziemy do lewego lub
      {                      // prawego syna, o ile takowy istnieje
        if(!p->left)         // Jeśli lewego syna nie ma,
        {
          p->left = w;       // to węzeł w staje się lewym synem
          break;             // Przerywamy pętlę while
        }
        else p = p->left;
      }
      else
      {
        if(!p->right)        // Jeśli prawego syna nie ma,
        {
          p->right = w;      // to węzeł w staje się prawym synem
          break;             // Przerywamy pętlę while
        }
        else p = p->right;
      }
}

// Rekurencyjna procedura inorder
//-------------------------------
void inorderBST(BSTNode * v)
{
  if(v)
  {
    inorderBST(v->left);   // przechodzimy lewe poddrzewo
    cout << v->key << " "; // odwiedzamy węzeł
    inorderBST(v->right);  // przechodzimy prawe poddrzewo
  }
}

// **********************
// *** PROGRAM GŁÓWNY ***
// **********************

int main()
{
  int i,n,x;
  BSTNode * root = NULL;// korzeń drzewa BST

  cin >> n;             // Czytamy liczbę elementów

  for(i = 0; i < n; i++)
  {
    cin >> x;           // Czytamy kolejne elementy
    insertBST(root,x);  // i umieszczamy je w drzewie BST
  }

  cout << endl;

  inorderBST(root);     // Przechodzimy drzewo algorytmem inorder

  DFSRelease(root);     // Usuwamy drzewo BST z pamięci

  return 0;
}
Free Basic
' Sortowanie BST
' Data: 5.05.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

' Typ węzłów drzewa BST

Type BSTNode
  Left As BSTNode Ptr
  Right As BSTNode Ptr
  key As Integer
End Type

' Procedura DFS:postorder usuwająca drzewo
'-----------------------------------------
Sub DFSRelease(v As BSTNode Ptr)
  If v Then
    DFSRelease(v->left)   ' usuwamy lewe poddrzewo
    DFSRelease(v->right)  ' usuwamy prawe poddrzewo
    delete v              ' usuwamy sam węzeł
  End If
End Sub

' Procedura wstawia do drzewa BST węzeł o kluczu k
'-------------------------------------------------
Sub insertBST(ByRef root As BSTNode Ptr, k As Integer)
	
  Dim As BSTNode Ptr w, p

  w = new BSTNode           ' Tworzymy dynamicznie nowy węzeł

  w->left  = 0              ' Zerujemy wskazania synów
  w->right = 0
  w->key = k                ' Wstawiamy klucz

  p = root                  ' Wyszukujemy miejsce dla w, rozpoczynając od korzenia

  If p = 0 Then             ' Drzewo puste?
    root = w                ' Jeśli tak, to w staje się korzeniem
  Else
    Do                      ' Pętla nieskończona
      If k < p->key Then    ' W zależności od klucza idziemy do lewego lub
                            ' prawego syna, o ile takowy istnieje
        If p->Left = 0 Then ' Jeśli lewego syna nie ma,
          p->left = w       ' to węzeł w staje się lewym synem
          Exit Do           ' Przerywamy pętlę
        Else
          p = p->Left
        End If
      Else
        If p->Right = 0 Then' Jeśli prawego syna nie ma,
          p->right = w      ' to węzeł w staje się prawym synem
          Exit Do           ' Przerywamy pętlę
        Else
          p = p->Right
        End If
      End If
    Loop                    ' Koniec pętli
  End If
End Sub

' Rekurencyjna procedura inorder
'-------------------------------
Sub inorderBST(v As BSTNode Ptr)
  If v  Then
    inorderBST(v->left)   ' przechodzimy lewe poddrzewo
    print v->key;         ' odwiedzamy węzeł
    inorderBST(v->right)  ' przechodzimy prawe poddrzewo
  End If
End Sub

' **********************
' *** PROGRAM GŁÓWNY ***
' **********************

Dim As Integer i,n,x
Dim As BSTNode Ptr root = 0 ' korzeń drzewa BST

Open Cons For Input As #1

Input #1,n              ' Czytamy liczbę elementów

For i = 1 To n
  Input #1,x            ' Czytamy kolejne elementy
  insertBST(root,x)     ' i umieszczamy je w drzewie BST
Next

Close #1

Print

inorderBST(root)        ' Przechodzimy drzewo algorytmem inorder

DFSRelease(root)        ' Usuwamy drzewo BST z pamięci

End
Wynik
29
14 23 16 27 24 17 10 2 29 5 22 7 25 1 11 13 8 15 21 6 9 26 19 28 3 20 12 18 4

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29

 

Kolejka priorytetowa

Kolejka priorytetowa (ang. priority queue) jest strukturą danych, w której umieszczone dane posiadają priorytet. Odczyt danych z kolejki zawsze wykonywany jest wg najwyższego priorytetu. Istnieje wiele różnych implementacji kolejek priorytetowych. Możemy je oprzeć na drzewie BST. Dane do drzewa BST wprowadzamy w normalny sposób. Natomiast wyprowadzamy zawsze największy węzeł. Kolejkę zrealizujemy w postaci obiektu. W rzeczywistej implementacji należałoby zadbać o równoważenie drzewa BST – np. można zliczać węzły oraz mierzyć wysokość drzewa przy wstawianiu nowego elementu i jeśli przekroczy ona znacznie wartość log2n, dokonać zrównoważenia algorytmem DSW, albo po prostu dokonywać zrównoważenia po wstawieniu lub usunięciu zadanej liczby elementów. U nas tę opcję pominiemy, pozostawiając ją zdolniejszym czytelnikom.

Program

Ważne:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

 

Program tworzy 10 elementów o losowych priorytetach i umieszcza je w kolejce, po czym odczytuje zawartość kolejki i wyświetla ją w oknie konsoli.

 

Lazarus
// Kolejka priorytetowa oparta na drzewie BST
// Data: 11.05.2013
// (C)2012 mgr Jerzy Wałaszek
//------------------------------

program prioqueue;

// Definicja typu węzłów drzewa
//-------------------------------

// Typ węzłów drzewa BST
//----------------------
type
  PBSTNode = ^BSTNode;
  BSTNode  = record
    up,left,right : PBSTNode;
    key : integer;     // Klucz jest priorytetem
    data : integer;    // Dane przechowywane przez węzeł
  end;

// Definicja typu obiektowego queue
//---------------------------------
  queue = object
    private
      root : PBSTNode;    // Korzeń drzewa BST

    public
      constructor init;
      destructor destroy;
      function empty : boolean;
      function front : integer;
      function frontprio: integer;
      procedure push(prio,v : integer);
      procedure pop;
  end;

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
constructor queue.init;
begin
  root := nil;
end;

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
procedure DFSRelease(v : PBSTNode);
begin
  if v <> nil then
  begin
    DFSRelease(v^.left);   // usuwamy lewe poddrzewo
    DFSRelease(v^.right);  // usuwamy prawe poddrzewo
    dispose(v);            // usuwamy sam węzeł
  end
end;

// Destruktor - usuwa listę z pamięci
//-----------------------------------
destructor queue.destroy;
begin
  DFSRelease(root);
end;

// Sprawdza, czy kolejka jest pusta
//---------------------------------
function queue.empty : boolean;
begin
  empty := root = nil;
end;

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
function queue.front : integer;
var
  p : PBSTNode;
begin
  if root <> nil then             // Jeśli drzewo nie jest puste,
  begin                           // to szukamy największego elementu
    p := root;
    while p^.right <> nil do
      p := p^.right;

    front := p^.data;             // i zwracamy jego wartość

  end

  else front := -MAXINT;          // inaczej zwracamy wartość specjalną

end;

// Zwraca priorytet pierwszego elementu
//-------------------------------------
function queue.frontprio : integer;
var
  p : PBSTNode;
begin
  if root <> nil then            // Jeśli drzewo nie jest puste,
  begin                          // to szukamy największego elementu
    p := root;
    while p^.right <> nil do
      p := p^.right;
    frontprio := p^.key;         // i zwracamy jego priorytet, czyli klucz
  end
  else frontprio := -MAXINT;     // inaczej zwracamy wartość specjalną

end;

// Zapisuje do kolejki
//--------------------
procedure queue.push(prio,v : integer);
var
  w,p : PBSTNode;
begin

  new(w);                      // Tworzymy dynamicznie nowy węzeł

  w^.left  := nil;             // Zerujemy wskazania synów
  w^.right := nil;
  w^.key   := prio;            // Wstawiamy priorytet
  w^.data  := v;               // Wstawiamy dane

  p := root;                   // Wyszukujemy miejsce dla w, rozpoczynając od korzenia

  if p = nil then              // Drzewo puste?
    root := w                  // Jeśli tak, to w staje się korzeniem
  else
    while true do              // Pętla nieskończona
      if prio < p^.key then    // W zależności od klucza idziemy do lewego lub
      begin                    // prawego syna, o ile takowy istnieje
        if p^.left = nil then  // Jeśli lewego syna nie ma,
        begin
          p^.left := w;        // to w staje się lewym synem
          break;               // Przerywamy pętlę while
        end
        else p := p^.left;
      end
      else
      begin
        if p^.right = nil then // Jeśli prawego syna nie ma,
        begin
          p^.right := w;       // to w staje się prawym synem
          break;               // Przerywamy pętlę while
        end
        else p := p^.right;
      end;

  w^.up   := p;     // Ojcem w jest zawsze p
end;

// Usuwa z kolejki
//----------------
procedure queue.pop;
var
  p : PBSTNode;
begin
  if root <> nil then         // Jeśli drzewo BST nie jest puste,
  begin                       // to szukamy największego elementu
    p := root;
    while p^.right <> nil do
      p := p^.right;

// Jeśli element ma lewego syna, to jego ojcem stanie się ojciec elementu

    if p^.left <> nil then p^.left^.up := p^.up;

// Jeśli element ma ojca, to jego prawym synem stanie sie lewy syn elementu

    if p^.up <> nil then p^.up^.right := p^.left
    else  root := p^.left;   // inaczej uaktualniamy korzeń drzewa

    dispose(p);              // zwalniamy pamięć

  end
end;

//---------------
// Program główny
//---------------

var
  Q : queue;   // kolejka
  i,p,v : integer;

begin
  randomize;                 // Inicjujemy generator pseudolosowy

  Q.init;                    // Inicjujemy kolejkę priorytetową

  for i := 1 to 10 do        // Wstawiamy do kolejki 10 elementów
  begin                      // o różnych priorytetach.
    v := random(100);
    p := random(10);
    writeln(v:2,':',p);
    Q.push(p,v);
  end;

  writeln('----');

  while not Q.empty do       // Pobieramy z kolejki kolejne elementy
  begin
    writeln(Q.front:2,':',Q.frontprio); // Wypisujemy ich zawartość
    Q.pop;                   // i usuwamy z kolejki
  end;

  Q.destroy;

end.
Code::Blocks
// Kolejka priorytetowa oparta na drzewie BST
// Data: 11.05.2013
// (C)2012 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <iomanip>
#include <cstdlib>
#include <ctime>

using namespace std;

const int MAXINT = 2147483647;

// Definicja typu węzłów drzewa
//-------------------------------

// Typ węzłów drzewa BST
//----------------------

struct BSTNode
{
  BSTNode * up, * left, * right;
  int key;     // Klucz jest priorytetem
  int data;    // Dane przechowywane przez węzeł
};

// Definicja typu obiektowego queue
//---------------------------------
class queue
{
  private:
    BSTNode * root;    // Korzeń drzewa BST

  public:
    queue();
    ~queue();
    bool empty();
    int front();
    int frontprio();
    void push(int prio, int v);
    void pop();
};

//---------------------
// Metody obiektu queue
//---------------------

// Konstruktor - tworzy pustą listę
//---------------------------------
queue::queue()
{
  root = NULL;
}

// Procedura DFS:postorder usuwająca drzewo
//-----------------------------------------
void DFSRelease(BSTNode * v)
{
  if(v)
  {
    DFSRelease(v->left);   // usuwamy lewe poddrzewo
    DFSRelease(v->right);  // usuwamy prawe poddrzewo
    delete v;              // usuwamy sam węzeł
  }
}

// Destruktor - usuwa listę z pamięci
//-----------------------------------
queue::~queue()
{
  DFSRelease(root);
}

// Sprawdza, czy kolejka jest pusta
//---------------------------------
bool queue::empty()
{
  return !root;
}

// Zwraca początek kolejki.
// Wartość specjalna to -MAXINT
//-----------------------------
int queue::front()
{
  BSTNode * p;

  if(root)                        // Jeśli drzewo nie jest puste,
  {                               // to szukamy największego elementu
    for(p = root; p->right; p = p->right) ;

    return p->data;               // i zwracamy jego wartość
  }
  else return -MAXINT;          // inaczej zwracamy wartość specjalną
}

// Zwraca priorytet pierwszego elementu
//-------------------------------------
int queue::frontprio()
{
  BSTNode * p;

  if(root)                       // Jeśli drzewo nie jest puste,
  {                              // to szukamy największego elementu
    for(p = root; p->right; p = p->right) ;

    return p->key;               // i zwracamy jego priorytet, czyli klucz
  }
  else return -MAXINT;           // inaczej zwracamy wartość specjalną
}

// Zapisuje do kolejki
//--------------------
void queue::push(int prio, int v)
{
  BSTNode * w, * p;

  w = new BSTNode;             // Tworzymy dynamicznie nowy węzeł

  w->left  =  w->right = NULL; // Zerujemy wskazania synów
  w->key  = prio;              // Wstawiamy priorytet
  w->data = v;                 // Wstawiamy dane

  p = root;                    // Wyszukujemy miejsce dla w, rozpoczynając od korzenia

  if(!p)                       // Drzewo puste?
    root = w;                  // Jeśli tak, to w staje się korzeniem
  else
    while(true)                // Pętla nieskończona
      if(prio < p->key)        // W zależności od klucza idziemy do lewego lub
      {                        // prawego syna, o ile takowy istnieje
        if(!p->left)           // Jeśli lewego syna nie ma,
        {
          p->left = w;         // to w staje się lewym synem
          break;               // Przerywamy pętlę while
        }
        else p = p->left;
      }
      else
      {
        if(!p->right)          // Jeśli prawego syna nie ma,
        {
          p->right = w;        // to w staje się prawym synem
          break;               // Przerywamy pętlę while
        }
        else p = p->right;
      }

  w->up   = p;     // Ojcem w jest zawsze p
}

// Usuwa z kolejki
//----------------
void queue::pop()
{
  BSTNode * p;

  if(root)         // Jeśli drzewo BST nie jest puste,
  {                // to szukamy największego elementu
    for(p = root; p->right; p = p->right) ;

// Jeśli element ma lewego syna, to jego ojcem stanie się ojciec elementu

    if(p->left) p->left->up = p->up;

// Jeśli element ma ojca, to jego prawym synem stanie sie lewy syn elementu

    if(p->up) p->up->right = p->left;
    else root = p->left;   // inaczej uaktualniamy korzeń drzewa

    delete p;              // zwalniamy pamięć
  }
}

//---------------
// Program główny
//---------------
int main()
{
  queue * Q = new queue;     // kolejka
  int i,p,v;

  srand(time(NULL));         // Inicjujemy generator pseudolosowy

  for(i = 0; i < 10; i++)    // Wstawiamy do kolejki 10 elementów
  {                          // o różnych priorytetach.
    v = rand() % 100;
    p = rand() %  10;
    cout << setw(2) << v << ":" << p << endl;
    Q->push(p,v);
  }

  cout << "----" << endl;

  while(!Q->empty())         // Pobieramy z kolejki kolejne elementy
  {
    cout << setw(2) << Q->front() << ":" << Q->frontprio() << endl; // Wypisujemy ich zawartość
    Q->pop();                // i usuwamy z kolejki
  }

  delete Q;
}
Free Basic
' Kolejka priorytetowa oparta na drzewie BST
' Data: 11.05.2013
' (C)2012 mgr Jerzy Wałaszek
'------------------------------
const MAXINT As Integer = 2147483647

' Definicja typu węzłów drzewa
'-------------------------------

' Typ węzłów drzewa BST
'----------------------

Type BSTNode
  Left As BSTNode Ptr
  Right As BSTNode Ptr
  Up As BSTNode Ptr
  key As Integer   ' Klucz jest priorytetem
  Data As integer ' Dane przechowywane przez węzeł
End Type

' Definicja typu obiektowego queue
'---------------------------------
Type queue
  Private:
    root As BSTNode Ptr    ' Korzeń drzewa BST

  Public:
    Declare Constructor()	
    Declare Destructor()
    Declare Function empty() As Integer
    Declare Function front() As Integer
    Declare Function frontprio() As Integer
    Declare Sub push(ByVal prio As integer, ByVal v As integer)
    Declare Sub pop()
End Type

'---------------------
' Metody obiektu queue
'---------------------

' Konstruktor - tworzy pustą listę
'---------------------------------
Constructor queue()
  root = 0
End Constructor

' Procedura DFS:postorder usuwająca drzewo
'-----------------------------------------
sub DFSRelease(ByVal v As BSTNode Ptr)
  If v Then
    DFSRelease(v->left)   ' usuwamy lewe poddrzewo
    DFSRelease(v->right)  ' usuwamy prawe poddrzewo
    delete v              ' usuwamy sam węzeł
  End If
End Sub

' Destruktor - usuwa listę z pamięci
'-----------------------------------
Destructor queue()
  DFSRelease(root)
End Destructor

' Sprawdza, czy kolejka jest pusta
'---------------------------------
Function queue.empty() As Integer
  Return root = 0
End Function

' Zwraca początek kolejki.
' Wartość specjalna to -MAXINT
'-----------------------------
Function queue.front() As Integer
  Dim As BSTNode Ptr p

  If root Then              ' Jeśli drzewo nie jest puste, to szukamy największego elementu
    p = root
    While p->Right
    	p = p->Right 
    Wend

    return p->Data          ' i zwracamy jego wartość
  Else
    Return -MAXINT          ' inaczej zwracamy wartość specjalną
  End If
End Function

' Zwraca priorytet pierwszego elementu
'-------------------------------------
Function queue.frontprio() As Integer
  Dim As BSTNode Ptr p

  If root Then              ' Jeśli drzewo nie jest puste, to szukamy największego elementu
    p = root
    While p->Right
    	p = p->Right 
    Wend

    Return p->key           ' i zwracamy jego priorytet, czyli klucz
  Else
    Return -MAXINT          ' inaczej zwracamy wartość specjalną
  End If
End Function

' Zapisuje do kolejki
'--------------------
Sub queue.push(ByVal prio As Integer, ByVal v As Integer)
  Dim As BSTNode ptr w, p

  w = new BSTNode             ' Tworzymy dynamicznie nowy węzeł

  w->left  = 0                ' Zerujemy wskazania synów
  w->right = 0
  w->key   = prio             ' Wstawiamy priorytet
  w->data  = v                ' Wstawiamy dane

  p = root                    ' Wyszukujemy miejsce dla w, rozpoczynając od korzenia

  If p = 0 Then               ' Drzewo puste?
    root = w                  ' Jeśli tak, to w staje się korzeniem
  Else
    While 1                   ' Pętla nieskończona
      if prio < p->key Then   ' W zależności od klucza idziemy do lewego lub
                              ' prawego syna, o ile takowy istnieje
        if p->Left = 0 Then   ' Jeśli lewego syna nie ma,
          p->left = w         ' to w staje się lewym synem
          Exit While          ' Przerywamy pętlę while
        Else
          p = p->Left
        End If
      Else
        if p->Right = 0 Then  ' Jeśli prawego syna nie ma,
          p->right = w        ' to w staje się prawym synem
          Exit While          ' Przerywamy pętlę while
        Else
          p = p->Right
        End If
      End If
    Wend
  End If
  w->up   = p                 ' Ojcem w jest zawsze p
End Sub

' Usuwa z kolejki
'----------------
Sub queue.pop()
  Dim As BSTNode Ptr p

  If root Then                ' Jeśli drzewo BST nie jest puste,
                              ' to szukamy największego elementu
    p = root
    While p->Right
      p = p->Right 
    Wend

' Jeśli element ma lewego syna, to jego ojcem stanie się ojciec elementu

    if p->left Then p->left->up = p->up

' Jeśli element ma ojca, to jego prawym synem stanie sie lewy syn elementu

    If p->up Then
    	p->up->right = p->Left
    Else
      root = p->Left   ' inaczej uaktualniamy korzeń drzewa
    End If
    
    Delete p              ' zwalniamy pamięć
  End If
End Sub

'---------------
' Program główny
'---------------
Dim Q As queue
Dim As Integer i,p,v

Randomize

For i = 1 To 10
  v = Int(Rnd() * 100)
  p = Int(Rnd() * 10)
  Print Using "##:#";v;p
  Q.push(p,v)
Next

Print "----"

While Q.empty() = 0
  Print Using "##:#";Q.front();Q.frontprio()
  Q.pop()
Wend

End
Wynik
33:9
39:6
83:9
71:6
61:5
86:4
 6:3
81:4
86:9
17:0
----
86:9
83:9
33:9
71:6
39:6
61:5
81:4
86:4
 6:3
17:0

 

 


   I Liceum Ogólnokształcące   
im. Kazimierza Brodzińskiego
w Tarnowie

©2019 mgr Jerzy Wałaszek

Dokument ten rozpowszechniany jest zgodnie z zasadami licencji
GNU Free Documentation License.

Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl

W artykułach serwisu są używane cookies. Jeśli nie chcesz ich otrzymywać,
zablokuj je w swojej przeglądarce.
Informacje dodatkowe