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

©2024 mgr Jerzy Wałaszek
I LO w Tarnowie

Drzewa Splay

SPIS TREŚCI W KONSERWACJI
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 (x→key) = 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 < (x→key),
to x ← (x→left)
inaczej x ← (x→right)		 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 (x→up) = nil,
to zakończ		 węzeł x znalazł się w korzeniu drzewa
K09: Jeśli (x→up→up) ≠ nil,
to idź do kroku K12		 badamy odpowiednie przypadki
K10: Jeśli (x→up→left) = x,
to rot_R (root, (x→up))
inaczej rot_L (root, (x→up))		 ojcem x jest korzeń. Rotacja ZIG umieszcza x w korzeniu drzewa
K11: Zakończ  
K12: Jeśli (x→up→up→left) ≠ (x→up) obrazek (x→up→left) ≠ x,
to idź do kroku K16		 badamy przypadek na ZIG-ZIG
K13: rot_R ( root, (x→up→up)) prawy ZIG z dziadkiem x
K14: rot_R ( root, (x→up)) prawy ZIG z ojcem x
K15: Idź do K08 kontynuujemy pętlę
K16: Jeśli (x→up→up→right) ≠ (x→up) obrazek (x→up→right) ≠ x,
to idź do kroku K20		 badamy przypadek na ZIG-ZIG
K17: rot_L ( root, (x→up→up)) lewy ZIG z dziadkiem x
K18: rot_L ( root, (x→up)) lewy ZIG z ojcem x
K19: Idź do K08  
K20: Jeśli (x→up→left) = x,
to idź do kroku K24		 ZIG-ZAG
K21: rot_L ( root, (x→up)) lewy ZIG z ojcem x
K22: rot_R ( root, (x→up)) prawy ZAG z pierwotnym dziadkiem x, teraz ojcem x
K23: Idź do kroku K08  
K24: rot_R ( root, (x→up)) przypadek lustrzanego odbicia ZIG-ZAG
K25: rot_L ( root, (x→up))  
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 (root→key) ≠ 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: (x→left) ← nil ustawiamy pola węzła
K04: (x→right) ← nil  
K05: (x→key) ← k  
K06: Jeśli root ≠ nil,
to idź do kroku K10		  
K07: (x→up) ← 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: (x→up) ← root ojcem x zawsze będzie korzeń
K12: Jeśli k < (root→key),
to idź do kroku K17		 sprawdzamy, gdzie umieścić x
K13: (x→right) ← ( root→right) x staje się prawym synem korzenia
K14: (root→right) ← x  
K15: Jeśli (x→right) ≠ nil,
to (x→right→up) ← x		 ojcem prawego syna korzenia staje się teraz węzeł x
K16: Zakończ  
K17: (x→left) ← ( root→left) x staje się lewym synem korzenia
K18: (root→left) ← x  
K19: Jeśli (x→left) ≠ nil,
to (x→left→up) ← 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 TL i TR. Jeśli oba poddrzewa TL i TR są puste, to kończymy. W przeciwnym razie mamy dwa poddrzewa (a właściwie przynajmniej jedno poddrzewo):

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

obrazek

Ponownie wykonujemy operację splay (TL, k) lub splay (TR, 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 TL
węzeł o minimalnym kluczu dla TR

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

w TL: do prawego syna y dołączamy poddrzewo TR
w TR: do lewego syna y dołączamy poddrzewo TL

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:
TL, TR  :  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 (root→key) ≠ k,
to zakończ		 w drzewie nie ma węzła o kluczu k
K04: TL ← (root→left) zapamiętujemy synów korzenia
K05: TR ← (root→right)  
K06: Usuń węzeł root z pamięci korzeń usuwamy
K07: root ← nil  
K08: Jeśli TL = nil, to idź do kroku K16 wybieramy istniejące poddrzewo
K09 (TL→up) ← nil TL jest korzeniem poddrzewa lewego
K10: splay (TL, k) istnieje TL, wykonujemy na nim operację splay
K11: Dopóki (TL→right) ≠ nil,
wykonuj rot_L (TL, TL)		 jeśli w drzewie są duplikaty, to przesuwamy się na skraj drzewa
K12: (TL→right) ← TR prawym synem staje się TR
K13: Jeśli TR ≠ nil,
to (TR→up) ← T L		 ojcem TR staje się T L
K14: root ← TL uaktualniamy korzeń
K15: Zakończ  
K16: Jeśli TR = nil,
to zakończ		 węzeł nie miał synów i drzewo jest teraz puste
K17 (TR→up) ← nil TR jest korzeniem poddrzewa prawego
K18: splay (TR, k) przypadek symetryczny dla TR
K19: Dopóki (TR→left) ≠ nil,
wykonuj rot_R (TR, TR)		  
K20: (TR→left) ← TL  
K21: Jeśli TL ≠ nil,
to (TL→up) ← T R		  
K22: root ← TR 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
©2024 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.