Trwałe struktury danych

07.06.2010 - Filip Sieczkowski
TrudnośćTrudnośćTrudnośćTrudność

Coś więcej: drzewa przeszukiwań binarnych

Jak widzieliśmy, stos w wersji trwałej w zasadzie nie różnił się od zwykłego stosu, do jakiego byliśmy przyzwyczajeni. Dzieje się tak, ponieważ nowo dodawany element nie będzie osiągalny z żadnego spośród elementów stosu. W przypadku drzewa BST, nowe elementy dodajemy w liściach drzewa, a więc muszą być one osiągalne z jego korzenia. Jednocześnie samego korzenia nie możemy zmodyfikować ─ z niego ``widoczna'' ma być stara wersja drzewa. Sposobem na poradzenie sobie z tym problemem jest technika kopiowania ścieżki ─ Skopiowane zostaną wszystkie elementy drzewa, z których widoczny jest nowo dodawany element, a więc ścieżka od korzenia aż do miejsca, w które nasz element zostanie wstawiony. Zobaczmy to na przykładzie wstawienia do drzewa elementu o kluczu 5. Elementy pokolorowane na czerwono zostały stworzone w trakcie operacji insert. Jak widać, został stworzony element o kluczu 5, a ścieżka prowadząca do niego od korzenia została skopiowana. Części drzewa poza ścieżką są współdzielone.

Poniżej przedstawiona jest implementacja drzewa BST z operacjami wstawiania, znajdowania i usuwania minimum, oraz znajdowania dolnego ograniczenia dla danego klucza.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class BSTree {
  BSTree() : key(0), left(NULL), right(NULL){}
  int key;
  BSTree * left;
  BSTree * right;
public:
  BSTree(int _key, BSTree * _left, BSTree * _right) :
    key(_key), left(_left), right(_right){}
 
  static BSTree * insert(int key, BSTree * tree){
    if(tree == NULL) return new BSTree(key, NULL, NULL);
    if(key > tree->key)
      return new BSTree(tree->key, tree->left, insert(key, tree->right));
    else if(key < tree->key)
      return new BSTree(tree->key, insert(key, tree->left), tree->right);
    else return tree;
  }
 
  int find_min(){
    if(left == NULL) return key;
    else return left->find_min();
  }
 
  int lower_bound(int k){
    if(key == k)return k;
    if(key > k){
      if(left == NULL)return -infinity;
      return left->lower_bound(k);
    }
    if(key < k){
      if(right == NULL) return key;
      return max(key, right->lower_bound(k));
    }
  }
 
  BSTree * delete_min(){
    if(tree -> left == leaf()) return tree -> right;
    else return new BSTree(tree->key, delete_min(tree->left), tree->right);
  }
 
};

Zwróćmy uwagę, jak w funkcjach zmieniających drzewo (delete_min i insert), cała ścieżka od drzewa do odpowiedniego węzła jest kopiowana, podczas gdy odpowiednie poddrzewa pozostają niezmienionymi wskaźnikami ─ a więc są współdzielone z poprzednią wersją struktury. Dokładnie taki był nasz cel, opisany na rysunku.

Oczywiście taką implementację drzew BST można, podobnie jak wersję ulotną, usprawnić tworząc trwałe drzewa AVL lub czerwono-czarne; odpowiednia modyfikacja (bez usuwania elementów) jest przedmiotem drugiego z zadań.

Nie możesz wysyłać i oglądać rozwiązań tego zadania ponieważ nie jesteś zalogowany. Zaloguj się lub załóż konto.
0
Twoja ocena: Brak

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com