Algorytmy i Struktury Danych - Drzewa poszukiwań binarnych

Drzewa BST pozwalają wyszukiwać zawarte w nich elementy z klasą złożoności obliczeniowej O(log n), gdzie n oznacza liczbę węzłów. Prześledźmy sposób wyszukiwania węzła o kluczu 19 w drzewie BST:

Stan	Opis
	Wyszukiwanie rozpoczynamy od korzenia drzewa. Porównujemy wartość węzła z wartością poszukiwaną. Ponieważ jest ona większa od wartości korzenia, idziemy wzdłuż prawej krawędzi do prawego syna (jeśli węzeł nie miałby prawego syna, to oznaczałoby to, że poszukiwanej wartości nie ma w drzewie BST).
	W węźle 21 ponownie dokonujemy porównania. Ponieważ poszukiwany węzeł jest mniejszy od 21, wybieramy gałąź lewą i przechodzimy do lewego syna 15.
	Porównujemy węzeł 15 z poszukiwanym 19. Ponieważ 19 jest większe, idziemy prawą krawędzią do prawego syna 19.
	Porównujemy węzeł 19 z poszukiwanym. Są równe. Wyszukiwanie zakończone.

Z przedstawionego powyżej schematu wynikają dwa proste wnioski:

Element najmniejszy w drzewie znajdziemy,
idąc lewymi gałęziami aż do elementu, który
nie posiada już lewego syna

Element największy w drzewie znajdziemy,
idąc prawymi gałęziami aż do elementu, który
nie posiada już prawego syna.

W obu przypadkach nie musimy nawet porównywać węzłów. Min i Max wyznacza sama struktura drzewa BST.

Algorytm wyszukiwania węzła w drzewie BST – find_bst(root, k)

Wejście:

k : klucz poszukiwanego węzła.
p : wskazanie korzenia drzewa BST.

Wyjście:

Wskazanie węzła na drzewie BST o kluczu k lub nil, jeśli drzewo nie zawiera takiego węzła.

Lista kroków:

K01: Dopóki (p ≠ nil)(p→key ≠ k), ; przeszukujemy drzewo BST
     wykonuj krok K02

K02:   Jeśli k < p→key, ; decydujemy, którą drogą pójść:
       to p ← p→left  ; w lewo
       inaczej p ← p→right ; czy w prawo
K03: Zakończ z wynikiem p

Algorytm wyszukiwania w drzewie BST węzła o najmniejszym kluczu – min_bst(p)

Wejście:

p : wskazanie korzenia drzewa BST.

Wyjście:

Wskazanie węzła o najmniejszym kluczu lub nil, jeśli drzewo jest puste.

Lista kroków:

K01: Jeśli p = nil, 
     to idź do kroku K03
K02: Dopóki p→left ≠ nil, ; szukamy węzła bez lewego syna 
     wykonuj p ← p→left
K03: Zakończ z wynikiem p

Algorytm wyszukiwania w drzewie BST węzła o największym kluczu – max_bst(p)

Wejście:

p : wskazanie korzenia drzewa BST.

Wyjście:

Wskazanie węzła o największym kluczu lub nil, jeśli drzewo jest puste.

Lista kroków:

K01: Jeśli p = nil, 
     to idź do kroku K03
K02: Dopóki p→right ≠ nil, ; szukamy węzła bez prawego syna 
     wykonuj p ← p→right
K03: Zakończ z wynikiem p

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 wczytuje definicję drzewa binarnego, którego klucze są liczbami całkowitymi. Wyznacza klucz minimalny i maksymalny, a następnie idąc kolejno przez wartości kluczy od min do max wyświetla informacje o znalezionym węźle.

Sposób wprowadzania drzew binarnych opisaliśmy w rozdziale o badaniu drzew binarnych. Tutaj krótko przypomnijmy, że węzły drzewa są numerowane od strony lewej do prawej na kolejnych poziomach. Pierwszą liczbą jest ilość wierzchołków n. Kolejne n wierszy zawiera 3 liczby określające kolejne wierzchołki. Pierwsza liczba w trójce określa klucz węzła. Pozostałe dwie liczby określają kolejno numer węzła będącego lewym i prawym synem. Jeśli węzeł nie ma któregoś z synów, to numer syna przyjmuje wartość zero. W strukturach węzłów nie będziemy wykorzystywać pola up, które tutaj nie będzie nam potrzebne, ponieważ będziemy poruszać się tylko w dół drzewa.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

Pascal

// Wyszukiwanie w drzewie BST
// Data: 24.04.2013
// (C)2013 mgr Jerzy Wałaszek
//---------------------------

program bst;

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

// Funkcja wczytuje drzewo BST
// ze standardowego wejścia
// i zwraca wskazanie korzenia
//----------------------------
function read_bst : PBSTnode;
var
  // Tablica wskazań węzłów
  vp : array of PBSTnode;
  key, l, r, i, n : integer;

begin

  // Odczytujemy liczbę
  // węzłów drzewa
  readln(n);

  // Tworzymy dynamiczną
  // tablicę wskazań węzłów
  SetLength(vp, n);

  // Tablicę dynamiczną wypełniamy
  // wskazaniami węzłów, które
  // również tworzymy dynamicznie
  for i := 0 to n-1 do
    new(vp[i]);

  // Teraz wczytujemy definicję
  // drzewa i tworzymy jego
  // strukturę w pamięci wypełniając
  // odpowiednie pola węzłów.
  for i := 0 to n-1 do
  begin

    // Czytamy klucz, numer lewego
    // i prawego syna 
    readln(key, l, r);

    // Ustawiamy klucz
    vp[i]^.key := key;

    // Ustawiamy lewego syna 
    if l > 0 then
      vp[i]^.left  := vp[l]
    else
      vp[i]^.left  := nil;

    // Ustawiamy prawego syna 
    if r > 0 then
      vp[i]^.right := vp[r]
    else
      vp[i]^.right := nil;

  end;

  // Zapamiętujemy korzeń
  read_bst := vp[0];

  // Usuwamy tablicę dynamiczną
  SetLength(vp, 0);
end;

// Funkcja szuka w drzewie BST
// węzła o zadanym kluczu.
// Jeśli go znajdzie, zwraca jego
// wskazanie. Jeżeli nie, to zwraca
// wskazanie puste.
// Parametrami są:
// p-wskazanie korzenia drzewa BST
// k-klucz poszukiwanego węzła
//---------------------------------
function find_bst(p : PBSTnode;
                  k : integer)
                    : PBSTnode;
begin
  while(p <> nil) and
       (p^.key <> k) do
    if k < p^.key then
      p := p^.left
    else
      p := p^.right;
  find_bst := p;
end;

// Funkcja zwraca wskazanie węzła
// o najmniejszym kluczu. Parametrem
// jest wskazanie korzenia drzewa BST
//-----------------------------------
function min_bst(p : PBSTnode)
                   : PBSTnode;
begin
  if p <> nil then
    while p^.left <> nil do
      p := p^.left;
  min_bst := p;
end;

// Funkcja zwraca wskazanie węzła
// o największym kluczu. Parametrem
// jest wskazanie korzenia drzewa BST
//-----------------------------------
function max_bst(p : PBSTnode)
                   : PBSTnode;
begin
  if p <> nil then
    while p^.right <> nil do
      p := p^.right;
  max_bst := p;
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;

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

var
  root, p : PBSTnode;
  k, mink, maxk : integer;

begin
  // Odczytujemy drzewo BST
  root := read_bst;
  if root <> nil then
  begin
    // Odczytujemy klucz minimalny
    mink := min_bst(root)^.key;
    // Odczytujemy klucz maksymalny
    maxk := max_bst(root)^.key;

    // Przechodzimy przez kolejne
    // wartości kluczy
    for k := mink to maxk do
    begin
      // szukamy węzła o kluczu k
      p := find_bst(root, k);
      write('KEY = ', k:3, ' : ');
      if p <> nil then
      begin
        if(p^.left = nil) and
          (p^.right = nil) then
          writeln('LEAF')
        else
          writeln('INNER NODE');
      end
      else writeln('NONE');
    end;
  end
  else writeln('BST is empty!!!');

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

C++

// Wyszukiwanie w drzewie BST
// Data: 24.04.2013
// (C)2013 mgr Jerzy Wałaszek
//------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

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

// Funkcja wczytuje drzewo BST
// ze standardowego wejścia
// i zwraca wskazanie korzenia
//----------------------------
BSTnode * read_bst()
{
  // Tablica wskazań węzłów
  BSTnode ** vp;
  int key, l, r, i, n;

  // Odczytujemy liczbę węzłów drzewa
  cin >> n;

  // Tworzymy dynamiczną tablicę
  // wskazań węzłów
  vp = new BSTnode * [n];

  // Tablicę dynamiczną wypełniamy
  // wskazaniami węzłów, które również
  // tworzymy dynamicznie
  for(i = 0; i < n; i++)
    vp[i] = new BSTnode;

  // Teraz wczytujemy definicję drzewa
  // i tworzymy jego strukturę w pamięci
  // wypełniając odpowiednie pola węzłów.
  for(i = 0; i < n; i++)
  {
    cin >> key >> l >> r;

    // Ustawiamy klucz
    vp[i]->key = key;

    // Ustawiamy lewego syna 
    vp[i]->left  = l ? vp[l] : NULL;

    // Ustawiamy prawego syna 
    vp[i]->right = r ? vp[r] : NULL;
  }
  // Zapamiętujemy korzeń
  BSTnode * p = vp[0];

  // Usuwamy tablicę dynamiczną
  delete [] vp;

  return p;
}

// Funkcja szuka w drzewie BST węzła
// o zadanym kluczu. Jeśli go znajdzie, 
// zwraca jego wskazanie. Jeżeli nie, 
// to zwraca wskazanie puste.
// Parametrami są:
// p-wskazanie korzenia drzewa BST
// k-klucz poszukiwanego węzła
//-------------------------------------
BSTnode * find_bst(BSTnode * p, int k)
{
  while(p && p->key != k)
    p = (k < p->key) ? p->left: p->right;
  return p;
}

// Funkcja zwraca wskazanie węzła
// o najmniejszym kluczu.
// Parametrem jest wskazanie korzenia
// drzewa BST.
//-----------------------------------
BSTnode * min_bst(BSTnode * p)
{
  if(p)
    while(p->left)
      p = p->left;
  return p;
}

// Funkcja zwraca wskazanie węzła
// o największym kluczu. Parametrem
// jest wskazanie korzenia drzewa BST
//-----------------------------------
BSTnode * max_bst(BSTnode * p)
{
  if(p)
    while(p->right)
      p = p->right;
  return p;
}

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

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

int main()
{
  BSTnode * root, * p;
  int k, mink, maxk;

  // Odczytujemy drzewo BST
  root = read_bst();

  if(root)
  {
    // Odczytujemy klucz minimalny
    mink = min_bst(root)->key;
    // Odczytujemy klucz maksymalny
    maxk = max_bst(root)->key;

    // Przechodzimy przez kolejne
    // wartości kluczy
    for(k = mink; k <= maxk; k++)
    {
      // szukamy węzła o kluczu k
      p = find_bst(root, k);
      cout << "KEY = " << setw(3)
           <<  k << ": ";
      if(p)
      {
        if(!p->left && !p->right)
          cout << "LEAF";
        else
          cout << "INNER NODE";
      }
      else cout << "NONE";
      cout << endl;
    }
  }
  else
    cout << "BST is empty!!!" << endl;

  // usuwamy drzewo z pamięci
  dfs_release(root);

  return 0;
}

Basic

' Wyszukiwanie w drzewie BST
' Data: 24.04.2013
' (C)2013 mgr Jerzy Wałaszek
'---------------------------

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

' Funkcja wczytuje drzewo BST
' ze standardowego wejścia
' i zwraca wskazanie korzenia
'----------------------------
Function read_bst() As BSTnode Ptr

  ' Tablica wskazań węzłów
  Dim As BSTnode Ptr Ptr vp
  Dim As Integer key, l, r, i, n

  Open Cons For Input As #1
 
  ' Odczytujemy liczbę
  ' węzłów drzewa
  Input #1, n

  ' Tworzymy dynamiczną tablicę
  ' wskazań węzłów
  vp = new BSTnode Ptr [n]

  ' Tablicę dynamiczną wypełniamy
  ' wskazaniami węzłów, które
  ' również tworzymy dynamicznie
  For i = 0 To n-1
  	vp[i] = new BSTnode
  Next

  ' Teraz wczytujemy definicję
  ' drzewa i tworzymy jego strukturę
  ' w pamięci wypełniając
  ' odpowiednie pola węzłów.
  For i = 0 To n-1
    ' Czytamy klucz, numer lewego
    ' i prawego syna 
    Input #1, key, l, r

    ' Ustawiamy klucz
    vp[i]->key = key

    ' Ustawiamy lewego syna 
    If l > 0 Then
      vp[i]->left = vp[l]
    Else
      vp[i]->left = 0
    End If

    ' Ustawiamy prawego syna 
    If r > 0 Then
      vp[i]->right = vp[r]
    Else
      vp[i]->right = 0
    End If
  Next
  
  Close #1
  
  ' Zapamiętujemy korzeń
  read_bst = vp [0]

  ' Usuwamy tablicę dynamiczną
  delete [] vp

End Function

' Funkcja szuka w drzewie BST
' węzła o zadanym kluczu. Jeśli go
' znajdzie, zwraca jego wskazanie.
' Jeżeli nie, to zwraca wskazanie
' puste.
' Parametrami są:
' p-wskazanie korzenia drzewa BST
' k-klucz poszukiwanego węzła
'--------------------------------
Function find_bst(p As BSTnode Ptr, _
                  k As Integer) _
                    As BSTnode Ptr

  while(p <> 0) AndAlso _
       (p->key <> k)
    If k < p->key Then
    	p = p->Left
    Else
    	p = p->Right
    End If
  Wend
 
  Return p
 
End Function

' Funkcja zwraca wskazanie węzła
' o najmniejszym kluczu. Parametrem
' jest wskazanie korzenia drzewa BST
'-----------------------------------
Function min_bst(p As BSTnode Ptr) _
                   As BSTnode Ptr
  If p Then
    While p->Left
      p = p->Left
    Wend
  End If

  Return p
  
End Function

' Funkcja zwraca wskazanie węzła
' o największym kluczu. Parametrem
' jest wskazanie korzenia drzewa BST
'-----------------------------------
Function max_bst(p As BSTnode Ptr) _
                   As BSTnode Ptr
  If p Then
    While p->Right
    	p = p->Right
    Wend
  End If

  Return p
  
End Function

' 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

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

Dim As BSTnode Ptr root, p
Dim As Integer k, mink, maxk

' Odczytujemy drzewo BST
root = read_bst()

If root Then

  ' Odczytujemy klucz minimalny
  mink = min_bst(root)->key
  ' Odczytujemy klucz maksymalny
  maxk = max_bst(root)->key

  ' Przechodzimy przez kolejne
  ' wartości kluczy
  For k = mink To maxk
   
    ' szukamy węzła o kluczu k
    p = find_bst(root, k)
    Print Using "KEY = ### : ";k;
    If p Then
      if(p->Left = 0) AndAlso _
        (p->Right = 0) Then
        Print "LEAF"
      Else
        Print "INNER NODE"
      End If  
    Else
     Print "NONE"
    End If

  Next

Else

  Print "BST is empty!!!"

End If

' usuwamy drzewo z pamięci
dfs_release(root)

End

Python (dodatek)

# Wyszukiwanie w drzewie BST
# Data: 12.07.2024
# (C)2024 mgr Jerzy Wałaszek
# ---------------------------

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

    def __init__(self):
        self.left = None
        self.right = None
        self.key = 0


# Funkcja wczytuje drzewo BST
# ze standardowego wejścia
# i zwraca wskazanie korzenia
def read_bst():
    # Tablica wskazań węzłów
    vp = []

    # Odczytujemy liczbę
    # węzłów drzewa
    n = int(input())

    # Tworzymy dynamiczną tablicę
    # wskazań węzłów
    for i in range(n):
        vp.append(BSTnode())

    # Teraz wczytujemy definicję
    # drzewa i tworzymy jego strukturę
    # w pamięci wypełniając
    # odpowiednie pola węzłów.
    for i in range(n):
        # Czytamy klucz, numer lewego
        # i prawego syna węzła
        arr = input().split()

        k = int(arr[0])
        l = int(arr[1])
        r = int(arr[2])

        # Ustawiamy klucz
        vp[i].key = k

        # Ustawiamy lewego syna
        if l:
            vp[i].left = vp[l]
        else:
            vp[i].left = None

        # Ustawiamy prawego syna
        if r:
            vp[i].right = vp[r]
        else:
            vp[i].right = None

    # Zapamiętujemy korzeń
    r = vp[0]
    return r


# Funkcja szuka w drzewie BST
# węzła o zadanym kluczu. Jeśli go
# znajdzie, zwraca jego wskazanie.
# Jeżeli nie, to zwraca wskazanie
# puste.
# Parametrami są:
# R - korzeń drzewa BST
# k - klucz poszukiwanego węzła
def find_bst(r, k):
    while r and (r.key != k):
        if k < r.key:
            r = r.left
        else:
            r = r.right
    return r


# Funkcja zwraca wskazanie węzła
# o najmniejszym kluczu.
# R - korzeń
def min_bst(r):
    if r:
        while r.left:
            r = r.left
    return r


# Funkcja zwraca wskazanie węzła
# o największym kluczu.
# R - korzeń
def max_bst(r):
    if r:
        while r.right:
            r = r.right
    return r


# 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


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

# Odczytujemy drzewo BST
root = read_bst()
if root:
    # Odczytujemy klucz minimalny
    mink = min_bst(root).key
    # Odczytujemy klucz maksymalny
    maxk = max_bst(root).key
    # Przechodzimy przez kolejne
    # wartości kluczy
    for k in range(mink, maxk + 1):
        # szukamy węzła o kluczu k
        p = find_bst(root, k)
        print("KEY = %3d : " % k, end="")
        if p:
            if (not p.left) and (not p.right):
                print("LEAF")
            else:
                print("INNER NODE")
        else:
            print("NONE")
else:
    print("BST is empty!!!")
# usuwamy drzewo z pamięci
dfs_release(root)

Wynik:

12
9 1 2
5 3 4
15 5 6
4 7 0
7 8 9
10 0 10
18 0 11
1 0 0
6 0 0
8 0 0
12 0 0
19 0 0
KEY =   1 : LEAF
KEY =   2 : NONE
KEY =   3 : NONE
KEY =   4 : INNER NODE
KEY =   5 : INNER NODE
KEY =   6 : LEAF
KEY =   7 : INNER NODE
KEY =   8 : LEAF
KEY =   9 : INNER NODE
KEY =  10 : INNER NODE
KEY =  11 : NONE
KEY =  12 : LEAF
KEY =  13 : NONE
KEY =  14 : NONE
KEY =  15 : INNER NODE
KEY =  16 : NONE
KEY =  17 : NONE
KEY =  18 : INNER NODE
KEY =  19 : LEAF

do podrozdziału do strony

Na początku rozdziału powiedzieliśmy, że kolejność węzłów w drzewie BST jest taka, iż w wyniku przejścia tego drzewa algorytmem in-order otrzymamy niemalejący ciąg kluczy. Przyjrzyjmy się dokładniej temu przejściu:

Zauważ, że znalezienie następnika wcale nie wymaga porównywania węzłów. Mogą wystąpić trzy przypadki:

	Przypadek 1: Węzeł x posiada prawego syna – następnikiem jest wtedy węzeł o minimalnym kluczu w poddrzewie, którego korzeniem jest prawy syn. Wykorzystujemy tutaj algorytm wyszukiwania węzła o najmniejszym kluczu w prawym poddrzewie.
	Przypadek 2: Węzeł x nie posiada prawego syna. W takim przypadku, idąc w górę drzewa, musimy znaleźć pierwszego ojca, dla którego nasz węzeł leży w lewym poddrzewie. Tutaj również nie musimy porównywać węzłów. Po prostu idziemy w górę drzewa i w węźle nadrzędnym sprawdzamy, czy przyszliśmy od strony lewego syna. Jeśli tak, to węzeł ten jest następnikiem. Jeśli nie, to kontynuujemy marsz w górę drzewa. Wymaga to zapamiętywania adresów kolejno mijanych węzłów.
	Przypadek 3: Węzeł x nie posiada prawego syna. Idąc w górę drzewa, dochodzimy do korzenia, a następnie do adresu nil, który wskazuje pole up korzenia drzewa BST. W takim przypadku węzeł x jest węzłem o największym kluczu i nie posiada następnika.

Ponieważ będziemy musieli poruszać się w górę drzewa, węzły muszą posiadać pole up prowadzące do ojca.

Algorytm znajdowania następnika węzła w drzewie BST – succ_bst(p)

Wejście:

p : wskazanie węzła na drzewie BST, dla którego poszukujemy następnika.

Wyjście:

Wskazanie węzła będącego następnikiem węzła wejściowego lub nil, jeśli węzeł wejściowy nie ma następnika.

Elementy pomocnicze:

r : wskazanie węzła.
min_bst(w) : znajduje element minimalny, traktując w jako korzeń.

Lista kroków:

K01: Jeśli p = nil, ; jeśli drzewo jest puste, 
     to zakończ z wynikiem p ; kończymy
K02: Jeśli p→right ≠ nil, ; Przypadek 1
     to zakończ z wynikiem min_bst(p→right)
K03: r ← p→up ; r wskazuje ojca p
K04: Dopóki (r ≠ nil)(p = r→right),
     wykonuj kroki K05…K06 ; Przypadki 2 i 3
K05:   p ← r ; przemieszczamy się w górę drzewa, 
       ; aż trafimy na węzeł, 
K06:   r ← r→up ; dla którego p leży w lewej gałęzi
K07: Zakończ z wynikiem r ; zwracamy znaleziony węzeł
     ; lub nil, jeśli następnika nie ma

Algorytm znajdowania poprzednika jest lustrzanym odbiciem algorytmu znajdowania następnika (dlaczego?):

Algorytm znajdowania poprzednika węzła w drzewie BST – pred_bst(p)

Wejście:

p : wskazanie węzła na drzewie BST, dla którego poszukujemy poprzednika.

Wyjście:

Wskazanie węzła będącego poprzednikiem węzła wejściowego lub nil, jeśli węzeł wejściowy nie ma następnika.

Elementy pomocnicze:

r : wskazanie węzła.
max_bst(w) : znajduje element maksymalny, traktując w jako korzeń.

Lista kroków:

K01: Jeśli p = nil, ; jeśli drzewo jest puste, kończymy
     to zakończ z wynikiem p
K02: Jeśli p→left ≠ nil, ; Przypadek 1
     to zakończ z wynikiem max_bst(p→left)
K03: r ← p→up ; r wskazuje ojca p
K04: Dopóki (r ≠ nil)(p = r→left), ; Przypadki 2 i 3
     wykonuj kroki K05…K06
K05:   p ← r ; przemieszczamy się w górę drzewa, 
       ; aż trafimy na węzeł, 
K06:   r ← r→up ; dla którego p leży w prawej gałęzi
K07: Zakończ z wynikiem r ; zwracamy znaleziony węzeł
     ; lub nil, jeśli poprzednika nie ma

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 wczytuje definicję drzewa binarnego, którego klucze są liczbami całkowitymi. Dane dla drzewa wyglądają następująco:

Pierwsza liczba n określa – ilość węzłów w drzewie.
Kolejne n wierszy zawiera po cztery liczby: klucz, numer ojca (dla korzenia wartość 0), numer lewego syna, numer prawego syna.
Program wyznacza kolejne następniki i poprzedniki korzenia.

Dane przykładowe (przekopiuj do schowka i wklej do okna konsoli):

Pascal

// Następnik i poprzednik w drzewie BST
// Data: 27.04.2013
// (C)2013 mgr Jerzy Wałaszek
//-------------------------------------

program sp_bst;

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

// Funkcja wczytuje drzewo BST ze
// standardowego wejścia i zwraca
// wskazanie korzenia.
//-------------------------------
function read_bst : PBSTnode;
var
   // Tablica wskazań węzłów
  vp : array of PBSTnode;
  key, u, l, r, i, n : integer;
begin

  // Odczytujemy liczbę węzłów drzewa
  readln(n);

  // Tworzymy dynamiczną tablicę
  // wskazań węzłów
  SetLength(vp, n);

  // Tablicę dynamiczną wypełniamy
  // wskazaniami węzłów, które również
  // tworzymy dynamicznie
  for i := 0 to n-1 do new(vp[i]);

  // Teraz wczytujemy definicję drzewa
  // i tworzymy jego strukturę w pamięci
  // wypełniając odpowiednie pola węzłów.
  for i := 0 to n-1 do
  begin
    // Czytamy klucz, numery ojca, 
    // lewego i prawego syna 
    readln(key, u, l, r);

    // Ustawiamy klucz
    vp[i]^.key := key;

    // Ustawiamy ojca 
    vp[i]^.up := vp[u];

    // Ustawiamy lewego syna 
    if l > 0 then
      vp[i]^.left := vp[l]
    else
      vp[i]^.left := nil;

    // Ustawiamy prawego syna 
    if r > 0 then
      vp[i]^.right := vp[r]
    else
      vp[i]^.right := nil;
  end;

  // Korzeń nie posiada ojca
  vp[0]^.up := nil;

  // Zapamiętujemy korzeń
  read_bst := vp[0];

  // Usuwamy tablicę dynamiczną
  SetLength(vp, 0);
end;

// Funkcja zwraca wskazanie węzła
// o najmniejszym kluczu. Parametrem
// jest wskazanie korzenia drzewa BST
//-----------------------------------
function min_bst(p : PBSTnode)
                : PBSTnode;
begin
  if p <> nil then
    while p^.left <> nil do
      p := p^.left;
  min_bst := p;
end;

// Funkcja zwraca wskazanie węzła
// o największym kluczu. Parametrem
// jest wskazanie korzenia drzewa BST
//-----------------------------------
function max_bst(p : PBSTnode)
                   : PBSTnode;
begin
  if p <> nil then
    while p^.right <> nil do
      p := p^.right;
  max_bst := p;
end;

// Funkcja znajduje następnik węzła p
//-----------------------------------
function succ_bst(p : PBSTnode)
                    : PBSTnode;
var
  r : PBSTnode;
begin
  succ_bst := nil;
  if p <> nil then
  begin
    if p^.right <> nil then
      succ_bst := min_bst(p^.right)
    else
    begin
      r := p^.up;
      while (r <> nil) and
            (p = r^.right) do
      begin
        p := r;
        r := r^.up;
      end;
      succ_bst := r;
    end;
  end;
end;

// Funkcja znajduje poprzednik węzła p
//------------------------------------
function pred_bst(p : PBSTnode)
                    : PBSTnode;
var
  r : PBSTnode;
begin
  predBST := nil;
  if p <> nil then
  begin
    if p^.left <> nil then
      predBST := max_bst(p^.left)
    else
    begin
      r := p^.up;
      while (r <> nil) and
            (p = r^.left) do
      begin
        p := r;
        r := r^.up;
      end;
      predBST := r;
    end;
  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;

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

var
  root, p : PBSTnode;

begin
  // Odczytujemy drzewo BST
  root := read_bst;
  if root <> nil then
  begin
    write('SUCCESORS    :');
    p := root;
    while p <> nil do
    begin
      write(p^.key:3);
      p := succ_bst(p);
    end;
    writeln;
    write ('PREDECCESORS :');
    p := root;
    while p <> nil do
    begin
      write(p^.key:3);
      p := pred_bst(p);
    end;
    writeln;
  end
  else writeln('BST is empty!!!');
  // usuwamy drzewo z pamięci
  dfs_release(root);

end.

C++

// Następnik i poprzednik w drzewie BST
// Data: 27.04.2013
// (C)2013 mgr Jerzy Wałaszek
//-------------------------------------

#include <iostream>
#include <iomanip>

using namespace std;

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

// Funkcja wczytuje drzewo BST
// ze standardowego wejścia
// i zwraca wskazanie korzenia
//----------------------------
BSTnode * read_bst()
{
  // Tablica wskazań węzłów
  BSTnode ** vp;
  int key, u, l, r, i, n;

  // Odczytujemy liczbę węzłów drzewa
  cin >> n;

  // Tworzymy dynamiczną tablicę
  // wskazań węzłów
  vp = new BSTnode * [n];

  // Tablicę dynamiczną wypełniamy
  // wskazaniami węzłów, które również
  // tworzymy dynamicznie
  for(i = 0; i < n; i++)
    vp[i] = new BSTnode;

  // Teraz wczytujemy definicję drzewa
  // i tworzymy jego strukturę w pamięci
  // wypełniając odpowiednie pola węzłów.
  for(i = 0; i < n; i++)
  {
    // Czytamy klucz, numery ojca, 
    // lewego i prawego syna 
    cin >> key >> u >> l >> r;

    // Ustawiamy klucz
    vp[i]->key = key;

    // Ustawiamy ojca 
    vp[i]->up = vp[u];

    // Ustawiamy lewego syna 
    vp[i]->left = l ? vp[l] : NULL;

    // Ustawiamy prawego syna 
    vp[i]->right = r ? vp[r] : NULL;
  }

  // Korzeń nie posiada ojca 
  vp[0]->up = NULL;

  // Zapamiętujemy korzeń
  BSTnode * p = vp[0];

  // Usuwamy tablicę dynamiczną
  delete [] vp;

  return p;
}

// Funkcja zwraca wskazanie węzła
// o najmniejszym kluczu. Parametrem
// jest wskazanie korzenia drzewa BST
//-----------------------------------
BSTnode * min_bst(BSTnode * p)
{
  if(p)
    while(p->left)
      p = p->left;
  return p;
}

// Funkcja zwraca wskazanie węzła
// o największym kluczu. Parametrem
// jest wskazanie korzenia drzewa BST
//-----------------------------------
BSTnode * max_bst(BSTnode * p)
{
  if(p)
    while(p->right)
      p = p->right;
  return p;
}

// Funkcja znajduje następnik węzła p
//-----------------------------------
BSTnode * succ_bst(BSTnode * p)
{
  BSTnode * r;

  if(p)
  {
    if(p->right)
      return min_bst(p->right);
    else
    {
      r = p->up;
      while(r && (p == r->right))
      {
        p = r;
        r = r->up;
      }
      return r;
    }
  }
  return p;
}

// Funkcja znajduje poprzednik węzła p
//------------------------------------
BSTnode * pred_bst(BSTnode * p)
{
  BSTnode * r;

  if(p)
  {
    if(p->left)
      return max_bst(p->left);
    else
    {
      r = p->up;
      while(r && (p == r->left))
      {
        p = r;
        r = r->up;
      }
      return r;
    }
  }
  return p;
}

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

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

int main()
{
  BSTnode *root, *p;

  // Odczytujemy drzewo BST
  root = read_bst();

  if(root)
  {
    cout << "SUCCESORS    :";
    for(p = root; p; p = succ_bst(p))
      cout << setw(3) << p->key;

    cout << endl << "PREDECCESORS :";
    for(p = root; p; p = pred_bst(p))
      cout << setw (3) << p->key;

    cout << endl;
  }
  else
    cout << "BST is empty!!!" << endl;

  // usuwamy drzewo z pamięci
  dfs_release(root);

  return 0;
}

Basic

' Następnik i poprzednik w drzewie BST
' Data: 27.04.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

' Funkcja wczytuje drzewo BST
' ze standardowego wejścia
' i zwraca wskazanie korzenia
'----------------------------
Function read_bst() As BSTnode Ptr

  ' Tablica wskazań węzłów
  Dim As BSTnode Ptr Ptr vp
  Dim As Integer key, u, l, r, i, n

  Open Cons For Input As #1
 
  ' Odczytujemy liczbę węzłów drzewa
  Input #1, n

  ' Tworzymy dynamiczną tablicę
  ' wskazań węzłów
  vp = new BSTnode Ptr [n]

  ' Tablicę dynamiczną wypełniamy
  ' wskazaniami węzłów, które również
  ' tworzymy dynamicznie
  For i = 0 To n-1
    vp[i] = new BSTnode
  Next

  ' Teraz wczytujemy definicję drzewa
  ' i tworzymy jego strukturę w pamięci
  ' wypełniając odpowiednie pola węzłów.
  For i = 0 To n-1
 
    ' Czytamy klucz, numery ojca, 
    ' lewego i prawego syna 
    Input #1, key, u, l, r

    ' Ustawiamy klucz
    vp[i]->key = key

    ' Ustawiamy ojca 
    vp[i]->up = vp[u]

    ' Ustawiamy lewego syna 
    If l > 0 Then
      vp[i]->left = vp[l]
    Else
      vp[i]->left = 0
    End If

    ' Ustawiamy prawego syna 
    If r > 0 Then
      vp[i]->right = vp[r] 
    Else
      vp[i]->right = 0
    End If

  Next

  Close #1
 
  ' Korzeń nie posiada ojca 
  vp[0]->up = 0

  ' Zapamiętujemy korzeń
  read_bst = vp[0]

  ' Usuwamy tablicę dynamiczną
  delete [] vp

End Function

' Funkcja zwraca wskazanie węzła
' o najmniejszym kluczu. Parametrem
' jest wskazanie korzenia drzewa BST
'-----------------------------------
Function min_bst(p As BSTnode Ptr) _
                As BSTnode Ptr
  If p Then
    While p->Left
      p = p->Left
    Wend
  End If
  Return p
End Function

' Funkcja zwraca wskazanie węzła
' o największym kluczu. Parametrem
' jest wskazanie korzenia drzewa BST
'-----------------------------------
Function max_bst(p As BSTnode Ptr) _
                As BSTnode Ptr
  If p Then
    While p->Right
      p = p->Right
    Wend
  End If
  Return p
End Function

' Funkcja znajduje następnik węzła p
'-----------------------------------
Function succ_bst(ByVal p As BSTnode Ptr) _
                 As BSTnode Ptr
  Dim As BSTnode Ptr r

  If p Then
    If p->Right Then
      Return min_bst(p->right)
    Else
      r = p->up
      while (r <> 0) AndAlso _
            (p = r->right)
        p = r
        r = r->up
      Wend
      Return r
    End If
  End If
  Return p
End Function

' Funkcja znajduje poprzednik węzła p
'------------------------------------
Function pred_bst(ByVal p As BSTnode Ptr) _
                 As BSTnode Ptr
  Dim As BSTnode Ptr r

  If p Then
    If p->Left Then
      Return max_bst(p->Left)
    Else
      r = p->up
      while(r <> 0) AndAlso _
           (p = r->Left)
        p = r
        r = r->up
      Wend
      Return r
    End If
  End If
  Return p
End Function

' 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

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

Dim As BSTnode Ptr root, p

' Odczytujemy drzewo BST
root = read_bst()
If root Then
  Print "SUCCESORS    :";
  p = root
  While p
    Print Using "###";p->key;
    p = succ_bst(p)
  Wend

  Print
  
  Print "PREDECCESORS :";
  p = root
  While p
    Print Using "###";p->key;
    p = pred_bst(p)
  Wend

  Print

Else
  Print "BST is empty!!!"
End If

' usuwamy drzewo z pamięci
dfs_release(root)

End

Python (dodatek)

# Następnik i poprzednik w drzewie BST
# Data: 13.07.2024
# (C)2024 mgr Jerzy Wałaszek
#-------------------------------------


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


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


# Funkcja wczytuje drzewo BST
# ze standardowego wejścia
# i zwraca wskazanie korzenia
def read_bst():
    # Tablica wskazań węzłów
    vp = []
    # Odczytujemy liczbę
    # węzłów drzewa
    n = int(input())
    # Tworzymy dynamiczną tablicę
    # wskazań węzłów
    for i in range(n):
        vp.append(BSTnode(0))
    # Teraz wczytujemy definicję
    # drzewa i tworzymy jego strukturę
    # w pamięci wypełniając
    # odpowiednie pola węzłów.
    for i in range(n):
        # Czytamy klucz, numer lewego
        # i prawego syna węzła
        arr = input().split()
        k = int(arr[0])
        u = int(arr[1])
        l = int(arr[2])
        r = int(arr[3])
        # Ustawiamy klucz
        vp[i].key = k
        # Ustawiamy ojca
        vp[i].up = vp[u]
        # Ustawiamy lewego syna
        if l:
            vp[i].left = vp[l]
        else:
            vp[i].left = None
        # Ustawiamy prawego syna
        if r:
            vp[i].right = vp[r]
        else:
            vp[i].right = None
    # Korzeń nie posiada ojca
    vp[0].up = None
    # Zapamiętujemy korzeń
    r = vp[0]
    return r


# Funkcja zwraca wskazanie węzła
# o najmniejszym kluczu.
# r - korzeń
def min_bst(r):
    if r:
        while r.left:
            r = r.left
    return r


# Funkcja zwraca wskazanie węzła
# o największym kluczu.
# r - korzeń
def max_bst(r):
    if r:
        while r.right:
            r = r.right
    return r


# Funkcja znajduje następnik węzła p
#-----------------------------------
def succ_bst(p):
    if p:
        if p.right:
            return min_bst(p.right)
        else:
            r = p.up
            while r and (p is r.right):
                p = r
                r = r.up
            return r
    return p

# Funkcja znajduje poprzednik węzła p
#------------------------------------
def pred_bst(p):
    if p:
        if p.left:
            return max_bst(p.left)
        else:
            r = p.up
            while r and (p is r.left):
                p = r
                r = r.up
            return r
    return p

# 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

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

# Odczytujemy drzewo BST
root = read_bst()
if root:
    print("SUCCESORS    :", end="")
    p = root
    while p:
        print("%3d" % p.key, end="")
        p = succ_bst(p)
    print()
    print("PREDECCESORS :", end="")
    p = root
    while p:
        print("%3d" % p.key, end="")
        p = pred_bst(p)
    print()
else:
    print("BST is empty!!!")
# usuwamy drzewo z pamięci
dfs_release(root)

Wynik:

12
9 0 1 2
5 0 3 4
15 0 5 6
4 1 7 0
7 1 8 9
10 2 0 10
18 2 0 11
1 3 0 0
6 4 0 0
8 4 0 0
12 5 0 0
19 6 0 0
SUCCESORS : 9 10 12 15 18 19
PREDECCESORS : 9 8 7 6 5 4 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.

up	:	wskazanie ojca węzła
left	:	wskazanie lewego syna
right	:	wskazanie prawego syna
key	:	klucz, wg którego węzły są uporządkowane w drzewie BST
data	:	dowolne dane węzła

Drzewa poszukiwań binarnych – BST

Budowa drzewa BST

Wyszukiwanie węzłów w drzewie BST

Algorytm wyszukiwania węzła w drzewie BST – find_bst(root, k)

Wejście:

Wyjście:

Lista kroków:

Algorytm wyszukiwania w drzewie BST węzła o najmniejszym kluczu – min_bst(p)

Wejście:

Wyjście:

Lista kroków:

Algorytm wyszukiwania w drzewie BST węzła o największym kluczu – max_bst(p)

Wejście:

Wyjście:

Lista kroków:

Przykładowe programy

Następnik i poprzednik węzła w drzewie BST

Algorytm znajdowania następnika węzła w drzewie BST – succ_bst(p)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Algorytm znajdowania poprzednika węzła w drzewie BST – pred_bst(p)

Wejście:

Wyjście:

Elementy pomocnicze:

Lista kroków:

Przykładowe programy