Równoważenie drzewa BST – algorytm DSW


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
  Rotacje drzewa BST
Algorytm DSW

Problem

Zrównoważyć drzewo BST.


Drzewo binarnych poszukiwań (ang. BST – Binary Search Tree) jest wygodną i szeroko stosowaną strukturą, która przechowuje uporządkowane dane (np. słowniki). Dobrze zbudowane drzewo pozwala wyszukiwać dane ze złożonością klasy O(log n) – np. dla miliarda danych należy wykonać tylko do 30 porównań, aby znaleźć poszukiwany obiekt. Jednakże z sytuacją tą mamy do czynienia tylko wtedy, gdy drzewo BST posiada najmniejszą możliwą wysokość, czyli jest drzewem zrównoważonym (ang. balanced tree). Przy wprowadzaniu danych struktura drzewa wynikowego może nie być optymalna, a w najgorszym przypadku możemy otrzymać listę uporządkowaną, dla której wyszukiwanie ma klasę O(n). Dzieje się tak wtedy, gdy wprowadzamy do drzewa ciąg uporządkowanych elementów. Z uwagi na sposób działania algorytmu wstawiania elementu do drzewa BST elementy uporządkowane zostają dołączone jako prawi synowie kolejnych węzłów przy ciągu rosnącym kluczy lub jako lewi synowie kolejnych węzłów przy ciągu malejącym kluczy.

 

1 - 2 - 3      3 - 2 - 1
BST   BST

 

Podany w tym rozdziale algorytm pozwoli zrównoważyć dowolne drzewo BST. Zanim go omówimy, musimy poznać tzw. rotacje drzewa.

 

Rotacje drzewa

Rotacja drzewa (ang. tree rotation) jest operacją na drzewie BST, która zmienia jego strukturę bez zmiany kolejności elementów, tzn. przejście in-order dla tego drzewa da takie same wyniki przed jak i po rotacji. Wyróżniamy dwie symetryczne rotacje: prawą i lewą.

 

Rotacja w prawo

Rotacja LL

 

Oznaczmy węzły drzewa BST jak na rysunku:

 

A  –  korzeń drzewa
B  –  lewy syn A, który zajmie miejsce A. Nazywamy go piwotem.
BL,BR  –  lewy i prawy syn B
AR  –  prawy syn A

 

Po wykonaniu rotacji w prawo B zajmuje miejsce A, a A staje się prawym synem B. Dodatkowo przemieszcza się również węzeł BR, czyli prawy syn B. Staje się on lewym synem A.

Kolejne fazy operacji rotacji są następujące:

 

Rotacja LL   Węzeł BR staje się lewym synem A.
Rotacja LL   Węzeł A staje się prawym synem B, po czym B zajmuje miejsce A w strukturze drzewa. Rotacja jest zakończona.

 

Zwróć uwagę na jedną charakterystyczną cechę rotacji w prawo: wysokość lewego poddrzewa maleje o 1, natomiast wysokość prawego poddrzewa rośnie o 1.

Rotację w prawo można wykonać tylko wtedy, gdy węzeł A posiada lewego syna B.

 

Algorytm rotacji w prawo drzewa BST

Wejście
root  –  referencja do zmiennej przechowującej adres korzenia drzewa BST
A  –  wskazanie węzła A
Wyjście:
Drzewo BST, na którym została wykonana rotacja w prawo względem węzła A.
Zmienne pomocnicze:
B  –  wskazanie węzła B
p  –  wskazanie ojca A
Lista kroków:
K01: B ← (Aleft) ; w B umieszczamy adres lewego syna węzła A
K02: Jeśli B = nil, to zakończ ; nie można wykonać rotacji
K03: p ← (Aup) ; w p umieszczamy ojca A
K04: (Aleft) ← (Bright) ; lewym synem A staje się prawy syn B
K05: Jeśli (Aleft) ≠ nil, to (Aleftup) ← A ; jeśli lewy syn istnieje, to jego ojcem jest teraz A
K06: (Bright) ← A ; prawym synem B staje się A
K07: (Bup) ← p ; ojcem B jest ojciec węzła A
K08: (Aup) ← B ; natomiast A zmienia ojca na B
K09: Jeśli p = nil, to idź do K12 ; sprawdzamy, czy węzeł A był korzeniem
K10: Jeśli (pleft) = A, to (pleft) ← B
Inaczej                     (pright) ← B
; jeśli nie, to uaktualniamy jego ojca
K11: Zakończ  
K12: rootB ; jeśli A był korzeniem, to uaktualniamy korzeń
K13: Zakończ  

 

Rotacja w lewo

Rotacja RR

 

Rotacja w lewo jest lustrzanym odbiciem rotacji w prawo (w lustrzanym odbiciu synowie prawi przechodzą w lewych i na odwrót). Zwróć uwagę, iż kolejne wykonanie rotacji w lewo i w prawo (lub w prawo i lewo) doprowadza drzewo do stanu początkowego.

 

Algorytm rotacji w lewo drzewa BST

Wejście
root  –  referencja do zmiennej przechowującej adres korzenia drzewa BST
A  –  wskazanie węzła A
Wyjście:
Drzewo BST, na którym została wykonana rotacja w lewo względem węzła A.
Zmienne pomocnicze:
B  –  wskazanie węzła B
p  –  wskazanie ojca A
Lista kroków:
K01: B ← (Aright) ; w B umieszczamy adres prawego syna węzła A
K02: Jeśli B = nil, to zakończ  
K03: p ← (Aup) ; w p umieszczamy ojca A
K04: (Aright) ← (Bleft) ; prawym synem A staje się lewy syn B
K05: Jeśli (Aright) ≠ nil, to (Arightup) ← A ; jeśli prawy syn istnieje, to jego ojcem jest teraz A
K06: (Bleft) ← A ; lewym synem B staje się A
K07: (Bup) ← p ; ojcem B jest ojciec węzła A
K08: (Aup) ← B ; natomiast A zmienia ojca na B
K09: Jeśli p = nil, to idź do K12 ; sprawdzamy, czy węzeł A był korzeniem
K10: Jeśli (pleft) = A, to (pleft) ← B
Inaczej                     (pright) ← B
; jeśli nie, to uaktualniamy jego ojca
K11: Zakończ  
K12: rootB ; jeśli A był korzeniem, to uaktualniamy korzeń
K13: Zakończ  

 

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 drzewo BST o 15 węzłach, a następnie dokonuje rotacji:
  • lewego poddrzewa korzenia w lewo
  • prawego poddrzewa korzenia w prawo

Program prezentuje wyniki w oknie konsoli.

 

Lazarus
// Rotacje drzewa BST
// Data: 3.05.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program bst;

// Typ węzłów drzewa BST

type
  PBSTNode = ^BSTNode;
  BSTNode  = record
    up,left,right : PBSTNode;
    key   : integer;
  end;

// Zmienne globalne

var
  cr,cl,cp : string;      // łańcuchy do znaków ramek

// Procedura wypisuje drzewo
//--------------------------
procedure printBT(sp,sn : string; v : PBSTNode);
var
  s : string;
begin
  if v <> nil then
  begin
    s := sp;
    if sn = cr then s[length(s) - 1] := ' ';
    printBT(s+cp,cr,v^.right);

    s := Copy(sp,1,length(sp)-2);
    writeln(s,sn,v^.key);

    s := sp;
    if sn = cl then s[length(s) - 1] := ' ';
    printBT(s+cp,cl,v^.left);
  end
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;

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

// Rotacja w lewo
//---------------
procedure rot_L(var root : PBSTNode; A : PBSTNode);
var
  B,p : PBSTNode;
begin
  B := A^.right;
  if B <> nil then
  begin
    p := A^.up;
    A^.right := B^.left;
    if A^.right <> nil then A^.right^.up := A;

    B^.left := A;
    B^.up := p;
    A^.up := B;

    if p <> nil then
    begin
      if p^.left = A then p^.left := B else p^.right := B;
    end
    else root := B;
  end;
end;

// Rotacja w prawo
//----------------
procedure rot_R(var root : PBSTNode; A : PBSTNode);
var
  B,p : PBSTNode;
begin
  B := A^.left;
  if B <> nil then
  begin
    p := A^.up;
    A^.left := B^.right;
    if A^.left <> nil then A^.left^.up := A;

    B^.right := A;
    B^.up := p;
    A^.up := B;

    if p <> nil then
    begin
      if p^.left = A then p^.left := B else p^.right := B;
    end
    else root := B;
  end;
end;

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

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

begin
  // ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
  // wstawiać znaki konsoli do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr := #218#196;
  cl := #192#196;
  cp := #179#32;

  randomize;            // Inicjujemy generator pseudolosowy

  root := nil;          // Tworzymy puste drzewo BST

  for i := 1 to 15 do   // Drzewo wypełniamy węzłami
    insertBST(root,10 + random(90));

  printBT('','',root);  // wyświetlamy drzewo

  writeln; writeln;

  // Dokonujemy rotacji lewego poddrzewa w lewo, jeśli istnieje

  if root^.left <> nil then rot_L(root,root^.left);

  // Dokonujemy rotacji prawego poddrzewa w prawo, jeśli istnieje

  if root^.right <> nil then rot_R(root,root^.right);

  printBT('','',root);  // wyświetlamy drzewo

  writeln; writeln;

  DFSRelease(root);     // Usuwamy drzewo BST z pamięci
end.
Code::Blocks
// Rotacje drzewa BST
// Data: 3.05.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

// Typ węzłów drzewa BST

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

// Zmienne globalne

string cr,cl,cp;      // łańcuchy do znaków ramek

// Procedura wypisuje drzewo
//--------------------------
void printBT(string sp, string sn, BSTNode * v)
{
  string s;

  if(v)
  {
    s = sp;
    if(sn == cr) s[s.length() - 2] = ' ';
    printBT(s + cp, cr, v->right);

    s = s.substr(0,sp.length()-2);
    cout << s << sn << v->key << endl;

    s = sp;
    if(sn == cl) s[s.length() - 2] = ' ';
    printBT(s + cp, cl, v->left);
  }
}

// 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;
      }

  w->up  = p;                // Ojcem węzła w jest zawsze węzeł wskazywany przez p
}

// Rotacja w lewo
//---------------
void rot_L(BSTNode * & root, BSTNode * A)
{
  BSTNode * B = A->right, * p = A->up;

  if(B)
  {
    A->right = B->left;
    if(A->right) A->right->up = A;

    B->left = A;
    B->up = p;
    A->up = B;

    if(p)
    {
      if(p->left == A) p->left = B; else p->right = B;
    }
    else root = B;
  }
}

// Rotacja w prawo
//----------------
void rot_R(BSTNode * & root, BSTNode * A)
{
  BSTNode * B = A->left, * p = A->up;

  if(B)
  {
    A->left = B->right;
    if(A->left) A->left->up = A;

    B->right = A;
    B->up = p;
    A->up = B;

    if(p)
    {
      if(p->left == A) p->left = B; else p->right = B;
    }
    else root = B;
  }
}

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

int main()
{
  int i;
  BSTNode * root = NULL;

  // ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
  // wstawiać znaki konsoli do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr = cl = cp = "  ";
  cr[0] = 218; cr[1] = 196;
  cl[0] = 192; cl[1] = 196;
  cp[0] = 179;

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

  for(i = 0; i < 15; i++)   // Drzewo wypełniamy węzłami
    insertBST(root,10 + rand() % 90);

  printBT("","",root);  // wyświetlamy drzewo

  cout << endl << endl;

  // Dokonujemy rotacji lewego poddrzewa w lewo, jeśli istnieje

  if(root->left) rot_L(root,root->left);

  // Dokonujemy rotacji prawego poddrzewa w prawo, jeśli istnieje

  if(root->right) rot_R(root,root->right);

  printBT("","",root);  // wyświetlamy drzewo

  cout << endl << endl;

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

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

' Typ węzłów drzewa BST

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

' Zmienne globalne

Dim Shared As String * 2 cr,cl,cp ' łańcuchy do ramek

' Procedura wypisuje drzewo
'--------------------------
Sub printBT(sp As String, sn As String, v As BSTNode Ptr)

  Dim As String s

  If v Then
    s = sp
    If sn = cr Then Mid(s,Len(s) - 1, 1) = " "
    printBT(s + cp, cr, v->Right)

    s = Mid(s,1, Len(sp)-2)
    Print Using "&&&";s;sn;v->key

    s = sp
    If sn = cl Then Mid(s,Len(s) - 1, 1) = " "
    printBT(s + cp, cl, v->Left)
  End If
End Sub

' 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
  
  w->up  = p                ' Ojcem węzła w jest zawsze węzeł wskazywany przez p

End Sub

' Rotacja w lewo
'---------------
Sub rot_L(ByRef root As BSTNode Ptr, ByVal A As BSTNode Ptr)
	
  Dim As BSTNode Ptr B = A->right, p = A->up

  If B Then
    A->right = B->Left
    If A->Right Then A->right->up = A

    B->left = A
    B->up = p
    A->up = B

    If p Then
      If p->left = A Then
        p->left = B
      Else
        p->right = B
      End If
    Else
      root = B
    End If
  End If
End Sub

' Rotacja w prawo
'----------------
Sub rot_R(ByRef root As BSTNode Ptr, ByVal A As BSTNode Ptr)

  Dim As BSTNode Ptr B = A->left, p = A->up

  If B Then
    A->left = B->Right
    If A->left Then A->left->up = A

    B->right = A
    B->up = p
    A->up = B

    If p Then
      If p->left = A Then
        p->left = B
      Else
       p->right = B
      End If
    Else
      root = B
    End If
  End If
End Sub

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

Dim As Integer i
Dim As BSTNode Ptr root = 0

' ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
' wstawiać znaki konsoli do tworzenia ramek.
' cr = +--
'      |

' cl = |
'      +--

' cp = |
'      |

cr = Chr(218) + Chr(196)
cl = Chr(192) + Chr(196)
cp = Chr(179) + " "

Randomize                ' Inicjujemy generator pseudolosowy

For i = 1 To 15          ' Drzewo wypełniamy węzłami
  insertBST(root,10 + Int(Rnd() * 90))
Next

printBT("","",root)      ' wyświetlamy drzewo

Print: Print

' Dokonujemy rotacji lewego poddrzewa w lewo, jeśli istnieje

If root->Left Then rot_L(root,root->left)

' Dokonujemy rotacji prawego poddrzewa w prawo, jeśli istnieje

if root->right Then rot_R(root,root->right)

printBT("","",root)  ' wyświetlamy drzewo

Print: Print

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

End
Wynik
    ┌─94
  ┌─88
┌─87
│ │ ┌─81
│ └─70
│   └─69
│     └─59
│       └─56
│         └─50
│           └─45
41
│ ┌─31
│ │ └─27
└─21
  └─16


      ┌─94
    ┌─88
  ┌─87
  │ └─81
┌─70
│ └─69
│   └─59
│     └─56
│       └─50
│         └─45
41
└─31
  │ ┌─27
  └─21
    └─16

 

Algorytm DSW

Zrównoważenie drzewa BST będzie polegało na takiej zmianie jego struktury, aby wysokość wynikowego drzewa BST była minimalna. W drzewie BST o minimalnej wysokości operacje poszukiwań posiadają klasę złożoności O(log n). Wymyślono wiele algorytmów, które realizują to zadanie. Algorytm DSW bierze swoją nazwę od swoich twórców: Colina Day'a (twórca algorytmu w 1976), Quentina Stouta i Bette Waren (modyfikatorzy algorytmu w 1986).

Algorytm DSW działa w dwóch fazach. W fazie pierwszej za pomocą rotacji w prawo drzewo BST zostaje przekształcone w listę liniową

 
     Rozpoczynamy od korzenia. Dopóki posiada on lewych synów, dokonujemy obrotu w prawo.
  Po obrocie zawsze wracamy do korzenia, który teraz jest poprzednim lewym synem. Ponieważ w tym przypadku korzeń nie posiada dalszych lewych synów, przechodzimy do jego prawego syna.
  Nowy węzeł posiada lewego syna, zatem dokonujemy obrotu w prawo.
  Po obrocie węzeł, który zajął miejsce poprzedniego w hierarchii drzewa nie posiada już lewego syna, zatem idziemy wzdłuż prawej krawędzi do pierwszego węzła, który posiada lewego syna, u nas jest to węzeł 15.
  Dokonujemy obrotu w prawo.
  Nowy węzeł nie ma lewego syna, zatem idziemy wzdłuż prawej krawędzi w dół drzewa. Dochodzimy do adresu pustego. Drzewo BST zostało przetworzone w listę liniową.

 

W fazie drugiej za pomocą obrotów w lewo na co drugim węźle przekształcamy listę liniową w drzewo BST.

 
  Korzeń obracamy w lewo.
  Co drugi węzeł obracamy w lewo.
  Kontynuujemy obracanie
  Operację powtarzamy, wyliczając liczbę węzłów do rotacji wg odpowiedniego wzoru.
  W efekcie otrzymujemy zrównoważone drzewo BST.

 

Algorytm DSW wymaga wyznaczenia liczby:

 

 

Liczba ta jest potrzebna do wyznaczenia ilości obrotów przy pierwszym obiegu algorytmu. Wygląda bardzo groźnie, jednak jej interpretacja jest bardzo prosta: to wartość binarna n+1, w której pozostawiono najstarszy bit o wartości 1, a pozostałe bity wyzerowano.

 

Na przykład:

n = 20
n + 1 = 21 = 101012 → 100002 → 16

 

Dzięki temu spostrzeżeniu możemy bardzo prosto wyznaczyć wartość tej liczby przez proste przesuwy bitowe.

 

Algorytm wyznaczania wartości 2|log x|

Wejście
x  –  wartość, dla której liczymy potęgę, x N .
Wyjście:
y – wynik
Lista kroków:
K01: y ← 1 ; wartość początkowa potęgi
K02: xx shr 1 ; przesuwamy wstępnie bity w x o 1 pozycję w prawo
K03: Dopóki x > 0, wykonuj K4...K5  
K04:     yy shl 1 ; bit 1 przesuwamy w y o jedną pozycję w lewo
K05:     xx shr 1 ; bity w x przesuwamy o jedną pozycję w prawo
K06: Zakończ ; koniec, wynik w y

 

Algorytm DSW – zrównoważanie drzewa BST

Wejście
root  –  referencja do zmiennej, która przechowuje adres korzenia drzewa BST.
Wyjście:
Zrównoważone drzewo BST
Zmienne pomocnicze:
p  –  wskazanie węzła
n  –  licznik wierszy, n N
s  –  licznik obrotów, s N
i  –  licznik, i N
rot_L(root,w)  –  procedura obrotu w lewo względem węzła w
rot_R(root,w)  –  procedura obrotu w prawo względem węzła w
log2(x)  –  Oblicza wartość 2|log x|
Lista kroków:
K01: n ← 0 ; zerujemy licznik węzłów
K02: proot ; rozpoczynamy tworzenie listy liniowej
K03: Dopóki pnil, wykonuj K04...K09 ; przetwarzamy drzewo począwszy od korzenia
K04:     Jeśli (pleft) = nil, to idź do K08 ; sprawdzamy, czy węzeł posiada lewego syna
K05:     rot_R(root,p) ; jeśli tak, to wykonujemy obrót w prawo
K06:     p ← (pup) ; wracamy do właściwego węzła po obrocie
K07:     Kontynuuj pętlę K03  
K08:     nn + 1 ; jeśli nie, to zwiększamy licznik węzłów
K09:     p ← (pright) ; i przesuwamy się w dół do prawego syna
K10: sn + 1 - log2(n + 1) ; wyznaczamy liczbę liści na najniższym poziomie
K11: p ← root ; przekształcamy listę w drzewo BST
K12: Dla i = 1,2,...,s: wykonuj K13...K14 ; za pomocą odpowiedniej liczby
K13:     rot_L(root,p) ; obrotów w lewo
K14:     p ← (pupright) ; co drugiego węzła na liście
K15: nn - s ; pomniejszamy liczbę węzłów o ilość liści
K16: Dopóki n > 1: wykonuj K17...K21 ; tworzymy drzewo BST
K17:     nn shr 1 ; n zmniejszamy do połowy
K18:     p root ; zawsze rozpoczynamy od korzenia drzewa
K19:     Dla i = 1,2,...,n: wykonuj K20...K21 ;
K20:          rot_L(root,p) ; obrót w lewo
K21          p ← (pupright) ; następny węzeł do obracania
K22: Zakończ  

 

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 drzewo BST zbudowane z 15 węzłów o losowych kluczach od 1 do 9. Następnie równoważy to drzewo za pomocą algorytmu DSW.

 

Lazarus
// Algorytm DSW
// Data: 4.05.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program bst;

// Typ węzłów drzewa BST

type
  PBSTNode = ^BSTNode;
  BSTNode  = record
    up,left,right : PBSTNode;
    key   : integer;
  end;

// Zmienne globalne

var
  cr,cl,cp : string;      // łańcuchy do znaków ramek

// Procedura wypisuje drzewo
//--------------------------
procedure printBT(sp,sn : string; v : PBSTNode);
var
  s : string;
begin
  if v <> nil then
  begin
    s := sp;
    if sn = cr then s[length(s) - 1] := ' ';
    printBT(s+cp,cr,v^.right);

    s := Copy(sp,1,length(sp)-2);
    writeln(s,sn,v^.key);

    s := sp;
    if sn = cl then s[length(s) - 1] := ' ';
    printBT(s+cp,cl,v^.left);
  end;
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;

  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;

  w^.up  := p;     // Ojcem w jest zawsze p
  w^.key := k;     // Wstawiamy klucz

end;

// Rotacja w lewo
//---------------
procedure rot_L(var root : PBSTNode; A : PBSTNode);
var
  B,p : PBSTNode;
begin
  B := A^.right;
  if B <> nil then
  begin
    p := A^.up;
    A^.right := B^.left;
    if A^.right <> nil then A^.right^.up := A;

    B^.left := A;
    B^.up := p;
    A^.up := B;

    if p <> nil then
    begin
      if p^.left = A then p^.left := B else p^.right := B;
    end
    else root := B;
  end;
end;

// Rotacja w prawo
//----------------
procedure rot_R(var root : PBSTNode; A : PBSTNode);
var
  B,p : PBSTNode;
begin
  B := A^.left;
  if B <> nil then
  begin
    p := A^.up;
    A^.left := B^.right;
    if A^.left <> nil then A^.left^.up := A;

    B^.right := A;
    B^.up := p;
    A^.up := B;

    if p <> nil then
    begin
      if p^.left = A then p^.left := B else p^.right := B;
    end
    else root := B;
  end;
end;

// Funkcja oblicza szybko 2^log2(x)
// Wartością tej funkcji jest liczba x,
// w której pozostawiono najstarszy bit 1.
//----------------------------------------
function log2(x : dword) : dword;
var
  y : integer;
begin
  y := 1;
  x := x shr 1;
  while x > 0 do
  begin
    y := y shl 1;
    x := x shr 1;
  end;
  log2 := y;
end;

// Procedura równoważy drzewo BST
// root - referencja zmiennej zawierającej adres korzenia
//----------------------------------------------------
procedure rebalanceDSW(var root : PBSTNode);
var
  n,i,s : dword;
  p     : PBSTNode;
begin
  n := 0;                         // W n zliczamy węzły
  p := root;
  while p <> nil do               // Dopóki jesteśmy w drzewie
    if p^.left <> nil then        // Jeśli przetwarzany węzeł ma lewego syna,
    begin
      rot_R(root,p);              // to obracamy wokół niego drzewo w prawo
      p := p^.up;
    end
    else
    begin
      inc(n);                     // Inaczej zwiększamy licznik węzłów
      p := p^.right;              // i przesuwamy się do prawego syna
    end;
                                  // Teraz z listy tworzymy drzewo BST
  s := n + 1 - log2(n + 1);       // Wyznaczamy początkową liczbę obrotów

  p := root;                      // Rozpoczynamy od początku drzewa
  for i := 1 to s do              // Zadaną liczbę razy
  begin
    rot_L(root,p);                // co drugi węzeł obracamy w lewo
    p := p^.up^.right;
  end;

  n := n - s;                     // Wyznaczamy kolejne liczby obrotów

  while n > 1 do                  // Powtarzamy procedurę obrotów węzłów
  begin
    n := n shr 1;                 // Jednakże wyznaczając za każdym razem
    p := root;                    // odpowiednio mniejszą liczbę obrotów, która
    for i := 1 to n do            // maleje z potęgami 2.
    begin
      rot_L(root,p);
      p := p^.up^.right;
    end;
  end;
end;

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

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

begin
  // ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
  // wstawiać znaki konsoli do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr := #218#196;
  cl := #192#196;
  cp := #179#32;

  randomize;            // Inicjujemy generator pseudolosowy

  root := nil;          // Tworzymy puste drzewo BST

  for i := 1 to 15 do   // Drzewo wypełniamy węzłami
    insertBST(root,1 + random(9));

  printBT('','',root);  // Wyświetlamy drzewo

  writeln; writeln;

  rebalanceDSW(root);   // Równoważymy drzewo

  printBT('','',root);  // Wyświetlamy drzewo

  writeln; writeln;

  DFSRelease(root);     // Usuwamy drzewo BST z pamięci
end.
Code::Blocks
// Algorytm DSW
// Data: 4.05.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <string>
#include <cstdlib>
#include <ctime>

using namespace std;

// Typ węzłów drzewa BST

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

// Zmienne globalne

string cr,cl,cp;      // łańcuchy do znaków ramek

// Procedura wypisuje drzewo
//--------------------------
void printBT(string sp, string sn, BSTNode * v)
{
  string s;

  if(v)
  {
    s = sp;
    if(sn == cr) s[s.length() - 2] = ' ';
    printBT(s + cp, cr, v->right);

    s = s.substr(0,sp.length()-2);
    cout << s << sn << v->key << endl;

    s = sp;
    if(sn == cl) s[s.length() - 2] = ' ';
    printBT(s + cp, cl, v->left);
  }
}

// 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

  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;
      }

  w->up  = p;                // Ojcem węzła w jest zawsze węzeł wskazywany przez p
  w->key = k;                // Wstawiamy klucz. Operacja jest zakończona.

}

// Rotacja w lewo
//---------------
void rot_L(BSTNode * & root, BSTNode * A)
{
  BSTNode * B = A->right, * p = A->up;

  if(B)
  {
    A->right = B->left;
    if(A->right) A->right->up = A;

    B->left = A;
    B->up = p;
    A->up = B;

    if(p)
    {
      if(p->left == A) p->left = B; else p->right = B;
    }
    else root = B;
  }
}

// Rotacja w prawo
//----------------
void rot_R(BSTNode * & root, BSTNode * A)
{
  BSTNode * B = A->left, * p = A->up;

  if(B)
  {
    A->left = B->right;
    if(A->left) A->left->up = A;

    B->right = A;
    B->up = p;
    A->up = B;

    if(p)
    {
      if(p->left == A) p->left = B; else p->right = B;
    }
    else root = B;
  }
}


// Funkcja oblicza szybko 2^log2(x)
// Wartością tej funkcji jest liczba x,
// w której pozostawiono najstarszy bit 1.
//----------------------------------------
unsigned log2(unsigned x)
{
  unsigned y = 1;

  while((x >>= 1) > 0) y <<= 1;

  return y;
}

// Procedura równoważy drzewo BST
// root - referencja zmiennej zawierającej adres korzenia
//----------------------------------------------------
void rebalanceDSW(BSTNode * & root)
{
  unsigned n,i,s;
  BSTNode * p;

  n = 0;                          // W n zliczamy węzły
  p = root;                       // Rozpoczynamy tworzenie listy liniowej
  while(p)                        // Dopóki jesteśmy w drzewie
    if(p->left)                   // Jeśli przetwarzany węzeł ma lewego syna,
    {
       rot_R(root,p);             // to obracamy wokół niego drzewo w prawo
       p = p->up;
    }
    else
    {
      n++;                        // Inaczej zwiększamy licznik węzłów
      p = p->right;               // i przesuwamy się do prawego syna
    }
                                  // Teraz z listy tworzymy drzewo BST
  s = n + 1 - log2(n + 1);        // Wyznaczamy początkową liczbę obrotów

  p = root;                       // Rozpoczynamy od początku drzewa
  for(i = 0; i < s; i++)          // Zadaną liczbę razy
  {
    rot_L(root,p);                // co drugi węzeł obracamy w lewo
    p = p->up->right;
  }

  n = n - s;                      // Wyznaczamy kolejne liczby obrotów

  while(n > 1)                    // Powtarzamy procedurę obrotów węzłów
  {
    n >>= 1;                      // Jednakże wyznaczając za każdym razem
    p = root;                     // odpowiednio mniejszą liczbę obrotów, która
    for(i = 0; i < n; i++)        // maleje z potęgami 2.
    {
      rot_L(root,p);
      p = p->up->right;
    }
  }
}

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

int main()
{
  int i;
  BSTNode * root = NULL;

  // ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
  // wstawiać znaki konsoli do tworzenia ramek.
  // cr = +--
  //      |

  // cl = |
  //      +--

  // cp = |
  //      |

  cr = cl = cp = "  ";
  cr[0] = 218; cr[1] = 196;
  cl[0] = 192; cl[1] = 196;
  cp[0] = 179;

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

  for(i = 0; i < 15; i++)   // Drzewo wypełniamy węzłami
    insertBST(root,1 + rand() % 9);

  printBT("","",root);      // wyświetlamy drzewo

  cout << endl << endl;

  rebalanceDSW(root);       // Równoważymy drzewo

  printBT("","",root);      // wyświetlamy drzewo

  cout << endl << endl;

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

  return 0;
}
Free Basic
' Algorytm DSW
' Data: 4.05.2013
' (C)2013 mgr Jerzy Wałaszek
'------------------------------

' Typ węzłów drzewa BST

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

' Zmienne globalne

Dim Shared As String * 2 cr,cl,cp ' łańcuchy do ramek

' Procedura wypisuje drzewo
'--------------------------
Sub printBT(sp As String, sn As String, v As BSTNode Ptr)

  Dim As String s

  If v Then
    s = sp
    If sn = cr Then Mid(s,Len(s) - 1, 1) = " "
    printBT(s + cp, cr, v->Right)

    s = Mid(s,1, Len(sp)-2)
    Print Using "&&&";s;sn;v->key

    s = sp
    If sn = cl Then Mid(s,Len(s) - 1, 1) = " "
    printBT(s + cp, cl, v->Left)
  End If
End Sub

' 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

  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
  
  w->up  = p                ' Ojcem węzła w jest zawsze węzeł wskazywany przez p
  w->key = k                ' Wstawiamy klucz. Operacja jest zakończona.

End Sub

' Rotacja w lewo
'---------------
Sub rot_L(ByRef root As BSTNode Ptr, ByVal A As BSTNode Ptr)
	
  Dim As BSTNode Ptr B = A->right, p = A->up

  If B Then
    A->right = B->Left
    If A->Right Then A->right->up = A

    B->left = A
    B->up = p
    A->up = B

    If p Then
      If p->left = A Then
        p->left = B
      Else
        p->right = B
      End If
    Else
      root = B
    End If
  End If
End Sub

' Rotacja w prawo
'----------------
Sub rot_R(ByRef root As BSTNode Ptr, ByVal A As BSTNode Ptr)

  Dim As BSTNode Ptr B = A->left, p = A->up

  If B Then
    A->left = B->Right
    If A->left Then A->left->up = A

    B->right = A
    B->up = p
    A->up = B

    If p Then
      If p->left = A Then
        p->left = B
      Else
       p->right = B
      End If
    Else
      root = B
    End If
  End If
End Sub

' Funkcja oblicza szybko 2^log2(x)
' Wartością tej funkcji jest liczba x,
' w której pozostawiono najstarszy bit 1.
'----------------------------------------
Function log2(ByVal x As UInteger) As UInteger 
  Dim As UInteger y = 1
  
  x shr= 1
  
  While x > 0
  	 y shl= 1
  	 x Shr= 1
  Wend

  log2 = y
End Function

' Procedura równoważy drzewo BST
' root - referencja zmiennej zawierającej adres korzenia
'----------------------------------------------------
Sub rebalanceDSW(ByRef root As BSTNode Ptr)

  Dim As UInteger n,i,s
  Dim As BSTNode Ptr p

  n = 0                           ' W n zliczamy węzły
  p = root                        ' Rozpoczynamy tworzenie listy liniowej
  While p                         ' Dopóki jesteśmy w drzewie
    If p->left Then               ' Jeśli przetwarzany węzeł ma lewego syna,
      rot_R(root,p)               ' to obracamy wokół niego drzewo w prawo
      p = p->up
    Else
      n += 1                      ' Inaczej zwiększamy licznik węzłów
      p = p->Right                ' i przesuwamy się do prawego syna
    End If
  Wend
                                  ' Teraz z listy tworzymy drzewo BST
  s = n + 1 - log2(n + 1)         ' Wyznaczamy początkową liczbę obrotów

  p = root                        ' Rozpoczynamy od początku drzewa
  For i = 1 To s                  ' Zadaną liczbę razy
    rot_L(root,p)                 ' co drugi węzeł obracamy w lewo
    p = p->up->Right
  Next

  n = n - s                       ' Wyznaczamy kolejne liczby obrotów

  While n > 1                     ' Powtarzamy procedurę obrotów węzłów
    n shr= 1                      ' Jednakże wyznaczając za każdym razem
    p = root                      ' odpowiednio mniejszą liczbę obrotów, która
    For i = 1 To n                ' maleje z potęgami 2.
      rot_L(root,p)
      p = p->up->right
    Next
  Wend

End Sub

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

Dim As Integer i
Dim As BSTNode Ptr root = 0

' ustawiamy łańcuchy znakowe, ponieważ nie wszystkie edytory pozwalają
' wstawiać znaki konsoli do tworzenia ramek.
' cr = +--
'      |

' cl = |
'      +--

' cp = |
'      |

cr = Chr(218) + Chr(196)
cl = Chr(192) + Chr(196)
cp = Chr(179) + " "

Randomize                ' Inicjujemy generator pseudolosowy

For i = 1 To 15          ' Drzewo wypełniamy węzłami
  insertBST(root,1 + Int(Rnd() * 9))
Next

printBT("","",root)      ' wyświetlamy drzewo

Print: Print

rebalanceDSW(root)       ' Równoważymy drzewo

printBT("","",root)      ' wyświetlamy drzewo

Print: Print

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

End
Wynik
      ┌─9
    ┌─9
    │ └─8
  ┌─8
  │ │     ┌─7
  │ │     │ └─6
  │ │   ┌─6
  │ │ ┌─5
  │ └─5
  │   │ ┌─4
  │   └─4
┌─3
2
│ ┌─1
└─1


    ┌─9
  ┌─9
  │ └─8
┌─8
│ │ ┌─7
│ └─6
│   └─6
5
│   ┌─5
│ ┌─4
│ │ └─4
└─3
  │ ┌─2
  └─1
    └─1

 

 


   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