Serwis Edukacyjny
w I-LO w Tarnowie
obrazek

Materiały dla uczniów liceum

  Wyjście       Spis treści       Wstecz       Dalej  

Autor artykułu: mgr Jerzy Wałaszek

©2020 mgr Jerzy Wałaszek
I LO w Tarnowie

Drzewa Splay

SPIS TREŚCI
Podrozdziały

Wiadomości podstawowe

Przedstawione w poprzednim rozdziale drzewa AVL pozwalały na utrzymywanie optymalnej wysokości drzewa binarnego, co przekłada się na szybkość w operacjach wyszukiwania danych przechowywanych w drzewie. Jednakże drzewa AVL wymagają dosyć skomplikowanych algorytmów przy wstawianiu i usuwaniu węzłów oraz każdy węzeł musi przechowywać dodatkowy parametr bf  zwany współczynnikiem równowagi. Zwiększa to zapotrzebowanie na pamięć.

Z tych powodów wymyślono prostsze struktury danych, zwane drzewami Splay ( ang. splay trees ). Wynalazcami tej struktury danych są Daniel Dominic Sleator oraz Robert Endre Tarjan. Nazwa drzew pochodzi od operacji splay ( T, x ) ( czytaj splej ), która wyszukuje w drzewie T węzeł x i umieszcza go w korzeniu drzewa. Jeśli w drzewie T nie ma węzła x, to w korzeniu jest umieszczany taki węzeł x' drzewa T, iż pomiędzy x a x' nie istnieje w tym drzewie żaden inny węzeł.

Węzły drzewa Splay są zwykłymi węzłami drzewa BST:

Pascal
type
  PBSTNode = ^BSTNode;
  BSTNode  = record
    up    : PBSTNode;
    left  : PBSTNode;
    right : PBSTNode;
    key   : integer;
    data  : typ_danych;
  end;
   C++
struct BSTNode
{
  BSTNode * up;
  BSTNode * left;
  BSTNode * right;
  int key;
  typ_danych data;
};
   Basic
Type BSTNode
  up    As BSTNode Ptr
  left  As BSTNode Ptr
  right As BSTNode Ptr
  key   As Integer
  data  As typ_danych
End Type

Zbalansowane drzewa BST zostały zaprojektowane w celu zredukowania pesymistycznego czasu wykonywania operacji. Jednakże w typowych aplikacjach wykonuje się na nich nie pojedyncze operacje lecz całe serie, zatem istotne znaczenie ma czas wykonania takiej serii operacji ( np. sprawdzenie poprawności ortograficznej tekstu wymaga wielu poszukiwań w drzewie BST słownika - przynajmniej tyle razy, ile wyrazów zawiera tekst ). W takiej sytuacji zamiast optymalizować pojedyncze operacje na drzewie BST, lepszym celem będzie zoptymalizowanie czasu zamortyzowanego ciągu operacji, gdzie przez czas zamortyzowany ( ang. amortized time ) autorzy tej struktury rozumieją średni czas operacji w przypadku pesymistycznym dla ciągu operacji na drzewie BST.

Właśnie opisane poniżej samoorganizujące się drzewa BST pozwalają zoptymalizować czas zamortyzowany. Pomiędzy operacjami drzewo może znajdować się w dowolnym stanie, jednakże przy każdej operacji zostaje ono przebudowane na korzyść przyszłych operacji. Dzięki operacji splay często wykorzystywane elementy wędrują w pobliże korzenia drzewa BST. Zatem kolejny dostęp do nich będzie już dużo szybszy.

Drzewa Splay posiadają kilka zalet w stosunku do struktur zbalansowanych o różnych ograniczeniach:

Samoorganizujące się drzewa BST posiadają jednakże trzy potencjalne wady:

  1. Wymagają więcej lokalnych regulacji, szczególnie podczas dostępu do danych. Struktury z ograniczeniami wymagają regulacji tylko przy przebudowie drzewa, a nie przy dostępie do danych.
  2. Pojedyncze operacje w ciągu mogą być kosztowne, co może się okazać wadą w rzeczywistych aplikacjach.
  3. Ponieważ każda operacja na takim drzewie przebudowuje go, to zastosowanie drzew splay w środowisku wielowątkowym może napotykać na pewne trudności, ale to już wyższa szkoła jazdy.
Na początek:  podrozdziału   strony 

Operacja Splay

Operacja Splay ( ang. rozchylanie ) polega na przemieszczeniu wybranego węzła w górę do korzenia drzewa. Przemieszczanie to dokonywane jest przy pomocy rotacji, które poznaliśmy przy okazji drzew AVL. W przypadku drzew Splay operacje te upraszczają się, ponieważ nie musimy się martwić o współczynniki zrównoważenia bf, których tutaj po prostu nie ma. Istnieją trzy zasady wykonywania rotacji w drzewie Splay:

Zasada nr 1 ( zig ):

Jeśli ojcem y  węzła x  jest korzeń drzewa T, to wykonujemy rotację pojedynczą, w której uczestniczą ojciec y  oraz węzeł x. Rotacja taka kończy operację splay. Poniższy rysunek przedstawia sposób wykonania rotacji.

obrazek

Zasada nr 2 ( zig-zig ):

Jeśli ojciec y  węzła x  nie jest korzeniem, a zarówno y  jak i x  są jednocześnie prawymi lub jednocześnie lewymi synami, to wykonujemy dwie rotacje: najpierw rotacja z dziadkiem z  i ojcem y, a następnie rotacja z ojcem y  i węzłem x. Poniżej przedstawiamy sposób wykonania tych rotacji ( przypadek lustrzany działa identycznie, zatem nie został uwzględniony na rysunku ):

obrazek

Zasada nr 3 ( zig-zag ):

Jeśli ojciec y  nie jest korzeniem, a węzły x  i y  są naprzemiennie lewym i prawym dzieckiem, to najpierw wykonujemy rotację węzła y  z węzłem x, a następnie rotację nowego ojca x ( jest to teraz węzeł z  )  z węzłem y. Poniżej przedstawiamy sposób wykonania tych rotacji:

obrazek

Rotacja zig oraz para rotacji zig-zig lub zig-zag nosi nazwę kroku rozchylającego ( ang. splaying step ). Kroki rozchylające wykonujemy dotąd, aż węzeł x  znajdzie się w korzeniu drzewa. Wtedy operacja splay się kończy.

Operacja splay ( T, x ) składa się zatem z dwóch faz. W pierwszej wyszukujemy węzeł x  w strukturze drzewa T. Jeśli węzeł x  nie zostanie znaleziony, to za x  przyjmujemy ostatni niepusty węzeł, który odwiedziła operacja wyszukiwania. W drugiej fazie wykonujemy kroki rozchylające dotąd, aż znaleziony w pierwszej fazie węzeł x  zostanie przesunięty do korzenia drzewa T.

Algorytm operacji splay

Wejście:

root  –  referencja do zmiennej, która przechowuje korzeń drzewa BST
k  –  klucz węzła, który ma się znaleźć w korzeniu drzewa

Wyjście:

Jeśli węzeł o kluczu k  znajduje się w drzewie BST, to jest on umieszczony w korzeniu. Jeśli takiego węzła nie ma w drzewie, to korzeń zawiera jego bezpośredni poprzednik lub następnik.
Zmienne pomocnicze:
x, y  –  wskazania węzłów
rot_R ( root, w  )  –  rotacja w prawo względem węzła w
rot_L ( root, w  )  –  rotacja w lewo względem węzła w

Lista kroków:

K01: x  ← root rozpoczynamy fazę poszukiwania węzła o kluczu k
K02: Jeśli x  = nil,
to zakończ
drzewo jest puste, kończymy
K03: Jeśli ( xkey  ) = k,
to idź do kroku K08
znaleźliśmy węzeł o kluczu k
K04: y  ← x zapamiętujemy bieżący węzeł
K05: Jeśli k  < ( xkey  ),
to x  ← ( xleft  )
inaczej x  ← ( xright  )
przechodzimy do potomka węzła x
K06: Jeśli x  ≠ nil,
to idź do kroku K03
kontynuujemy wyszukiwanie
K07: x  ← y w drzewie nie ma węzła o kluczu k, za x przyjmujemy poprzednik lub następnik
K08: Jeśli ( xup  ) = nil,
to zakończ
węzeł x znalazł się w korzeniu drzewa
K09: Jeśli ( xupup  ) ≠ nil,
to idź
do kroku K12
badamy odpowiednie przypadki
K10: Jeśli ( xupleft  ) = x,
to rot_R ( root, ( xup  ) )
inaczej rot_L ( root, ( xup  ) )
ojcem x jest korzeń. Rotacja ZIG umieszcza x w korzeniu drzewa
K11: Zakończ  
K12: Jeśli ( xupupleft  ) ≠ ( xup  ) obrazek ( xupleft  ) ≠ x,
to idź do kroku K16
badamy przypadek na ZIG-ZIG
K13: rot_R ( root, ( xupup  ) ) prawy ZIG z dziadkiem x
K14: rot_R ( root, ( xup  ) ) prawy ZIG z ojcem x
K15: Idź do K08 kontynuujemy pętlę
K16: Jeśli ( xupupright  ) ≠ ( xup  ) obrazek ( xupright  ) ≠ x,
to idź do kroku K20
badamy przypadek na ZIG-ZIG
K17: rot_L ( root, ( xupup  ) ) lewy ZIG z dziadkiem x
K18: rot_L ( root, ( xup  ) ) lewy ZIG z ojcem x
K19: Idź do K08  
K20: Jeśli ( xupleft  ) = x,
to idź do kroku K24
ZIG-ZAG
K21: rot_L ( root, ( xup  ) ) lewy ZIG z ojcem x
K22: rot_R ( root, ( xup  ) ) prawy ZAG z pierwotnym dziadkiem x, teraz ojcem x
K23: Idź do kroku K08  
K24: rot_R ( root, ( xup  ) ) przypadek lustrzanego odbicia ZIG-ZAG
K25: rot_L ( root, ( xup  ) )  
K26: Idź do kroku K08  

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 zrównoważone drzewo BST o 15 węzłach z kluczami od 1 do 15, wyświetla je, a następnie wykonuje operację Splay dla losowego klucza i wyświetla drzewo wynikowe.
Pascal
// Drzewo Splay
// Data: 29.05.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

program splaytree;

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

// Procedura Splay
// root - korzeń drzewa
// k    - klucz
//---------------------

procedure splay ( var root : PBSTNode; k : integer );
var
  x, y : PBSTNode;
begin
  x := root;                // Poszukujemy węzła o kluczu k, poczynając od korzenia
  if x <> nil then
  begin
    repeat
      if x^.key = k then break;
      y := x;               // Zapamiętujemy adres węzła
      if k < x^.key then x := x^.left
      else               x := x^.right;
    until x = nil;

    if x = nil then x := y; // Jeśli w drzewie nie ma takiego węzła, to za x
                            // bierzemy bezpośredni następnik lub poprzednik
    while true do           // W pętli węzeł x przesuwamy do korzenia
    begin
      if x^.up = nil then break; // x jest korzeniem, kończymy

      if x^.up^.up = nil then
      begin                 // Ojcem x jest korzeń. Wykonujemy ZIG
        if x^.up^.left = x then rot_R ( root, x^.up )
        else                    rot_L ( root, x^.up );
        break;              // Kończymy
      end;

      if( x^.up^.up^.left = x^.up ) and ( x^.up^.left = x ) then
      begin                 // prawy ZIG-ZIG
        rot_R ( root, x^.up^.up );
        rot_R ( root, x^.up );
        continue;
      end;

      if( x^.up^.up^.right = x^.up ) and ( x^.up^.right = x ) then
      begin                 // lewy ZIG-ZIG
        rot_L ( root, x^.up^.up );
        rot_L ( root, x^.up );
        continue;
      end;

      if x^.up^.right = x then
      begin                // lewy ZIG, prawy ZAG
        rot_L ( root, x^.up );
        rot_R ( root, x^.up );
      end
      else
      begin                // prawy ZIG, lewy ZAG
        rot_R ( root, x^.up );
        rot_L ( root, x^.up );
      end;
    end;
  end;
end;

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

var
  a, b, c, 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

  a := 8; b := 16; c := a;
  for i := 1 to 15 do   // Drzewo wypełniamy węzłami
  begin
    insertBST ( root, c );
    inc ( c, b );
    if c > 16 then
    begin
      a := a shr 1;
      b := b shr 1;
      c := a;
    end;
  end;

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

  writeln; writeln;

  c := 1 + random ( 15 );   // Losujemy klucz
  writeln ( c );

  splay ( root, c );        // Operacja splay dla wylosowanego klucza

  writeln; writeln;

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

  writeln; writeln;

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

end.
C++
// Drzewo Splay
// Data: 29.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;
  }
}

// Procedura Splay
// root - korzeń drzewa
// k    - klucz
//---------------------
void splay ( BSTNode * & root, int k )
{
  BSTNode * x, *y;

  x = root;                 // Poszukujemy węzła o kluczu k, poczynając od korzenia
  if( x )
  {
    do
    {
      if( x->key == k ) break;
      y = x;                // Zapamiętujemy adres węzła
      x = k < x->key ? x->left: x->right;
    } while( x );

    if( !x ) x = y;         // Jeśli w drzewie nie ma takiego węzła, to za x
                            // bierzemy bezpośredni następnik lub poprzednik
    while( true )           // W pętli węzeł x przesuwamy do korzenia
    {
      if( !x->up ) break;   // x jest korzeniem, kończymy

      if( !x->up->up )
      {                     // Ojcem x jest korzeń. Wykonujemy ZIG
        if( x->up->left == x ) rot_R ( root, x->up );
        else rot_L ( root, x->up );
        break;              // Kończymy
      }

      if( ( x->up->up->left == x->up ) && ( x->up->left == x ) )
      {                     // prawy ZIG-ZIG
        rot_R ( root, x->up->up );
        rot_R ( root, x->up );
        continue;
      }

      if( ( x->up->up->right == x->up ) && ( x->up->right == x ) )
      {                     // lewy ZIG-ZIG
        rot_L ( root, x->up->up );
        rot_L ( root, x->up );
        continue;
      }

      if( x->up->right == x )
      {                     // lewy ZIG, prawy ZAG
        rot_L ( root, x->up );
        rot_R ( root, x->up );
      }
      else
      {                     // prawy ZIG, lewy ZAG
        rot_R ( root, x->up );
        rot_L ( root, x->up );
      }
    }
  }
}

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

int main( )
{
  int a, b, c, 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

  a = c = 8; b = 16;
  for( i = 0; i < 15; i++ )   // Drzewo wypełniamy węzłami
  {
    insertBST ( root, c );
    c += b;
    if( c > 16 )
    {
      a >>= 1;
      b >>= 1;
      c = a;
    }
  }

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

  cout << endl << endl;

  c = 1 + rand( ) % 15;     // Losujemy klucz
  cout << c << endl;

  splay ( root, c );        // Operacja splay dla wylosowanego klucza

  cout << endl << endl;

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

  cout << endl << endl;

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

  return 0;
}
Basic
' Drzewo Splay
' Data: 29.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

' Procedura Splay
' root - korzeń drzewa
' k    - klucz
'---------------------
Sub splay ( ByRef root As BSTNode Ptr, ByVal k As Integer )
  Dim As BSTNode Ptr x, y

  x = root                  ' Poszukujemy węzła o kluczu k, poczynając od korzenia
  If x Then
    Do
      If x->key = k Then Exit Do
      y = x                 ' Zapamiętujemy adres węzła
      If k < x->key Then x = x->Left: Else x = x->right
    Loop Until x = 0

    if x = 0 Then x = y     ' Jeśli w drzewie nie ma takiego węzła, to za x
                            ' bierzemy bezpośredni następnik lub poprzednik
    While 1                 ' W pętli węzeł x przesuwamy do korzenia
      If x->up = 0 Then Exit While ' x jest korzeniem, kończymy

      If x->up->up = 0 Then ' Ojcem x jest korzeń. Wykonujemy ZIG
        If x->up->left = x Then rot_R ( root, x->up ): Else rot_L ( root, x->up )
        Exit While          ' Kończymy
      End If

      if( x->up->up->left = x->up ) AndAlso ( x->up->left = x ) Then
        rot_R ( root, x->up->up ) ' prawy ZIG-ZIG
        rot_R ( root, x->up )
        Continue While
      End If

      if( x->up->up->right = x->up ) AndAlso ( x->up->right = x ) Then
        rot_L ( root, x->up->up ) ' lewy ZIG-ZIG
        rot_L ( root, x->up )
        Continue While
      End If

      If x->up->right = x Then
        rot_L ( root, x->up ) ' lewy ZIG, prawy ZAG
        rot_R ( root, x->up )
      Else
        rot_R ( root, x->up ) ' prawy ZIG, lewy ZAG
        rot_L ( root, x->up )
      End If
    Wend
  End If
End Sub

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

Dim As Integer a, b, c, 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

a = 8: c = 8: b = 16
For i = 1 To 15          ' Drzewo wypełniamy węzłami
  insertBST ( root, c )
  c += b
  If c > 16 Then
    a Shr= 1
    b Shr= 1
    c = a
  End If
Next

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

Print: Print

c = 1 + Int ( Rnd( ) * 15 )  ' Losujemy klucz
Print c

splay ( root, c )            ' Operacja splay dla wylosowanego klucza

Print: Print

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

Print: Print

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

End
Wynik:
    ┌─15
  ┌─14
  │ └─13
┌─12
│ │ ┌─11
│ └─10
│   └─9
8
│   ┌─7
│ ┌─6
│ │ └─5
└─4
  │ ┌─3
  └─2
    └─1


13


  ┌─15
┌─14
13
│ ┌─12
│ │ │ ┌─11
│ │ └─10
│ │   └─9
└─8
  │   ┌─7
  │ ┌─6
  │ │ └─5
  └─4
    │ ┌─3
    └─2
      └─1
Na początek:  podrozdziału   strony 

Wyszukiwanie węzłów w drzewie Splay

W Przeciwieństwie do zwykłego drzewa BST, wszystkie operacje na drzewie Splay T  wykorzystują opisaną powyżej operację splay. Wyszukanie węzła o zadanym kluczu k  polega zatem na wykonaniu operacji splay ( T, k ). Następnie sprawdzamy, co znalazło się w korzeniu drzewa. Jeśli korzeń ma klucz równy k, to zwracamy jego adres. W przeciwnym razie zwracamy adres pusty – drzewo T nie zawiera węzła o kluczu k.

Algorytm wyszukiwania węzła w drzewie Splay

Wejście:

root  –  referencja do zmiennej przechowującej korzeń drzewa Splay
k  –  klucz poszukiwanego elementu

Wyjście:

Wskazanie węzła o kluczu k  lub wskazanie puste, jeśli drzewo nie zawiera węzła o kluczu k.
Zmienne pomocnicze:
splay ( root, k  )  –  operacja splay

Lista kroków:

K01: splay ( root, k  ) element o kluczu k trafia do korzenia
K02: Jeśli root  = nil obrazek ( rootkey  ) ≠ k,
to zakończ z wynikiem nil
element nie został znaleziony, zwracamy wskazanie puste
K03: Zakończ z wynikiem root korzeń drzewa zawiera poszukiwany węzeł
Na początek:  podrozdziału   strony 

Wstawianie węzła do drzewa Splay

Aby wstawić węzeł do drzewa Splay, postępujemy następująco:

Jeśli drzewo Splay jest puste, to węzeł umieszczamy w jego korzeniu i kończymy.

W przeciwnym razie wykonujemy operację splay ( T, k  ), gdzie k  jest kluczem wstawianego węzła. Operacja ta umieszcza w węźle bezpośredni następnik lub poprzednik wstawianego węzła x ( jeśli dopuszczamy duplikaty węzłów, to w korzeniu może się znaleźć węzeł o kluczu równym k ).

obrazek

Porównujemy klucz k z kluczem węzła. Jeśli k jest mniejsze od klucza węzła w korzeniu drzewa, to węzeł x wstawiamy jako lewego syna korzenia, w przeciwnym razie x wstawiamy jako prawego syna.

Istnieje również wariant tej metody: węzeł wstawiamy do drzewa BST normalnie, a następnie przesuwamy go do korzenia drzewa za pomocą rotacji węzłów jak w operacji splay. W takim przypadku wstawiany węzeł zawsze znajduje się w korzeniu drzewa. Jednakże ten sam efekt otrzymamy dokonując rotacji w lewo lub w prawo ( w zależności czy węzeł stał się prawym czy lewym synem korzenia ) po wstawieniu węzła wg pierwszej metody.

Algorytm wstawiania węzła do drzewa Splay

Wejście:

root  –  referencja do zmiennej przechowującej korzeń drzewa Splay
k  –  klucz nowego elementu ( mogą również wystąpić dodatkowe dane, które chcemy umieszczać w węzłach )

Wyjście:

Drzewo Splay z wstawionym elementem o kluczu k.

Zmienne pomocnicze:

splay ( root, k  )  –  operacja splay
x  –  wskazanie węzła

Lista kroków:

K01: Utwórz nowy węzeł  
K02: x  ← adres nowego węzła  
K03: ( xleft  ) ← nil ustawiamy pola węzła
K04: ( xright  ) ← nil  
K05: ( xkey  ) ← k  
K06: Jeśli root  ≠ nil,
to idź do kroku K10
 
K07: ( xup  ) ← nil zerujemy ojca węzła x, ponieważ stanie się on korzeniem
K08: root  ← x drzewo jest puste, węzeł x wstawiamy do korzenia
K09: Zakończ  
K10: splay ( root, k  ) w korzeniu umieszczamy bezpośredni poprzednik lub następnik x
K11: ( xup  ) ← root ojcem x zawsze będzie korzeń
K12: Jeśli k  < ( rootkey  ),
to idź do kroku K17
sprawdzamy, gdzie umieścić x
K13: ( xright  ) ← ( rootright  ) x staje się prawym synem korzenia
K14: ( rootright  ) ← x  
K15: Jeśli ( xright  ) ≠ nil,
to ( xrightup  ) ← x
ojcem prawego syna korzenia staje się teraz węzeł x
K16: Zakończ  
K17: ( xleft  ) ← ( rootleft  ) x staje się lewym synem korzenia
K18: ( rootleft  ) ← x  
K19: Jeśli ( xleft  ) ≠ nil,
to ( xleftup  ) ← x
 
K20: Zakończ  
Na początek:  podrozdziału   strony 

Usuwanie węzła z drzewa Splay

Aby usunąć węzeł o kluczu k  z drzewa Splay postępujemy następująco:

Jeśli drzewo Splay jest puste, kończymy.

Wykonujemy operację splay ( T, k  ). Jeśli korzeń drzewa nie zawiera elementu o kluczu k, to kończymy – w drzewie nie ma pożądanego węzła.

W przeciwnym razie odłączamy korzeń od drzewa i usuwamy go z pamięci, zapamiętując jego synów T L i T R. Jeśli oba poddrzewa T L i T R są puste, to kończymy. W przeciwnym razie mamy dwa poddrzewa ( a właściwie przynajmniej jedno poddrzewo ):

T L – o kluczach mniejszych ( lub równych, jeśli dopuściliśmy duplikaty kluczy ) k
T
R – o kluczach większych ( lub równych ) k.

obrazek

Ponownie wykonujemy operację splay ( T L, k  ) lub splay ( T R, k  ) w zależności od tego, które z poddrzew istnieje. W efekcie do korzenia wybranego poddrzewa trafi:

węzeł o maksymalnym kluczu dla T L
węzeł o minimalnym kluczu dla T R

Oznaczmy ten węzeł przez y. Jeśli dopuściliśmy duplikaty kluczy, to za pomocą rotacji ( w lewo dla T L lub w prawo dla T R ) w korzeniu poddrzewa ustawiamy węzeł, który nie posiada prawego syna dla T L lub lewego syna dla T R – jest to konieczne, ponieważ potrzebujemy skrajne węzły poddrzewa, aby połączyć ze sobą T L i T R. Teraz w zależności od tego, w którym z poddrzew jest węzeł y:

w T L: do prawego syna y  dołączamy poddrzewo T R
w T R: do lewego syna y  dołączamy poddrzewo T L

W efekcie otrzymamy pojedyncze drzewo o korzeniu y. Na koniec wskazanie y  zapamiętujemy w zmiennej root.

Algorytm usuwania węzła o kluczu k z drzewa Splay

Wejście:

root  –  referencja do zmiennej przechowującej korzeń drzewa Splay.
k  –  klucz węzła do usunięcia.

Wyjście:

Drzewo Splay z usuniętym węzłem o kluczu k
Zmienne pomocnicze:
T L, T R  –  korzenie poddrzew
splay ( r, k  )  –  wykonuje operację splay na drzewie o korzeniu r   i kluczu k.
rot_L ( r, x  )  –  wykonuje rotację w lewo na poddrzewie o korzeniu r, względem węzła x.
rot_R ( r, x  )  –  wykonuje rotację w prawo na poddrzewie o korzeniu r, względem węzła x.

Lista kroków:

K01: Jeśli root  = nil,
to zakończ
 
K02: splay ( root, k  ) usuwany element idzie do korzenia
K03: Jeśli ( rootkey  ) ≠ k,
to zakończ
w drzewie nie ma węzła o kluczu k
K04: T L ← ( rootleft  ) zapamiętujemy synów korzenia
K05: T R ← ( root→right )  
K06: Usuń węzeł root  z pamięci korzeń usuwamy
K07: root  ← nil  
K08: Jeśli T L = nil, to idź do kroku K16 wybieramy istniejące poddrzewo
K09 ( T Lup  ) ← nil T L jest korzeniem poddrzewa lewego
K10: splay ( T L, k  ) istnieje T L, wykonujemy na nim operację splay
K11: Dopóki ( T Lright  ) ≠ nil,
wykonuj rot_L ( T L, T L )
jeśli w drzewie są duplikaty, to przesuwamy się na skraj drzewa
K12: ( T Lright  ) ← T R prawym synem staje się T R
K13: Jeśli T Rnil,
to ( T Rup  ) ← T L
ojcem T R staje się T L
K14: root  ← T L uaktualniamy korzeń
K15: Zakończ  
K16: Jeśli T R = nil,
to zakończ
węzeł nie miał synów i drzewo jest teraz puste
K17 ( T Rup  ) ← nil T R jest korzeniem poddrzewa prawego
K18: splay ( T R, k  ) przypadek symetryczny dla T R
K19: Dopóki ( T Rleft  ) ≠ nil,
wykonuj rot_R ( T R, T R )
 
K20: ( T Rleft  ) ← T L  
K21: Jeśli T Lnil,
to ( T Lup  ) ← T R
 
K22: root  ← T R uaktualniamy korzeń
K23: 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 losowo drzewo Splay z 30 węzłów o kluczach od 1 do 30. Wyświetla je, następnie usuwa z tego drzewa 10 losowych węzłów i wyświetla drzewo wynikowe.
Pascal
// Wstawianie i usuwanie węzłów na drzewie Splay
// Data: 30.05.2013
// (C)2013 mgr Jerzy Wałaszek
//----------------------------------------------

program splaytree;

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

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

// Procedura Splay
// root - korzeń drzewa
// k    - klucz
//---------------------
procedure splay ( var root : PBSTNode; k : integer );
var
  x, y : PBSTNode;
begin
  x := root;                // Poszukujemy węzła o kluczu k, poczynając od korzenia
  if x <> nil then
  begin
    repeat
      if x^.key = k then break;
      y := x;               // Zapamiętujemy adres węzła
      if k < x^.key then x := x^.left
      else               x := x^.right;
    until x = nil;

    if x = nil then x := y; // Jeśli w drzewie nie ma takiego węzła, to za x
                            // bierzemy bezpośredni następnik lub poprzednik
    while true do           // W pętli węzeł x przesuwamy do korzenia
    begin
      if x^.up = nil then break; // x jest korzeniem, kończymy

      if x^.up^.up = nil then
      begin                 // Ojcem x jest korzeń. Wykonujemy ZIG
        if x^.up^.left = x then rot_R ( root, x^.up )
        else                    rot_L ( root, x^.up );
        break;              // Kończymy
      end;

      if( x^.up^.up^.left = x^.up ) and ( x^.up^.left = x ) then
      begin                 // prawy ZIG-ZIG
        rot_R ( root, x^.up^.up );
        rot_R ( root, x^.up );
        continue;
      end;

      if( x^.up^.up^.right = x^.up ) and ( x^.up^.right = x ) then
      begin                 // lewy ZIG-ZIG
        rot_L ( root, x^.up^.up );
        rot_L ( root, x^.up );
        continue;
      end;

      if x^.up^.right = x then
      begin                // lewy ZIG, prawy ZAG
        rot_L ( root, x^.up );
        rot_R ( root, x^.up );
      end
      else
      begin                // prawy ZIG, lewy ZAG
        rot_R ( root, x^.up );
        rot_L ( root, x^.up );
      end;
    end;
  end;
end;

// Procedura wstawia do drzewa Splay nowy węzeł
// root - referencja do zmiennej przechowującej adres korzenia
// k    - klucz wstawianego węzła
//------------------------------------------------------------
procedure insertSplay ( var root : PBSTNode; k : integer );
var
  x : PBSTNode;
begin
  new ( x );               // Tworzymy nowy węzeł

  x^.left  := nil;         // Ustawiamy pola nowego węzła
  x^.right := nil;
  x^.key   := k;

  if root = nil then
  begin                    // Jeśli drzewo jest puste, 
    x^.up := nil;          // to węzeł x staje się korzeniem
    root  := x;
  end
  else
  begin
    splay ( root, k );         // W korzeniu pojawia się następnik lub poprzedni
    x^.up := root;         // Będzie on zawsze ojcem węzła x
    if k < root^.key then  // Wybieramy miejsce dla x
    begin
      x^.left := root^.left;
      root^.left := x;     // x staje się lewym synem korzenia
      if x^.left <> nil then x^.left^.up := x;
    end
    else
    begin
      x^.right := root^.right;
      root^.right := x;   // x staje się prawym synem korzenia
      if x^.right <> nil then x^.right^.up := x;
    end
  end;
end;

// Procedura usuwa węzeł z drzewa Splay
// root - referencja do zmiennej z adresem korzenia
// k    - klucz węzła do usunięcia
//-------------------------------------------------
procedure removeSplay ( var root : PBSTNode; k : integer );
var
  TL, TR : PBSTNode;
begin
  if root <> nil then
  begin
    splay ( root, k );    // Usuwany węzeł idzie do korzenia
    if root^.key = k then // Sprawdzamy, czy rzeczywiście tam trafił
    begin
      TL := root^.left;   // Zapamiętujemy synów węzła
      TR := root^.right;
      dispose ( root );   // Węzeł usuwamy z pamięci
      root := nil;        // Teraz drzewo jest puste
      if TL <> nil then   // Wybieramy niepuste poddrzewo
      begin
        TL^.up := nil;    // Teraz TL wskazuje korzeń
        splay ( TL, k );      // Do korzenia trafia poprzednik usuniętego węzła
        while TL^.right <> nil do rot_L ( TL, TL ); // idziemy na skraj drzewa
        TL^.right := TR;  // TR staje się prawym synem
        if TR <> nil then TR^.up := TL;
        root := TL;       // Uaktualniamy korzeń
      end
      else if TR <> nil then // Przypadek symetryczny dla TR
      begin
        TR^.up := nil;    // Teraz TR wskazuje korzeń
        splay ( TR, k );      // Do korzenia trafia następnik usuniętego węzła
        while TR^.left <> nil do rot_R ( TR, TR ); // idziemy na skraj drzewa
        TR^.left := TL;   // TL staje się lewym synem
        if TL <> nil then TL^.up := TR;
        root := TR;       // Uaktualniamy korzeń
      end;
    end
  end
end;

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

var
  T         : array [ 0..29 ] of integer;
  i, i1, i2, x : 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

  // W tablicy ustawiamy numery węzłów od 1 do 31

  for i := 0 to 29 do T [ i ] := i + 1;

  // Mieszamy tablicę

  for i := 0 to 300 do
  begin
    i1 := random ( 30 ); i2 := random ( 30 );
    x := T [ i1 ]; T [ i1 ] := T [ i2 ]; T [ i2 ] := x;
  end;

  // Wyświetlamy tablicę i tworzymy drzewo Splay

  for i := 0 to 29 do
  begin
    write ( T [ i ], ' ' );
    insertSplay ( root, T [ i ] );
  end;

  writeln; writeln;

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

  // Ponownie mieszamy tablicę

  for i := 0 to 300 do
  begin
    i1 := random ( 30 ); i2 := random ( 30 );
    x := T [ i1 ]; T [ i1 ] := T [ i2 ]; T [ i2 ] := x;
  end;

  // Usuwamy węzły

  writeln; writeln;

  for i := 0 to 9 do
  begin
    write ( T [ i ], ' ' );
    removeSplay ( root, T [ i ] );
  end;

  writeln; writeln;

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

  writeln; writeln;

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

end.
C++
// Wstawianie i usuwanie węzłów na drzewie Splay
// Data: 30.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ł
  }
}

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

// Procedura Splay
// root - korzeń drzewa
// k    - klucz
//---------------------
void splay ( BSTNode * & root, int k )
{
  BSTNode * x, *y;

  x = root;                 // Poszukujemy węzła o kluczu k, poczynając od korzenia
  if( x )
  {
    do
    {
      if( x->key == k ) break;
      y = x;                // Zapamiętujemy adres węzła
      x = k < x->key ? x->left: x->right;
    } while( x );

    if( !x ) x = y;         // Jeśli w drzewie nie ma takiego węzła, to za x
                            // bierzemy bezpośredni następnik lub poprzednik
    while( true )           // W pętli węzeł x przesuwamy do korzenia
    {
      if( !x->up ) break;   // x jest korzeniem, kończymy

      if( !x->up->up )
      {                     // Ojcem x jest korzeń. Wykonujemy ZIG
        if( x->up->left == x ) rot_R ( root, x->up );
        else                 rot_L ( root, x->up );
        break;              // Kończymy
      }

      if( ( x->up->up->left == x->up ) && ( x->up->left == x ) )
      {                     // prawy ZIG-ZIG
        rot_R ( root, x->up->up );
        rot_R ( root, x->up );
        continue;
      }

      if( ( x->up->up->right == x->up ) && ( x->up->right == x ) )
      {                    // lewy ZIG-ZIG
        rot_L ( root, x->up->up );
        rot_L ( root, x->up );
        continue;
      }

      if( x->up->right == x )
      {                    // lewy ZIG, prawy ZAG
        rot_L ( root, x->up );
        rot_R ( root, x->up );
      }
      else
      {                    // prawy ZIG, lewy ZAG
        rot_R ( root, x->up );
        rot_L ( root, x->up );
      }
    }
  }
}

// Procedura wstawia do drzewa Splay nowy węzeł
// root - referencja do zmiennej przechowującej adres korzenia
// k    - klucz wstawianego węzła
//------------------------------------------------------------
void insertSplay ( BSTNode * & root, int k )
{
  BSTNode * x = new BSTNode; // Tworzymy nowy węzeł

  x->left = x->right = NULL; // Ustawiamy pola nowego węzła
  x->key  = k;

  if( !root )
  {                         // Jeśli drzewo jest puste, 
    x->up = NULL;           // to węzeł x staje się korzeniem
    root  = x;
  }
  else
  {
    splay ( root, k );      // W korzeniu pojawia się następnik lub poprzedni
    x->up = root;           // Będzie on zawsze ojcem węzła x
    if( k < root->key )     // Wybieramy miejsce dla x
    {
      x->left = root->left;
      root->left = x;       // x staje się lewym synem korzenia
      if( x->left ) x->left->up = x;
    }
    else
    {
      x->right = root->right;
      root->right = x;      // x staje się prawym synem korzenia
      if( x->right ) x->right->up = x;
    }
  }
}

// Procedura usuwa węzeł z drzewa Splay
// root - referencja do zmiennej z adresem korzenia
// k    - klucz węzła do usunięcia
//-------------------------------------------------
void removeSplay ( BSTNode * & root, int k )
{
  BSTNode *TL, *TR;

  if( root )
  {
    splay ( root, k );    // Usuwany węzeł idzie do korzenia
    if( root->key == k )  // Sprawdzamy, czy rzeczywiście tam trafił
    {
      TL = root->left;    // Zapamiętujemy synów węzła
      TR = root->right;
      delete root;        // Węzeł usuwamy z pamięci
      root = NULL;        // Teraz drzewo jest puste
      if( TL )            // Wybieramy niepuste poddrzewo
      {
        TL->up = NULL;    // Teraz TL wskazuje korzeń
        splay ( TL, k );  // Do korzenia trafia poprzednik usuniętego węzła
        while( TL->right ) rot_L ( TL, TL ); // idziemy na skraj drzewa
        TL->right = TR;   // TR staje się prawym synem
        if( TR ) TR->up = TL;
        root = TL;        // Uaktualniamy korzeń
      }
      else if( TR )       // Przypadek symetryczny dla TR
      {
        TR->up = NULL;    // Teraz TR wskazuje korzeń
        splay ( TR, k );      // Do korzenia trafia następnik usuniętego węzła
        while( TR->left ) rot_R ( TR, TR ); // idziemy na skraj drzewa
        TR->left = TL;    // TL staje się lewym synem
        if( TL ) TL->up = TR;
        root = TR;        // Uaktualniamy korzeń
      }
    }
  }
}

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

int main( )
{
  int i, i1, i2, x, T [ 30 ];
  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

  // W tablicy ustawiamy numery węzłów od 1 do 31

  for( i = 0; i < 30; i++ ) T [ i ] = i + 1;

  // Mieszamy tablicę

  for( i = 0; i < 300; i++ )
  {
    i1 = rand( ) % 30; i2 = rand( ) % 30;
    x = T [ i1 ]; T [ i1 ] = T [ i2 ]; T [ i2 ] = x;
  }

  // Wyświetlamy tablicę i tworzymy drzewo Splay

  for( i = 0; i < 30; i++ )
  {
    cout << T [ i ] << " ";
    insertSplay ( root, T [ i ] );
  }

  cout << endl << endl;

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

  // Ponownie mieszamy tablicę

  for( i = 0; i < 300; i++ )
  {
    i1 = rand( ) % 30; i2 = rand( ) % 30;
    x = T [ i1 ]; T [ i1 ] = T [ i2 ]; T [ i2 ] = x;
  }

  // Usuwamy węzły

  cout << endl << endl;

  for( i = 0; i < 10; i++ )
  {
    cout << T [ i ] << " ";
    removeSplay ( root, T [ i ] );
  }

  cout << endl << endl;

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

  cout << endl << endl;

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

  return 0;
}
Basic
' Wstawianie i usuwanie węzłów na drzewie Splay
' Data: 30.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

' 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

' Procedura Splay
' root - korzeń drzewa
' k    - klucz
'---------------------
Sub splay ( ByRef root As BSTNode Ptr, ByVal k As Integer )
  Dim As BSTNode Ptr x, y

  x = root                  ' Poszukujemy węzła o kluczu k, poczynając od korzenia
  If x Then
    Do
      If x->key = k Then Exit Do
      y = x                 ' Zapamiętujemy adres węzła
      If k < x->key Then x = x->Left: Else x = x->right
    Loop Until x = 0

    if x = 0 Then x = y     ' Jeśli w drzewie nie ma takiego węzła, to za x
                            ' bierzemy bezpośredni następnik lub poprzednik
    While 1                 ' W pętli węzeł x przesuwamy do korzenia
      If x->up = 0 Then Exit While ' x jest korzeniem, kończymy

      If x->up->up = 0 Then ' Ojcem x jest korzeń. Wykonujemy ZIG
        If x->up->left = x Then rot_R ( root, x->up ): Else rot_L ( root, x->up )
        Exit While          ' Kończymy
      End If

      if( x->up->up->left = x->up ) AndAlso ( x->up->left = x ) Then
        rot_R ( root, x->up->up ) ' prawy ZIG-ZIG
        rot_R ( root, x->up )
        Continue While
      End If

      if( x->up->up->right = x->up ) AndAlso ( x->up->right = x ) Then
        rot_L ( root, x->up->up ) ' lewy ZIG-ZIG
        rot_L ( root, x->up )
        Continue While
      End If

      If x->up->right = x Then
        rot_L ( root, x->up ) ' lewy ZIG, prawy ZAG
        rot_R ( root, x->up )
      Else
        rot_R ( root, x->up ) ' prawy ZIG, lewy ZAG
        rot_L ( root, x->up )
      End If
    Wend
  End If
End Sub

' Procedura wstawia do drzewa Splay nowy węzeł
' root - referencja do zmiennej przechowującej adres korzenia
' k    - klucz wstawianego węzła
'------------------------------------------------------------
Sub insertSplay ( ByRef root As BSTNode Ptr, ByVal k As Integer )

  Dim As BSTNode Ptr x = new BSTNode ' Tworzymy nowy węzeł

  x->left  = 0              ' Ustawiamy pola nowego węzła
  x->right = 0
  x->key   = k

  If root = 0 Then
    x->up = 0               ' Jeśli drzewo jest puste,            
    root  = x               ' to węzeł x staje się korzeniem
  Else
    splay ( root, k )           ' W korzeniu pojawia się następnik lub poprzedni
    x->up = root            ' Będzie on zawsze ojcem węzła x
    If k < root->key Then   ' Wybieramy miejsce dla x
      x->left = root->Left
      root->left = x        ' x staje się lewym synem korzenia
      if x->Left Then x->left->up = x
    Else
      x->right = root->Right
      root->right = x       ' x staje się prawym synem korzenia
      if x->Right Then x->right->up = x
    End If
  End If
End Sub

' Procedura usuwa węzeł z drzewa Splay
' root - referencja do zmiennej z adresem korzenia
' k    - klucz węzła do usunięcia
'-------------------------------------------------
Sub removeSplay ( ByRef root As BSTNode Ptr, ByVal k As Integer )

  Dim As BSTNode Ptr TL, TR

  If root Then
    splay ( root, k )     ' Usuwany węzeł idzie do korzenia
    If root->key = k Then ' Sprawdzamy, czy rzeczywiście tam trafił
      TL = root->Left     ' Zapamiętujemy synów węzła
      TR = root->Right
      delete root         ' Węzeł usuwamy z pamięci
      root = 0            ' Teraz drzewo jest puste
      If TL Then     ' Wybieramy niepuste poddrzewo
        TL->up = 0        ' Teraz TL wskazuje korzeń
        splay ( TL, k )       ' Do korzenia trafia poprzednik usuniętego węzła
        While TL->Right: rot_L ( TL, TL ): Wend ' idziemy na skraj drzewa
        TL->right = TR    ' TR staje się prawym synem
        If TR Then TR->up = TL
        root = TL         ' Uaktualniamy korzeń
      ElseIf TR Then ' Przypadek symetryczny dla TR
        TR->up = 0        ' Teraz TR wskazuje korzeń
        splay ( TR, k )       ' Do korzenia trafia następnik usuniętego węzła
        While TR->Left: rot_R ( TR, TR ): Wend ' idziemy na skraj drzewa
        TR->left = TL     ' TL staje się lewym synem
        if TL then TL->up = TR
        root = TR         ' Uaktualniamy korzeń
      End If
    End If
  End If
End Sub

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

Dim As Integer i, i1, i2, x, T ( 29 )
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

' W tablicy ustawiamy numery węzłów od 1 do 31

For i = 0 To 29: T ( i ) = i + 1: Next

' Mieszamy tablicę

For i = 0 To 300
  i1 = Int ( rnd( ) * 30 ): i2 = Int ( rnd( ) * 30 )
  x = T ( i1 ): T ( i1 ) = T ( i2 ): T ( i2 ) = x
Next

' Wyświetlamy tablicę i tworzymy drzewo Splay

For i = 0 To 29
  Print T ( i );
  insertSplay ( root, T ( i ) )
Next

Print: Print

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

' Ponownie mieszamy tablicę

For i = 0 To 300
  i1 = Int ( rnd( ) * 30 ): i2 = Int ( rnd( ) * 30 )
  x = T ( i1 ): T ( i1 ) = T ( i2 ): T ( i2 ) = x
Next

' Usuwamy węzły

Print: Print

For i = 0 To 9
    print T ( i );
    removeSplay ( root, T ( i ) )
Next

Print: Print

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

Print: Print

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

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


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


1 23 29 22 30 10 12 20 25 21

   ┌─28
   │ │ ┌─27
   │ └─26
┌─24
19
│   ┌─18
│ ┌─17
│ │ └─16
│ │   │ ┌─15
│ │   └─14
│ │     └─13
└─11
  └─9
    │   ┌─8
    │   │ └─7
    │   │   └─6
    │   │     └─5
    │ ┌─4
    │ │ └─3
    └─2
Na początek:  podrozdziału   strony 

Zespół Przedmiotowy
Chemii-Fizyki-Informatyki

w I Liceum Ogólnokształcącym
im. Kazimierza Brodzińskiego
w Tarnowie
ul. Piłsudskiego 4
©2020 mgr Jerzy Wałaszek

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.