Algorytmy i Struktury Danych

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.

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):

Zasada nr 3 (zig-zag):

Jeśli ojciec y nie jest korzeniem, a węzły x i y są naprzemiennie lewym i prawym synem, 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:

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.

Elementy 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, ; drzewo jest puste, kończymy
     to zakończ
K03: Jeśli x→key = k, ; znaleźliśmy węzeł o kluczu k?
     to idź do kroku K08
K04: y ← x ; zapamiętujemy bieżący węzeł
K05: Jeśli k < x→key, 
     to x ← x→left       ; przechodzimy do
     inaczej x ← x→right ; syna węzła x
K06: Jeśli x ≠ nil, ; kontynuujemy wyszukiwanie
     to idź do kroku K03
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, ; węzeł x znalazł się
     to zakończ          ; w korzeniu drzewa?
K09: Jeśli x→up→up ≠ nil, ; badamy odpowiednie przypadki
     to idź do kroku K12
K10: Jeśli x→up→left = x, ; ojcem x jest korzeń?
     to rot_r(root, x→up)      ; Rotacja ZIG umieszcza x
     inaczej rot_l(root, x→up) ; w korzeniu drzewa
K11: Zakończ
K12: Jeśli x→up→up→left ≠ x→up 
           x→up→left ≠ x, ; badamy przypadek na ZIG-ZIG
     to idź do kroku K16
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 
           x→up→right ≠ x, ; badamy przypadek na ZIG-ZIG
     to idź do kroku K20
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, ; ZIG-ZAG
     to idź do kroku K24
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
  // łańcuchy do znaków ramek
  cr, cl, cp : string;

// Procedura wypisuje drzewo
//--------------------------
procedure print_bt(sp, sn : string;
                        v : PBSTnode);
var
  s : string;
  i : integer;
begin
  if v <> nil then
  begin
    s := sp;
    if sn = cr then
      s[length(s)-1] := ' ';
    print_bt(s+cp, cr, v^.right);
    s := Copy(sp, 1, length(sp)-2);
    for i := 1 to length(s) do
      write(char(ord(s[i])));
    for i := 1 to length(sn) do
      write(char(ord(sn[i])));
    writeln(v^.key);
    s := sp;
    if sn = cl then
      s[length(s)-1] := ' ';
    print_bt(s+cp, cl, v^.left);
  end;
end;

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

// Procedura wstawia do drzewa BST
// węzeł o kluczu k
//--------------------------------
procedure insert_bst(var root : PBSTnode;
                            k : integer);
var
  w, p : PBSTnode;
begin
  // Tworzymy dynamicznie nowy węzeł
  new(w);
  // Zerujemy wskazania synów
  w^.left  := nil;
  w^.right := nil;
  // Wyszukujemy miejsce dla w, 
  // rozpoczynając od korzenia
  p := root;
  // Drzewo puste?
  if p = nil then
    // Jeśli tak, to w
    // staje się korzeniem
    root := w
  else
    // Pętla nieskończona
    while true do
      // W zależności od klucza
      // idziemy do lewego lub
      // prawego syna, 
      // o ile takowy istnieje
      if k < p^.key then
      begin
        // Jeśli lewego syna nie ma, 
        if p^.left = nil then
        begin
          // to w staje się
          // lewym synem 
          p^.left := w;
          break; // Przerywamy pętlę
        end
        else p := p^.left;
      end
      else
      begin
        // Jeśli prawego syna nie ma, 
        if p^.right = nil then
        begin
          // to w staje się prawym synem 
          p^.right := w;
          break; // Przerywamy pętlę
        end
        else p := p^.right;
      end;
  // Rodzicem w jest zawsze p
  w^.up  := p;
  // Wstawiamy klucz
  w^.key := k;
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
  // Poszukujemy węzła o kluczu k, 
  // poczynając od korzenia
  x := root;
  if x <> nil then
  begin
    repeat
      if x^.key = k then break;
      // Zapamiętujemy adres węzła
      y := x;
      if k < x^.key then
        x := x^.left
      else
        x := x^.right;
    until x = nil;
    // Jeśli w drzewie nie ma takiego węzła, 
    // to za x bierzemy bezpośredni
    // następnik lub poprzednik
    if x = nil then x := y;
    // W pętli węzeł x przesuwamy do korzenia
    while true do
    begin
      // x jest korzeniem, kończymy
      if x^.up = nil then break;
      // Jeśli ojcem x jest korzeń, to
      // wykonujemy ZIG
      if x^.up^.up = nil then
      begin
        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;
  // korzeń drzewa BST
  root : PBSTnode;

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;
  // Tworzymy puste drzewo BST
  root := nil;
  a := 8; b := 16; c := a;
  // Drzewo wypełniamy węzłami
  for i := 1 to 15 do
  begin
    insert_bst(root, c);
    inc(c, b);
    if c > 16 then
    begin
      a := a shr 1;
      b := b shr 1;
      c := a;
    end;
  end;
  // Wyświetlamy drzewo
  print_bt('', '', root);
  // Losujemy klucz
  c := 1+random(15);
  writeln(c);
  // Operacja splay dla wylosowanego klucza
  splay(root, c);
  // Wyświetlamy drzewo
  print_bt('', '', root);
  // Usuwamy drzewo BST z pamięci
  dfs_release(root);
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
//-----------------

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

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

  if(v)
  {
    s = sp;
    if(sn == cr) s[s.length()-2] = ' ';
    print_bt(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] = ' ';
    print_bt(s+cp, cl, v->left);
  }
}

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

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

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

  // Zerujemy wskazania synów
  w->left = w->right = NULL;

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

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

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

  // Poszukujemy węzła o kluczu k, 
  // poczynając od korzenia
  x = root;
  if(x)
  {
    do
    {
      if(x->key == k) break;
      // Zapamiętujemy adres węzła
      y = x;
      x = k < x->key ? x->left:
                       x->right;
    } while(x);
    // Jeśli w drzewie nie ma
    // takiego węzła, to za x
    // bierzemy bezpośredni
    // następnik lub poprzednik
    if(!x) x = y;
    // W pętli węzeł x przesuwamy
    // do korzenia
    while(true)
    {
      // x jest korzeniem, kończymy
      if(!x->up) break;

      // Rodzicem x jest korzeń.
      // Wykonujemy ZIG
      if(!x->up->up)
      {
        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;

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

  a = c = 8;
  b = 16;
  // Drzewo wypełniamy węzłami
  for(i = 0; i < 15; i++)
  {
    insert_bst(root, c);
    c += b;
    if(c > 16)
    {
      a >>= 1;
      b >>= 1;
      c = a;
    }
  }
  // Wyświetlamy drzewo
  print_bt("", "", root);
  // Losujemy klucz
  c = 1+rand()%15;
  cout << c << endl;
  // Operacja splay
  // dla wylosowanego klucza
  splay(root, c);
  // Wyświetlamy drzewo
  print_bt("", "", root);
  // Usuwamy drzewo BST z pamięci
  dfs_release(root);
  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
'-----------------

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

' Procedura wypisuje drzewo
'--------------------------
Sub print_bt(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) = " "
    print_bt(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) = " "
    print_bt(s+cp, cl, v->Left)
  End If
End Sub

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

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

  ' Tworzymy dynamicznie nowy węzeł
  w = new BSTnode
  ' Zerujemy wskazania synów
  w->left  = 0
  w->right = 0
  ' Wyszukujemy miejsce dla w, 
  ' rozpoczynając od korzenia
  p = root
  ' Drzewo puste?
  If p = 0 Then
    ' Jeśli tak, to w staje się korzeniem
    root = w
  Else
    Do ' Pętla nieskończona
      ' W zależności od klucza idziemy
      ' do lewego lub prawego syna, 
      ' o ile takowy istnieje
      If k < p->key Then
        If p->Left = 0 Then
           ' Jeśli lewego syna nie ma, 
           ' to węzeł w staje się
           ' lewym synem 
           p->left = w
          Exit Do ' Przerywamy pętlę
        Else
          p = p->Left
        End If
      Else
        If p->Right = 0 Then
          ' Jeśli prawego syna nie ma, 
          ' to węzeł w staje się
          ' prawym synem 
          p->right = w
          Exit Do ' Przerywamy pętlę
        Else
          p = p->Right
        End If
      End If
    Loop ' Koniec pętli
  End If
  ' Rodzicem węzła w jest zawsze
  ' węzeł wskazywany przez p
  w->up  = p
  ' Wstawiamy klucz.
  ' Operacja jest zakończona.
  w->key = k
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

  ' Poszukujemy węzła o kluczu k, 
  ' poczynając od korzenia
  x = root
  If x Then
    Do
      If x->key = k Then Exit Do
      ' Zapamiętujemy adres węzła
      y = x
      If k < x->key Then
        x = x->Left
      Else
        x = x->right
      End If
    Loop Until x = 0
    ' Jeśli w drzewie nie ma
    ' takiego węzła, to za x
    ' bierzemy bezpośredni
    ' następnik lub poprzednik
    If x = 0 Then x = y
    ' W pętli węzeł x przesuwamy
    ' do korzenia
    While 1
      ' x jest korzeniem, kończymy
      If x->up = 0 Then Exit While
      ' Rodzicem x jest korzeń.
      ' Wykonujemy ZIG
      If x->up->up = 0 Then
        If x->up->left = x Then
          rot_r(root, x->up)
        Else
          rot_l(root, x->up)
        End If  
        Exit While ' Kończymy
      End If
      if(x->up->up->left = x->up) AndAlso _
        (x->up->left = x) Then
        ' prawy ZIG-ZIG
        rot_r(root, x->up->up)
        rot_r(root, x->up)
        Continue While
      End If
      If(x->up->up->right = x->up) AndAlso _
        (x->up->right = x) Then
        ' lewy ZIG-ZIG
        rot_l(root, x->up->up)
        rot_l(root, x->up)
        Continue While
      End If
      If x->up->right = x Then
        ' 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)
      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

a = 8: c = 8: b = 16
' Drzewo wypełniamy węzłami
For i = 1 To 15
  insert_bst(root, c)
  c += b
  If c > 16 Then
    a Shr= 1
    b Shr= 1
    c = a
  End If
Next
' Wyświetlamy drzewo
print_bt("", "", root)
' Losujemy klucz
c = 1+Int(Rnd()*15)
Print c
' Operacja splay dla
' wylosowanego klucza
splay(root, c)
' Wyświetlamy drzewo
print_bt("", "", root)
' Usuwamy drzewo BST
dfs_release(root)
End

Python (dodatek)

# Drzewo Splay
# Data: 31.07.2024
# (C)2024 mgr Jerzy Wałaszek
# ------------------------------

import random

# łańcuchy do tworzenia wykresu
cr = "┌─"
cl = "└─"
cp = "│ "


# klasa węzłów drzewa BST
class BSTnode:

    def __init__(self, k):
        self.up = None
        self.left = None
        self.right = None
        self.key = k


# wypisuje drzewo
def print_bt(sp, sn, v):
    global cl, cp, cr

    if v:
        s = sp
        if sn == cr:
            s = s[:-2] + ' ' + s[-1]
        print_bt(s + cp, cr, v.right)
        s = s[:-2]
        print(s, sn, v.key, sep="")
        s = sp
        if sn == cl:
            s = s[:-2] + ' ' + s[-1]
        print_bt(s + cp, cl, v.left)


# Procedura DFS:postorder
# usuwająca drzewo
def dfs_release(v):
    if v:
        # usuwamy lewe poddrzewo
        dfs_release(v.left)
        # usuwamy prawe poddrzewo
        dfs_release(v.right)
        # usuwamy odwołania
        v.left = None
        v.right = None


# Procedura wstawia do drzewa BST
# węzeł o kluczu k
# r - korzeń
# k - klucz
def insert_bst(r, k):
    # Tworzymy dynamicznie nowy węzeł
    w = BSTnode(k)
    # Wyszukujemy miejsce dla w, 
    # rozpoczynając od korzenia
    p = r
    # Drzewo puste?
    if not p:
        # Jeśli tak, to w staje się
        # korzeniem
        r = w
    else:
        while True:  # Pętla nieskończona
            # W zależności od klucza idziemy
            # do lewego lub prawego syna, 
            # o ile takowy istnieje
            if k < p.key:
                # Jeśli lewego syna nie ma, 
                if not p.left:
                    # to węzeł w staje się
                    # lewym synem 
                    p.left = w
                    break  # Przerywamy pętlę
                else:
                    p = p.left
            else:
                # Jeśli prawego syna nie ma, 
                if not p.right:
                    # to węzeł w staje się
                    # prawym synem 
                    p.right = w
                    break  # Przerywamy pętlę
                else:
                    p = p.right
    # Rodzicem węzła w jest zawsze węzeł
    # wskazywany przez p
    w.up = p
    return r


# Rotacja w lewo
# r - korzeń
def rot_l(r, a):
    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 is a:
                p.left = b
            else:
                p.right = b
        else:
            r = b
    return r


# Rotacja w prawo
# r - korzeń
def rot_r(r, a):
    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 is a:
                p.left = b
            else:
                p.right = b
        else:
            r = b
    return r


# Procedura Splay
# r - korzeń
# k - klucz
def splay(r, k):
    # Poszukujemy węzła o kluczu k, 
    # poczynając od korzenia
    x = r
    if x:
        while True:
            if x.key == k: break
            # Zapamiętujemy adres węzła
            y = x
            if k < x.key:
                x = x.left
            else:
                x = x.right
            if not x: break
        # Jeśli w drzewie nie ma
        # takiego węzła, to za x
        # bierzemy bezpośredni
        # następnik lub poprzednik
        if not x: x = y
        # W pętli węzeł x przesuwamy
        # do korzenia
        while True:
            # x jest korzeniem, kończymy
            if not x.up: break
            # Rodzicem x jest korzeń.
            # Wykonujemy ZIG
            if not x.up.up:
                if x.up.left is x:
                    r = rot_r(r, x.up)
                else:
                    r = rot_l(r, x.up)
                break  # Kończymy
            if (x.up.up.left is x.up) and \
                    (x.up.left is x):
                # prawy ZIG-ZIG
                r = rot_r(r, x.up.up)
                r = rot_r(r, x.up)
                continue
            if (x.up.up.right is x.up) and \
                    (x.up.right is x):
                # lewy ZIG-ZIG
                r = rot_l(r, x.up.up)
                r = rot_l(r, x.up)
                continue
            if x.up.right is x:
                # lewy ZIG, prawy ZAG
                r = rot_l(r, x.up)
                r = rot_r(r, x.up)
            else:
                # prawy ZIG, lewy ZAG
                r = rot_r(r, x.up)
                r = rot_l(r, x.up)
    return r


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Tworzymy puste drzewo BST
root = None
a, c, b = 8, 8, 16
# Drzewo wypełniamy węzłami
for i in range(15):
    root = insert_bst(root, c)
    c += b
    if c > 16:
        a >>= 1
        b >>= 1
        c = a
# Wyświetlamy drzewo
print_bt("", "", root)
# Losujemy klucz
c = random.randrange(1, 15)
print(c)
# Operacja splay dla
# wylosowanego klucza
root = splay(root, c)
# Wyświetlamy drzewo
print_bt("", "", root)
# Usuwamy drzewo BST
dfs_release(root)

Wynik:

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

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.

Elementy 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  (root→key) ≠ k, ; element nie został znaleziony, 
     to zakończ z wynikiem nil ; zwracamy wskazanie puste
K03: Zakończ z wynikiem root ; korzeń drzewa zawiera poszukiwany węzeł

do podrozdziału do strony

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 korzeniu 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).

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.

Elementy 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, ; sprawdzamy, gdzie umieścić x
     to idź do kroku K17
K13: x→right ← root→right ; x staje się prawym
     ; synem korzenia
K14: root→right ← x
K15: Jeśli x→right ≠ nil, ; ojcem prawego syna 
     to x→right→up ← x ; 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

do podrozdziału do strony

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.

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.

Elementy 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 root→key ≠ k, ; w drzewie nie ma węzła o kluczu k
     to zakończ
K04: T_L ← root→left ; 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, ; wybieramy istniejące poddrzewo
     to idź do kroku K16
K09: T_L→up ← nil ; T_L jest korzeniem poddrzewa lewego
K10: splay(T_L, k) ; istnieje T_L, wykonujemy na nim operację splay
K11: Dopóki T_L→right ≠ nil, 
     wykonuj rot_l(T_L, T_L) ; jeśli w drzewie są duplikaty, 
     ; to przesuwamy się na skraj drzewa
K12: T_L→right ← T_R ; prawym synem staje się T_RK13: Jeśli T_R ≠ nil, ; ojcem T_R staje się T_L
     to T_R→up ← T_LK14: root ← T_L; uaktualniamy korzeń
K15: Zakończ
K16: Jeśli T_R = nil, ; węzeł nie miał synów
     to zakończ ; i drzewo jest teraz puste
K17: T_R→up ← nil ; T_R jest korzeniem poddrzewa prawego
K18: splay(T_R, k) ; przypadek symetryczny dla T_RK19: Dopóki T_R→left ≠ nil, 
     wykonuj rot_r(T_R, T_R)
K20: T_R→left ← T_LK21: Jeśli T_L ≠ nil, 
     to T_L→up ← T_RK22: 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
  // łańcuchy do znaków ramek
  cr, cl, cp : string;

// Procedura wypisuje drzewo
//--------------------------
procedure print_bt(sp, sn : string;
                        v : PBSTnode);
var
  s : string;
  i : integer;
begin
  if v <> nil then
  begin
    s := sp;
    if sn = cr then s[length(s)-1] := ' ';
    print_bt(s+cp, cr, v^.right);
    s := Copy(sp, 1, length(sp)-2);
    for i := 1 to length(s) do
      write(char(ord(s[i])));
    for i := 1 to length(sn) do
      write(char(ord(sn[i])));
    writeln(v^.key);
    s := sp;
    if sn = cl then s[length(s)-1] := ' ';
    print_bt(s+cp, cl, v^.left);
  end;
end;

// Procedura DFS:postorder
// usuwająca drzewo
//------------------------
procedure dfs_release(v : PBSTnode);
begin
  if v <> nil then
  begin
    // usuwamy lewe poddrzewo
    dfs_release(v^.left);
    // usuwamy prawe poddrzewo
    dfs_release(v^.right);
    // usuwamy sam węzeł
    dispose(v);
  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
  // Poszukujemy węzła o kluczu k, 
  // poczynając od korzenia
  x := root;
  if x <> nil then
  begin
    repeat
      if x^.key = k then break;
      // Zapamiętujemy adres węzła
      y := x;
      if k < x^.key then
        x := x^.left
      else
        x := x^.right;
    until x = nil;
    // Jeśli w drzewie nie ma
    // takiego węzła, 
    // to za x bierzemy bezpośredni
    // następnik lub poprzednik
    if x = nil then x := y;
    // W pętli węzeł x przesuwamy
    // do korzenia
    while true do
    begin
      // x jest korzeniem, kończymy
      if x^.up = nil then break;
      // Jeśli ojcem x jest korzeń, to
      // wykonujemy ZIG
      if x^.up^.up = nil then
      begin
        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 insert_splay(var root : PBSTnode;
                             k : integer);
var
  x : PBSTnode;
begin
  // Tworzymy nowy węzeł
  new(x);
  // Ustawiamy pola nowego węzła
  x^.left  := nil;
  x^.right := nil;
  x^.key   := k;

  if root = nil then
  begin
    // Jeśli drzewo jest puste, 
    // to węzeł x staje się korzeniem
    x^.up := nil;
    root  := x;
  end
  else
  begin
    // W korzeniu pojawia się
    // następnik lub poprzedni
    splay(root, k);
    // Będzie on zawsze ojcem węzła x
    x^.up := root;
    // Wybieramy miejsce dla x
    if k < root^.key then
    begin
      x^.left := root^.left;
      // x staje się lewym synem korzenia
      root^.left := x;
      if x^.left <> nil then
        x^.left^.up := x;
    end
    else
    begin
      x^.right := root^.right;
      // x staje się prawym synem korzenia
      root^.right := x;
      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 remóve_splay(var root : PBSTnode;
                             k : integer);
var
  TL, TR : PBSTnode;
begin
  if root <> nil then
  begin
    // Usuwany węzeł idzie do korzenia
    splay(root, k);
    // Sprawdzamy, czy rzeczywiście
    // tam trafił
    if root^.key = k then
    begin
      // Zapamiętujemy synów węzła
      TL := root^.left;
      TR := root^.right;
      // Węzeł usuwamy z pamięci
      dispose(root);
      // Teraz drzewo jest puste
      root := nil;
      // Wybieramy niepuste poddrzewo
      if TL <> nil then
      begin
        // Teraz TL wskazuje korzeń
        TL^.up := nil;
        // Do korzenia trafia poprzednik
        // usuniętego węzła
        splay(TL, k);
        // idziemy na skraj drzewa
        while TL^.right <> nil do
          rot_l(TL, TL);
        // TR staje się prawym synem 
        TL^.right := TR;
        if TR <> nil then
          TR^.up := TL;
        // Uaktualniamy korzeń
        root := TL;
      end
      else
        // Przypadek symetryczny dla TR
        if TR <> nil then
        begin
          // Teraz TR wskazuje korzeń
          TR^.up := nil;
          // Do korzenia trafia następnik
          // usuniętego węzła
          splay(TR, k);
          while TR^.left <> nil do
            // idziemy na skraj drzewa
            rot_r(TR, TR);
          // TL staje się lewym synem 
          TR^.left := TL;
          if TL <> nil then
            TL^.up := TR;
          // Uaktualniamy korzeń
          root := TR;
        end;
      end
    end
  end;

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

var
  T : array [0..29] of integer;
  i, i1, i2, x : integer;
  // korzeń drzewa BST
  root : PBSTnode;

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;
  // Tworzymy puste drzewo BST
  root := nil;
  // 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], ' ');
    insert_splay(root, T[i]);
  end;
  writeln;
   // Wyświetlamy drzewo
  print_bt('', '', root);
  writeln; writeln;
  // 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
  for i := 0 to 9 do
  begin
    write(T[i], ' ');
    remóve_splay(root, T[i]);
  end;
  writeln; writeln;
  // Wyświetlamy drzewo
  print_bt('', '', root);
  // Usuwamy drzewo BST z pamięci
  dfs_release(root);
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
//-----------------

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

// Procedura wypisuje drzewo
//--------------------------
void print_bt(string sp, 
             string sn, 
             BSTnode * v)
{
  string s;
  if(v)
  {
    s = sp;
    if(sn == cr)
      s[s.length()-2] = ' ';
    print_bt (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] = ' ';
    print_bt (s+cp, cl, v->left);
  }
}

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

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

  // Poszukujemy węzła o kluczu k, 
  // poczynając od korzenia
  x = root;
  if(x)
  {
    do
    {
      if(x->key == k) break;
      // Zapamiętujemy adres węzła
      y = x;
      x = k < x->key ? x->left:
                       x->right;
    } while(x);
    // Jeśli w drzewie nie ma
    // takiego węzła, to za x
    // bierzemy bezpośredni
    // następnik lub poprzednik
    if(!x)
      x = y;
    // W pętli węzeł x przesuwamy
    // do korzenia
    while(true)
    {
      // x jest korzeniem? Kończymy
      if(!x->up) break;
      // Rodzicem x jest korzeń?
      // Wykonujemy ZIG
      if(!x->up->up)
      {
        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 insert_splay(BSTnode * & root, 
                 int k)
{
  // Tworzymy nowy węzeł
  BSTnode * x = new BSTnode;

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

  // Jeśli drzewo jest puste, 
  if(!root)
  {
    // to węzeł x staje się korzeniem
    x->up = NULL;
    root  = x;
  }
  else
  {
    // W korzeniu pojawia się
    // następnik lub poprzednik
    splay (root, k);
    // Będzie on zawsze
    // ojcem węzła x
    x->up = root;
    // Wybieramy miejsce dla x
    if(k < root->key)
    {
      x->left = root->left;
      // x staje się lewym
      // `synem korzenia
      root->left = x;
      if(x->left) x->left->up = x;
    }
    else
    {
      x->right = root->right;
      // x staje się prawym
      // korzeniem korzenia
      root->right = x;
      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 remóve_splay(BSTnode * & root, 
                 int k)
{
  BSTnode *TL, *TR;

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

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

int main()
{
  int i, i1, i2, 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));

  // 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;
    swap(T[i1], T[i2]);
  }
  // Wyświetlamy tablicę
  // i tworzymy drzewo Splay
  for(i = 0; i < 30; i++)
  {
    cout << T[i] << " ";
    insert_splay(root, T[i]);
  }
  cout << endl << endl;
  // Wyświetlamy drzewo
  print_bt("", "", root);
  // Ponownie mieszamy tablicę
  for(i = 0; i < 300; i++)
  {
    i1 = rand()%30;
    i2 = rand()%30;
    swap(T[i1], T[i2]);
  }
  // Usuwamy węzły
  cout << endl << endl;
  for(i = 0; i < 10; i++)
  {
    cout << T[i] << " ";
    remóve_splay(root, T[i]);
  }
  cout << endl << endl;
  // Wyświetlamy drzewo
  print_bt("", "", root);
  cout << endl << endl;
  // Usuwamy drzewo BST z pamięci
  dfs_release(root);
  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
'-----------------

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

' Procedura wypisuje drzewo
'--------------------------
Sub print_bt(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) = " "
    print_bt(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) = " "
    print_bt(s+cp, cl, v->Left)
  End If
End Sub

' Procedura DFS:postorder
' usuwająca drzewo
'------------------------
Sub dfs_release(v As BSTnode Ptr)
  If v Then
    ' usuwamy lewe poddrzewo
    dfs_release(v->left)
    ' usuwamy prawe poddrzewo
    dfs_release(v->right)
    ' usuwamy sam węzeł
    delete v
  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

  ' Poszukujemy węzła o kluczu k, 
  ' poczynając od korzenia
  x = root
  If x Then
    Do
      If x->key = k Then Exit Do
      ' Zapamiętujemy adres węzła
      y = x
      If k < x->key Then
        x = x->Left
      Else
        x = x->right
      End If
    Loop Until x = 0
    ' Jeśli w drzewie nie ma
    ' takiego węzła, to za x
    ' bierzemy bezpośredni
    ' następnik lub poprzednik
    If x = 0 Then x = y
    ' W pętli węzeł x
    ' przesuwamy do korzenia
    While 1
      ' x jest korzeniem, kończymy
      If x->up = 0 Then Exit While
      ' Rodzicem x jest korzeń.
      ' Wykonujemy ZIG
      If x->up->up = 0 Then
        If x->up->left = x Then
          rot_r(root, x->up)
        Else
          rot_l(root, x->up)
        End If
        Exit While ' Kończymy
      End If
      if(x->up->up->left = x->up) AndAlso _
        (x->up->left = x) Then
        ' prawy ZIG-ZIG
        rot_r(root, x->up->up)
        rot_r(root, x->up)
        Continue While
      End If
      if(x->up->up->right = x->up) AndAlso _
        (x->up->right = x) Then
        ' lewy ZIG-ZIG
        rot_l(root, x->up->up)
        rot_l(root, x->up)
        Continue While
      End If
      If x->up->right = x Then
        ' 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)
      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 insert_splay(ByRef root As BSTnode Ptr, _
                ByVal k As Integer)
  ' Tworzymy nowy węzeł
  Dim As BSTnode Ptr x = new BSTnode

  ' Ustawiamy pola nowego węzła
  x->left  = 0
  x->right = 0
  x->key   = k
  If root = 0 Then
    ' Jeśli drzewo jest puste,           
    x->up = 0
    ' to węzeł x staje się korzeniem
    root  = x
  Else
    ' W korzeniu pojawia się
    ' następnik lub poprzedni
    splay(root, k)
    ' Będzie on zawsze ojcem węzła x
    x->up = root
    ' Wybieramy miejsce dla x
    If k < root->key Then
      x->left = root->Left
      ' x staje się lewym synem korzenia
      root->left = x
      if x->Left Then x->left->up = x
    Else
      x->right = root->Right
      ' x staje się prawym synem korzenia
      root->right = x
      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 remóve_splay(ByRef root As BSTnode Ptr, _
                ByVal k As Integer)
  Dim As BSTnode Ptr TL, TR

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

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

Dim As Integer i, i1, i2, 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

' 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)
  Swap T(i1), T(i2)
Next
' Wyświetlamy tablicę
'i tworzymy drzewo Splay
For i = 0 To 29
  Print T(i);
  insert_splay(root, T(i))
Next
Print: Print
' Wyświetlamy drzewo
print_bt("", "", root)
' Ponownie mieszamy tablicę
For i = 0 To 300
  i1 = Int(rnd()*30)
  i2 = Int(rnd()*30)
  Swap T(i1), T(i2)
Next
' Usuwamy węzły
Print: Print
For i = 0 To 9
  Print T(i);
  remóve_splay(root, T(i))
Next
Print: Print
' Wyświetlamy drzewo
print_bt("", "", root)
Print: Print
' Usuwamy drzewo BST z pamięci
dfs_release(root)
End

Python (dodatek)

# Wstawianie i usuwanie
# węzłów na drzewie Splay
# Data: 2.08.2024
# (C)2024 mgr Jerzy Wałaszek
# ------------------------------

import random

# łańcuchy do tworzenia wykresu
cr = "┌─"
cl = "└─"
cp = "│ "


# klasa węzłów drzewa BST
class BSTnode:

    def __init__(self, k):
        self.up = None
        self.left = None
        self.right = None
        self.key = k


# wypisuje drzewo
def print_bt(sp, sn, v):
    global cl, cp, cr

    if v:
        s = sp
        if sn == cr:
            s = s[:-2] + ' ' + s[-1]
        print_bt(s + cp, cr, v.right)
        s = s[:-2]
        print(s, sn, v.key, sep="")
        s = sp
        if sn == cl:
            s = s[:-2] + ' ' + s[-1]
        print_bt(s + cp, cl, v.left)


# Procedura DFS:postorder
# usuwająca drzewo
def dfs_release(v):
    if v:
        # usuwamy lewe poddrzewo
        dfs_release(v.left)
        # usuwamy prawe poddrzewo
        dfs_release(v.right)
        # usuwamy odwołania
        v.left = None
        v.right = None


# Rotacja w lewo
# r - korzeń
def rot_l(r, a):
    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 is a:
                p.left = b
            else:
                p.right = b
        else:
            r = b
    return r


# Rotacja w prawo
# r - korzeń
def rot_r(r, a):
    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 is a:
                p.left = b
            else:
                p.right = b
        else:
            r = b
    return r


# Procedura Splay
# r - korzeń
# k - klucz
def splay(r, k):
    # Poszukujemy węzła o kluczu k,
    # poczynając od korzenia
    x = r
    if x:
        while True:
            if x.key == k: break
            # Zapamiętujemy adres węzła
            y = x
            if k < x.key:
                x = x.left
            else:
                x = x.right
            if not x: break
        # Jeśli w drzewie nie ma
        # takiego węzła, to za x
        # bierzemy bezpośredni
        # następnik lub poprzednik
        if not x: x = y
        # W pętli węzeł x przesuwamy
        # do korzenia
        while True:
            # x jest korzeniem, kończymy
            if not x.up: break
            # Rodzicem x jest korzeń.
            # Wykonujemy ZIG
            if not x.up.up:
                if x.up.left is x:
                    r = rot_r(r, x.up)
                else:
                    r = rot_l(r, x.up)
                break  # Kończymy
            if (x.up.up.left is x.up) and \
                    (x.up.left is x):
                # prawy ZIG-ZIG
                r = rot_r(r, x.up.up)
                r = rot_r(r, x.up)
                continue
            if (x.up.up.right is x.up) and \
                    (x.up.right is x):
                # lewy ZIG-ZIG
                r = rot_l(r, x.up.up)
                r = rot_l(r, x.up)
                continue
            if x.up.right is x:
                # lewy ZIG, prawy ZAG
                r = rot_l(r, x.up)
                r = rot_r(r, x.up)
            else:
                # prawy ZIG, lewy ZAG
                r = rot_r(r, x.up)
                r = rot_l(r, x.up)
    return r


# Procedura wstawia do
# drzewa Splay nowy węzeł
# r - korzeń
# k - klucz
def insert_splay(r, k):
    # Tworzymy nowy węzeł
    x = BSTnode(k)
    if not r:
        # Jeśli drzewo jest puste,
        # to węzeł x staje się korzeniem
        r = x
    else:
        # W korzeniu pojawia się
        # następnik lub poprzedni
        r = splay(r, k)
        # Będzie on zawsze ojcem węzła x
        x.up = r
        # Wybieramy miejsce dla x
        if k < r.key:
            x.left = r.left
            # x staje się lewym synem korzenia
            r.left = x
            if x.left: x.left.up = x
        else:
            x.right = r.right
            # x staje się prawym synem korzenia
            r.right = x
            if x.right: x.right.up = x
    return r


# Procedura usuwa węzeł z drzewa Splay
# r - korzeń
# k - klucz
def remove_splay(r, k):
    if r:
        # Usuwany węzeł idzie do korzenia
        r = splay(r, k)
        # Sprawdzamy, czy rzeczywiście tam trafił
        if r.key == k:
            # Zapamiętujemy synów węzła
            tl = r.left
            tr = r.right
            # Teraz drzewo jest puste
            r = None
            # Wybieramy niepuste poddrzewo
            if tl:
                # Teraz tl wskazuje korzeń
                tl.up = None
                # Do korzenia trafia
                # poprzednik usuniętego węzła
                tl = splay(tl, k)
                # idziemy na skraj drzewa
                while tl.right: tl = rot_l(tl, tl)
                # tr staje się prawym synem
                tl.right = tr
                if tr: tr.up = tl
                # Uaktualniamy korzeń
                r = tl
            # Przypadek symetryczny dla tr
            elif tr:
                # Teraz tr wskazuje korzeń
                tr.up = None
                # Do korzenia trafia
                # następnik usuniętego węzła
                tr = splay(tr, k)
                # idziemy na skraj drzewa
                while tr.left: tr = rot_r(tr, tr)
                # tl staje się lewym synem
                tr.left = tl
                if tl: tl.up = tr
                # Uaktualniamy korzeń
                r = tr
    return r


# **********************
# *** PROGRAM GŁÓWNY ***
# **********************

# Puste drzewo
root = None
# W tablicy ustawiamy numery
# węzłów od 1 do 31
t = [i + 1 for i in range(30)]
# Mieszamy tablicę
for i in range(300):
    i1 = random.randrange(30)
    i2 = random.randrange(30)
    t[i1], t[i2] = t[i2], t[i1]
# Wyświetlamy tablicę
# i tworzymy drzewo Splay
for i in range(30):
    print(t[i], end=" ")
    root = insert_splay(root, t[i])
print()
print()
# Wyświetlamy drzewo
print_bt("", "", root)
# Ponownie mieszamy tablicę
for i in range(300):
    i1 = random.randrange(30)
    i2 = random.randrange(30)
    t[i1], t[i2] = t[i2], t[i1]
# Usuwamy węzły
print()
print()
for i in range(10):
    print(t[i], end=" ")
    root = remove_splay(root, t[i])
print()
print()
# Wyświetlamy drzewo
print_bt("", "", root)
print()
print()
# Usuwamy drzewo BST z pamięci
dfs_release(root)

Wynik:

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

    ┌─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


2 1 23 15 24 17 3 21 8 4

          ┌─30
        ┌─29
        │ │ ┌─28
        │ │ │ └─27
        │ └─26
        │   └─25
      ┌─22
    ┌─20
    │ │   ┌─19
    │ │   │ └─18
    │ │ ┌─16
    │ └─14
    │   │ ┌─13
    │   └─12
    │     │   ┌─11
    │     │ ┌─10
    │     └─9
  ┌─7
┌─6
5

do podrozdziału do strony

Materiały tylko do użytku dydaktycznego. Ich kopiowanie i powielanie jest dozwolone pod warunkiem podania źródła oraz niepobierania za to pieniędzy.
Pytania proszę przesyłać na adres email: i-lo@eduinf.waw.pl
Serwis wykorzystuje pliki cookies. Jeśli nie chcesz ich otrzymywać, zablokuj je w swojej przeglądarce.

Informacje dodatkowe.

Drzewa Splay

Wiadomości podstawowe

Operacja Splay

Zasada nr 1 (zig):

Zasada nr 2 (zig-zig):

Zasada nr 3 (zig-zag):

Algorytm operacji splay

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Wyszukiwanie węzłów w drzewie Splay

Algorytm wyszukiwania węzła w drzewie Splay

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Wstawianie węzła do drzewa Splay

Algorytm wstawiania węzła do drzewa Splay

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Usuwanie węzła z drzewa Splay

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

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy