Algorytmy i Struktury Danych

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

obrazek

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:

	Węzeł BR staje się lewym synem A.
	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 ← ( A→left )	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 ← ( A→up )	w p umieszczamy ojca A
K04:	( A→left ) ← ( B→right )	lewym synem A staje się prawy syn B
K05:	Jeśli ( A→left ) ≠ nil, to ( A→left→up ) ← A	jeśli lewy syn istnieje, to jego ojcem jest teraz A
K06:	( B→right ) ← A	prawym synem B staje się A
K07:	( B→up ) ← p	ojcem B jest ojciec węzła A
K08:	( A→up ) ← B	natomiast A zmienia ojca na B
K09:	Jeśli p = nil, to idź do kroku K12	sprawdzamy, czy węzeł A był korzeniem
K10:	Jeśli ( p→left ) = A, to ( p→left ) ← B inaczej ( p→right ) ← B	jeśli nie, to uaktualniamy jego ojca
K11:	Zakończ
K12:	root ← B	jeśli A był korzeniem, to uaktualniamy korzeń
K13:	Zakończ

Rotacja w lewo

obrazek

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 ← ( A→right )	w B umieszczamy adres prawego syna węzła A
K02:	Jeśli B = nil, to zakończ
K03:	p ← ( A→up )	w p umieszczamy ojca A
K04:	( A→right ) ← ( B→left )	prawym synem A staje się lewy syn B
K05:	Jeśli ( A→right ) ≠ nil, to ( A→right→up ) ← A	jeśli prawy syn istnieje, to jego ojcem jest teraz A
K06:	( B→left ) ← A	lewym synem B staje się A
K07:	( B→up ) ← p	ojcem B jest ojciec węzła A
K08:	( A→up ) ← B	natomiast A zmienia ojca na B
K09:	Jeśli p = nil, to idź do kroku K12	sprawdzamy, czy węzeł A był korzeniem
K10:	Jeśli ( p→left ) = A, to ( p→left ) ← B Inaczej ( p→right ) ← B	jeśli nie, to uaktualniamy jego ojca
K11:	Zakończ
K12:	root ← B	jeśli A był korzeniem, to uaktualniamy korzeń
K13:	Zakończ

Przykładowe programy

Uwaga:

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.

Pascal

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

C++

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

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

Na początek: podrozdziału strony

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 = 10101₂ → 10000₂ → 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:

–

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:	x ← x shr 1	przesuwamy wstępnie bity w x o 1 pozycję w prawo
K03:	Dopóki x > 0, wykonuj kroki K4...K5
K04:	y ← y shl 1	bit 1 przesuwamy w y o jedną pozycję w lewo
K05:	x ← x 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:	p ← root	rozpoczynamy tworzenie listy liniowej
K03:	Dopóki p ≠ nil, wykonuj kroki K04...K09	przetwarzamy drzewo począwszy od korzenia
K04:	Jeśli ( p→left ) = 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 ← ( p→up )	wracamy do właściwego węzła po obrocie
K07:	Kontynuuj pętlę K03
K08:	n ← n + 1	jeśli nie, to zwiększamy licznik węzłów
K09:	p ← ( p→right )	i przesuwamy się w dół do prawego syna
K10:	s ← n + 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 kroki K13...K14	za pomocą odpowiedniej liczby
K13:	rot_L ( root, p )	obrotów w lewo
K14:	p ← ( p→up→right )	co drugiego węzła na liście
K15:	n ← n - s	pomniejszamy liczbę węzłów o ilość liści
K16:	Dopóki n > 1: wykonuj kroki K17...K21	tworzymy drzewo BST
K17:	n ← n shr 1	n zmniejszamy do połowy
K18:	p ← root	zawsze rozpoczynamy od korzenia drzewa
K19:	Dla i = 1, 2, ..., n : wykonuj kroki K20...K21
K20:	rot_L ( root, p )	obrót w lewo
K21	p ← ( p→up→right )	następny węzeł do obracania
K22:	Zakończ

Przykładowe programy

Uwaga:

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.

Pascal

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

C++

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

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

Na początek: podrozdziału strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone
pod warunkiem podania źródła oraz niepobierania za to pieniędzy.

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

Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Równoważenie drzewa BST – algorytm DSW

Problem

Rotacje drzewa

Rotacja w prawo

Algorytm rotacji w prawo drzewa BST

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Rotacja w lewo

Algorytm rotacji w lewo drzewa BST

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Algorytm DSW

Algorytm wyznaczania wartości 2^{|log x|}

Wejście:

Wyjście:

Lista kroków:

Algorytm DSW – zrównoważanie drzewa BST

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Równoważenie drzewa BST – algorytm DSW

Problem

Rotacje drzewa

Rotacja w prawo

Algorytm rotacji w prawo drzewa BST

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Rotacja w lewo

Algorytm rotacji w lewo drzewa BST

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Algorytm DSW

Algorytm wyznaczania wartości 2 |log x|

Wejście:

Wyjście:

Lista kroków:

Algorytm DSW – zrównoważanie drzewa BST

Wejście:

Wyjście:

Zmienne pomocnicze:

Lista kroków:

Przykładowe programy

Algorytm wyznaczania wartości 2^{|log x|}