Algorytmy i Struktury Danych

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

Rotacja w prawo

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

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

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

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

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

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

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

Algorytm rotacji w prawo drzewa BST

Wejście:

root : referencja do zmiennej przechowującej adres korzenia drzewa BST.
A : wskazanie węzła A.

Wyjście:

Drzewo BST, na którym została wykonana rotacja w prawo względem węzła A.

Elementy pomocnicze:

B : wskazanie węzła B.
p : wskazanie ojca węzła A.

Lista kroków:

K01: B ← A→left ; w B umieszczamy adres
                  ; lewego syna węzła A
K02: Jeśli B = nil, ; nie można wykonać rotacji
     to zakończ
K03: p ← A→up ; w p umieszczamy ojca węzła A
K04: A→left ← B→right ; lewym synem A
     ; staje się prawy syn B
K05: Jeśli A→left ≠ nil, ; jeśli lewy syn istnieje, 
     to A→left→up ← A ; to jego ojcem jest teraz A
K06: B→right ← A ; prawym synem B staje się A
K07: B→up ← p ; ojcem B jest ojciec węzła A
K08: A→up ← B ; natomiast A zmienia ojca na B
K09: Jeśli p = nil, ; sprawdzamy, czy węzeł A był korzeniem
     to idź do kroku K12
K10: Jeśli p→left = A, ; jeśli nie, to uaktualniamy jego ojca 
     to p→left ← B
     inaczej p→right ← B
K11: Zakończ
K12: root ← B ; jeśli A był korzeniem, 
     ; to uaktualniamy korzeń
K13: Zakończ

Rotacja w lewo

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

Algorytm rotacji w lewo drzewa BST

Wejście:

root : referencja do zmiennej przechowującej adres korzenia drzewa BST.
A : wskazanie węzła A.

Wyjście:

Drzewo BST, na którym została wykonana rotacja w lewo względem węzła A.

Elementy pomocnicze:

B : wskazanie węzła B.
p : wskazanie ojca A.

Lista kroków:

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

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program tworzy drzewo BST o 15 węzłach, a następnie dokonuje rotacji:

lewego poddrzewa korzenia w lewo
prawego poddrzewa korzenia w prawo

Program prezentuje wyniki w oknie konsoli.

Pascal

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

program bst;

// Typ węzłów drzewa BST
type
  PBSTnode = ^BSTnode;
  BSTnode  = record
    up, left, right : PBSTnode;
    key : integer;
  end;

// Zmienne globalne

var
  // ł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;
  // Wstawiamy klucz
  w^.key := k;
  // 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
      if k < p^.key then
      // prawego syna, 
      // o ile takowy istnieje
      begin
        // Jeśli lewego syna nie ma, 
        if p^.left = nil then
        begin
          // to w staje się lewym synem 
          p^.left := w;
          // Przerywamy pętlę while
          break;
        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;
          // Przerywamy pętlę while
          break;
        end
        else
          p := p^.right;
      end;
  // Rodzicem w jest zawsze p
  w^.up  := p;
end;

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

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

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

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

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

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

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

var
  i    : integer;
  // 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;

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

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

  writeln; writeln;

  // Dokonujemy rotacji lewego
  // poddrzewa w lewo, 
  // jeśli istnieje
  if root^.left <> nil then
    rot_l(root, root^.left);

  // Dokonujemy rotacji prawego
  // poddrzewa w prawo, 
  // jeśli istnieje
  if root^.right <> nil then
    rot_r(root, root^.right);

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

  writeln; writeln;

  // Usuwamy drzewo BST z pamięci
  dfs_release (root);
end.

C++

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

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

using namespace std;

// Typ węzłów drzewa BST
struct BSTnode
{
  BSTnode *up, *left, *right;
  int key;
};

// Zmienne globalne

// ł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 obu synów
  w->left = w->right = NULL;
  // Wstawiamy klucz
  w->key = k;

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

  if(!p) // Drzewo puste?
    // 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;
}

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

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

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

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

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

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

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

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

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

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

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

  // cl = |
  //      +--

  // cp = |
  //      |

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

  srand(time(NULL));

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

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

  cout << endl << endl;

  // Dokonujemy rotacji lewego poddrzewa
  // w lewo, jeśli istnieje
  if(root->left)
    rot_l(root, root->left);

  // Dokonujemy rotacji prawego poddrzewa
  // w prawo, jeśli istnieje
  if(root->right)
    rot_r(root, root->right);

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

  cout << endl << endl;

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

  return 0;
}

Basic

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

' Typ węzłów drzewa BST
Type BSTnode
  up    As BSTnode Ptr
  left  As BSTnode Ptr
  right As BSTnode Ptr
  key As Integer
End Type

' Zmienne globalne

' ł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
  ' Wstawiamy klucz
  w->key = k

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

  If p = 0 Then ' Drzewo puste?
    ' 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
        ' Jeśli lewego syna nie ma, 
        If p->Left = 0 Then
          ' to węzeł w staje się
          ' lewym synem 
          p->left = w
          Exit Do ' Przerywamy pętlę
        Else
          p = p->Left
        End If
      Else
        ' Jeśli prawego syna nie ma, 
        If p->Right = 0 Then
          ' 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
End Sub

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

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

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

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

' Rotacja w prawo
'----------------
Sub rot_r(ByRef root As BSTnode Ptr, _
          ByVal A As BSTnode Ptr)

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

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

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

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

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

Dim As Integer i
Dim As BSTnode Ptr root = 0

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

' cl = |
'      +--

' cp = |
'      |

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

Randomize

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

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

Print: Print

' Dokonujemy rotacji lewego poddrzewa
' w lewo, jeśli istnieje
If root->Left Then _
  rot_l(root, root->left)

' Dokonujemy rotacji prawego poddrzewa
' w prawo, jeśli istnieje
if root->right Then _
  rot_r(root, root->right)

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

Print: Print

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

End

Python (dodatek)

# Rotacje drzewa BST
# Data: 16.07.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random


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


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


# zmienne globalne
#-----------------

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


# procedura wypisuje drzewo
#--------------------------
def print_bt(sp, sn, v):
    global cr, cl, cp
    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 BST
#------------------------
def dfs_release(v):
    if v:
        # usuwamy lewe poddrzewo
        dfs_release(v.left)
        # usuwamy prawe poddrzewo
        dfs_release(v.right)
        # usuwamy odwołania
        v.up    = None
        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


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

# Korzeń
root = None
# Drzewo wypełniamy węzłami
for i in range(15):
    k = random.randrange(10, 100)
    root = insert_bst(root, k)
# wyświetlamy drzewo
print_bt("", "", root)
print()
print()
# Dokonujemy rotacji lewego poddrzewa
# w lewo, jeśli istnieje
if root.left:
    root = rot_l(root, root.left)
# Dokonujemy rotacji prawego poddrzewa
# w prawo, jeśli istnieje
if root.right:
    root = rot_r(root, root.right)
# wyświetlamy drzewo
print_bt("", "", root)
# Usuwamy drzewo BST z pamięci
dfs_release(root)

Wynik:

┌─99
│ │ ┌─96
│ │ │ └─92
│ │ │   │ ┌─91
│ │ │   │ │ └─89
│ │ │   └─89
│ └─66
│   └─57
│     │ ┌─47
│     └─35
35
│   ┌─34
│ ┌─23
└─20
  └─16


  ┌─99
  │ └─96
  │   └─92
  │     │ ┌─91
  │     │ │ └─89
  │     └─89
┌─66
│ └─57
│   │ ┌─47
│   └─35
35
│ ┌─34
└─23
  └─20
    └─16

do podrozdziału do strony

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

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

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

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

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

Algorytm DSW wymaga wyznaczenia liczby:

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

Na przykład:

n = 20
n+1 = 21 = 10101₂ → 10000₂ → 16

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

Algorytm wyznaczania wartości 2^|_log2^x_|

Wejście:

x : wartość, dla której liczymy potęgę, x ∈ N.

Wyjście:

y : wynik

Lista kroków:

K01: y ← 1 ; wartość początkowa potęgi
K02: x ← x shr 1 ; przesuwamy wstępnie bity
     ; w x o 1 pozycję w prawo
K03: Dopóki x > 0, 
     wykonuj kroki K4…K5
K04:   y ← y shl 1 ; bit 1 przesuwamy
       ; w y o jedną pozycję w lewo
K05:   x ← x shr 1 ; bity w x przesuwamy
       ; o jedną pozycję w prawo
K06: Zakończ ; koniec, wynik w y

Algorytm DSW – zrównoważanie drzewa BST - rebalance_dsw(root)

Wejście:

root : referencja do zmiennej, która przechowuje adres korzenia drzewa BST.

Wyjście:

Zrównoważone drzewo BST

Elementy pomocnicze:

p : wskazanie węzła.
n : licznik wierszy, n ∈ N.
s : licznik obrotów, s ∈ N.
i : licznik, i ∈ N.
rot_l(root, w) : procedura obrotu w lewo względem węzła w.
rot_r(root, w) : procedura obrotu w prawo względem węzła w.
log2(x) : Oblicza wartość 2^|^_^log2^x_|

Lista kroków:

K01: n ← 0 ; zerujemy licznik węzłów
K02: p ← root ; rozpoczynamy tworzenie listy
     ; liniowej
K03: Dopóki p ≠ nil, ; przetwarzamy drzewo
     wykonuj kroki K04…K09 ; począwszy od korzenia
K04:   Jeśli p→left = nil, ; sprawdzamy, czy 
       to idź do K08 ; węzeł posiada lewego syna 
K05:   rot_r(root, p) ; jeśli tak, to wykonujemy
       ; obrót w prawo
K06:   p ← p→up ; wracamy do właściwego węzła
       ; po obrocie
K07:   Kontynuuj pętlę K03
K08:   n ← n+1 ; jeśli nie, to zwiększamy
       ; licznik węzłów
K09:   p ← p→right ; i przesuwamy się w dół
       ; do prawego syna 
K10: s ← n+1-log2(n+1) ; wyznaczamy liczbę
     ; liści na najniższym poziomie
K11: p ← root ; przekształcamy listę w drzewo BST
K12: Dla i = 1, 2, …, s:   ; za pomocą odpowiedniej liczby
     wykonuj kroki K13…K14
K13:   rot_l(root, p)    ; obrotów w lewo
K14:   p ← p→up→right ; co drugiego węzła na liście
K15: n ← n-s ; pomniejszamy liczbę węzłów o ilość liści
K16: Dopóki n > 1: ; tworzymy drzewo BST
     wykonuj kroki K17…K21
K17:   n ← n shr 1 ; n zmniejszamy do połowy
K18:   p ← root ; zawsze rozpoczynamy od korzenia drzewa
K19:   Dla i = 1, 2, …, n:
       wykonuj kroki K20…K21
K20:     rot_l(root, p) ; obrót w lewo
K21:     p ← p→up→right ; następny węzeł do obracania
K22: Zakończ

Przykładowe programy

Uwaga:

Zanim uruchomisz program, przeczytaj wstęp do tego artykułu, w którym wyjaśniamy funkcje tych programów oraz sposób korzystania z nich.

Program tworzy drzewo BST zbudowane z 15 węzłów o losowych kluczach od 1 do 9. Następnie równoważy to drzewo za pomocą algorytmu DSW.

Pascal

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

program bst;

// Typ węzłów drzewa BST
type
  PBSTnode = ^BSTnode;
  BSTnode  = record
    up, left, right : PBSTnode;
    key : integer;
  end;

// Zmienne globalne

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

  if p = nil then // Drzewo puste?
    // Jeśli tak, to w staje
    // się korzeniem
    root := w
  else
    while true 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
      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ę while
        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ę while
        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;

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

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

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

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

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

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

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

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

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

  writeln; writeln;

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

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

  writeln; writeln;

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

end.

C++

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

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

using namespace std;

// Typ węzłów drzewa BST
struct BSTnode
{
  BSTnode *up, *left, *right;
  int key;
};

// Zmienne globalne

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

  if(!p) // Drzewo puste?
    // 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;
          break; // Przerywamy pętlę while
        }
        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;
          break; // Przerywamy pętlę while
        }
        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;
  }
}

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

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

  return y;
}

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

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

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

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

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

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

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

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

  // cl = |
  //      +--

  // cp = |
  //      |

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

  srand(time(NULL));

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

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

  cout << endl << endl;

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

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

  cout << endl << endl;

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

  return 0;
}

Basic

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

' Typ węzłów drzewa BST
Type BSTnode
  up    As BSTnode Ptr
  Left  As BSTnode Ptr
  Right As BSTnode Ptr
  key As Integer
End Type

' Zmienne globalne

' ł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

  If p = 0 Then ' Drzewo puste?
    ' 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
        ' Jeśli lewego syna nie ma, 
        ' to węzeł w staje się
        ' lewym synem 
        If p->Left = 0 Then
          p->left = w
          Exit Do ' Przerywamy pętlę
        Else
          p = p->Left
        End If
      Else
        ' Jeśli prawego syna nie ma, 
        If p->Right = 0 Then
          ' 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

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

  log2 = y
End Function

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

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

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

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

  ' Wyznaczamy kolejne liczby obrotów
  n -= s

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

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

Dim As Integer i
Dim As BSTnode Ptr root = 0

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

' cl = |
'      +--

' cp = |
'      |

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

Randomize

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

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

Print: Print

' Równoważymy drzewo
rebalance_dsw(root)

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

Print: Print

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

End

Python (dodatek)

# algorytm DSW
# Data: 19.07.2024
# (C)2024 mgr Jerzy Wałaszek
#---------------------------

import random


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


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

# zmienne globalne
#-----------------

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


# procedura wypisuje drzewo
#--------------------------
def print_bt(sp, sn, v):
    global cr, cl, cp
    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 BST
#------------------------
def dfs_release(v):
    if v:
        # usuwamy lewe poddrzewo
        dfs_release(v.left)
        # usuwamy prawe poddrzewo
        dfs_release(v.right)
        # usuwamy odwołania
        v.up    = None
        v.left  = None
        v.right = None


# Procedura wstawia do drzewa BST
# węzeł o kluczu k
# r - korzeń
#--------------------------------
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 bool(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 bool(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

# Funkcja oblicza szybko 2^log2(x)
# Wartością tej funkcji jest liczba x, 
# w której pozostawiono najstarszy bit 1
#---------------------------------------
def log2(x):
    y = 1
    while x >> 1:
        y <<= 1
        x >>= 1
    return y

# Procedura równoważy drzewo BST
# r - korzeń
#-------------------------------
def rebalance_dsw(r):
    # W n zliczamy węzły
    n = 0
    # Rozpoczynamy tworzenie listy liniowej
    p = r
    # Dopóki jesteśmy w drzewie
    while p:
        # Jeśli przetwarzany węzeł ma
        # lewego syna, 
        if p.left:
            # to obracamy wokół niego
            # drzewo w prawo
            r = rot_r(r, p)
            p = p.up
        else:
            # Inaczej zwiększamy
            # licznik węzłów
            n += 1
            # i przesuwamy się do
            # prawego syna 
            p = p.right
    # Teraz z listy tworzymy drzewo BST
    # Wyznaczamy początkową liczbę obrotów
    s = n+1-log2(n+1)
    # Rozpoczynamy od początku drzewa
    p = r
    # Zadaną liczbę razy
    for i in range(s):
        # co drugi węzeł obracamy w lewo
        r = rot_l(r, p)
        p = p.up.right
    # Wyznaczamy kolejne liczby obrotów
    n -= s
    # Powtarzamy procedurę obrotów węzłów
    while n > 1:
        # Jednakże wyznaczając za każdym razem
        # odpowiednio mniejszą liczbę obrotów, 
        # która maleje z potęgami 2
        n >>= 1
        p = r
        for i in range(n):
            r = rot_l(r, p)
            p = p.up.right
    return r

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

# Korzeń
root = None
# Drzewo wypełniamy węzłami
for i in range(15):
    k = random.randrange(1, 10)
    root = insert_bst(root, k)
# wyświetlamy drzewo
print_bt("", "", root)
print()
print()
# Równoważymy drzewo
root = rebalance_dsw(root)
# wyświetlamy drzewo
print_bt("", "", root)
# Usuwamy drzewo BST z pamięci
dfs_release(root)

Wynik:

        ┌─9
      ┌─6
    ┌─6
  ┌─6
┌─5
│ │     ┌─4
│ │   ┌─4
│ │ ┌─4
│ └─4
4
│     ┌─2
│     │ └─1
│   ┌─1
│ ┌─1
└─1


    ┌─9
  ┌─6
  │ └─6
┌─6
│ │ ┌─5
│ └─4
│   └─4
4
│   ┌─4
│ ┌─4
│ │ └─2
└─1
  │ ┌─1
  └─1
    └─1

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.

Równoważenie drzewa BST – algorytm DSW

Problem

Rotacje drzewa

Rotacja w prawo

Algorytm rotacji w prawo drzewa BST

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Rotacja w lewo

Algorytm rotacji w lewo drzewa BST

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Algorytm DSW

Algorytm wyznaczania wartości 2^|_log2^x_|

Wejście:

Wyjście:

Lista kroków:

Algorytm DSW – zrównoważanie drzewa BST - rebalance_dsw(root)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Równoważenie drzewa BST – algorytm DSW

Problem

Rotacje drzewa

Rotacja w prawo

Algorytm rotacji w prawo drzewa BST

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Rotacja w lewo

Algorytm rotacji w lewo drzewa BST

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Algorytm DSW

Algorytm wyznaczania wartości 2|_log2 x_|

Wejście:

Wyjście:

Lista kroków:

Algorytm DSW – zrównoważanie drzewa BST - rebalance_dsw(root)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy

Algorytm wyznaczania wartości 2^|_log2^x_|