OBOWIĄZKOWE DO PRZESŁANIA: jedno zadanie
W drzewach BST (ang. Binary Search Tree, binarne drzewo poszukiwań) przeglądanie wierzchołków w kolejności inorder daje elementy posortowane niemalejąco. Aby to uzyskać trzeba wstawiać elementy do drzewa w następujący sposób:
Koszt wykonania podstawowych operacji w drzewie BST (insert, search, remove) jest rzędu O(h), gdzie h jest wysokością drzewa. Jeżeli drzewo BST jest zrównoważone, wtedy h ~ log(n). W przypadku zdegenerowanym h = n.
// Szablon dla przypadkowego drzewa binarnego.
template <typename T>
class BinarySearchTree {
BSTNode<T> *root;
public:
BinarySearchTree() : root(nullptr) {} // konstruktor domyślny
~BinarySearchTree() { delete root; } // trzeba wyczyścić
void clear() { delete root; root = nullptr; }
bool empty() const { return root == nullptr; }
T& top() { assert(root != nullptr); return root->value; } // podgląd korzenia
void insert(const T& item) { root = insert(root, item); }
void remove(const T& item); // usuwanie przez złączanie
// Szukając element dostajemy wskaźnik do elementu lub nullptr.
T* search(const T& item) const {
auto ptr = search(root, item);
return ((ptr == nullptr) ? nullptr : &(ptr->value));
}
T* iter_search(const T& item) const { // wg libavl
for (auto node=root; node != nullptr; ) {
if (item == node->value) {
return &(node->value);
} else if (item < node->value) {
node = node->left;
} else {
node = node->right;
}
}
return nullptr;
}
T* find_min();
T* find_max();
void preorder() { preorder(root); }
void inorder() { inorder(root); }
void postorder() { postorder(root); }
void iter_preorder();
void iter_inorder(); // trudne
void iter_postorder(); // trudne
void bfs(); // przejście poziomami (wszerz)
void display() { display(root, 0); }
// Metody bezpośrednio odwołujące się do node.
// Mogą działać na poddrzewie.
BSTNode<T> * insert(BSTNode<T> *node, const T& item); // zwraca nowy korzeń
BSTNode<T> * search(BSTNode<T> *node, const T& item) const; // zwraca węzeł
BSTNode<T> * remove(BSTNode<T> *node); // zwraca nowy korzeń poddrzewa
void preorder(BSTNode<T> *node);
void inorder(BSTNode<T> *node);
void postorder(BSTNode<T> *node);
void display(BSTNode<T> *node, int level);
virtual void visit(BSTNode<T> *node) {
assert(node != nullptr);
std::cout << "visiting " << node->value << std::endl;
}
};
template <typename T>
BSTNode<T> * BinarySearchTree<T>::insert(BSTNode<T> *node, const T& item) {
if (node == nullptr) {
return new BSTNode<T>(item);
}
if (item < node->value) {
node->left = insert(node->left, item);
} else {
node->right = insert(node->right, item);
}
return node; // zwraca nowy korzeń
}
template <typename T>
BSTNode<T> * BinarySearchTree<T>::search(BSTNode<T> *node, const T& item) const {
if (node == nullptr || node->value == item) {
return node;
} else if (item < node->value) {
return search(node->left, item);
} else {
return search(node->right, item);
}
}
Rotacja drzewa (ang. tree rotation) jest operacją na drzewie BST, która zmienia jego lokalną strukturę bez zmiany kolejności elementów, przy przechodzeniu przez drzewo BST metodą inorder. Wyróżnia się dwie symetryczne operacje: rotacja w prawo i rotacja w lewo.
| X --[w prawo]-o Y | | / \ / \ | | Y C o-[w lewo]-- A X | | / \ / \ | | A B B C |
template <typename T>
BSTNode<T> * BinarySearchTree<T>::rotate_right(BSTNode<T> *node) {
if (node->left == nullptr)
return node; // bez zmian
BSTNode<T> *top = node; // węzeł X
node = top->left; // węzeł Y
top->left = node->right; // przepinamy węzeł B
node->right = top; // przepinamy węzeł X
return node; // zwracamy węzeł Y
}
template <typename T>
BSTNode<T> * BinarySearchTree<T>::rotate_left(BSTNode<T> *node) {
if (node->right == nullptr)
return node; // bez zmian
BSTNode<T> *top = node; // węzeł Y
node = top->right; // węzeł X
top->right = node->left; // przepinamy węzeł B
node->left = top; // przepinamy węzeł Y
return node; // zwracamy węzeł X
}
template <typename T>
void BinarySearchTree<T>::remove(const T& item) { // usuwanie przez złączanie
// Najpierw znajdujemy węzeł i jego rodzica.
BSTNode<T> *node = root;
BSTNode<T> *prev = nullptr;
while (node != nullptr) {
if (node->value == item)
break;
prev = node;
if (item < node->value) {
node = node->left;
} else {
node = node->right;
}
}
// Szukamy przyczyny przerwania pętli while.
if (node != nullptr && node->value == item) {
// node ma być usunięty.
if (node == root) {
root = remove(node);
} else if (prev->left == node) {
prev->left = remove(node);
} else {
prev->right = remove(node);
}
} else if (root != nullptr) {
; // klucza nie znaleziono
} else { // root == nullptr
; // drzewo jest puste
}
}
template <typename T>
BSTNode<T> * BinarySearchTree<T>::remove(BSTNode<T> *node) {
// Mamy usunąć węzeł i zwrócić nowy korzeń poddrzewa.
assert(node != nullptr);
BSTNode<T> *new_root;
if (node->right == nullptr) { // node nie ma prawego dziecka
new_root = node->left;
} else if (node->left == nullptr) { // node nie ma lewego dziecka
new_root = node->right;
} else { // obecne lewe i prawe dziecko
new_root = node; // zapisujemy stary korzeń
node = node->left; // idziemy w lewo
while (node->right != nullptr) { // idziemy w prawo do końca
node = node->right;
}
node->right = new_root->right; // prawe poddrzewo przełączone
node = new_root; // węzeł do usunięcia
new_root = node->left; // nowy korzeń
}
delete node;
return new_root;
}
| X Usuwamy węzeł X. | / \ Nowym korzeniem poddrzewa będzie Y. | Y C Y Z jest poprzednikiem X. | / \ / \ | A Z A Z | / / \ | B B C
https://en.wikipedia.org/wiki/Day%E2%80%93Stout%E2%80%93Warren_algorithm
Algorytm DSW (Day, Stout, Warren) służy do zrównoważenia drzewa BST. Algorytm działa w miejscu i w czasie O(n).
Napisać funkcje find_min() i find_max() znajdujące odpowiednio wartość najmniejszą i największą w drzewie BST. Funkcje powinny zwracać wskaźnik do wartości lub nullptr dla pustego drzewa.
Napisać funkcję find_successor() znajdujący następnik danego węzła przy przechodzeniu inorder (lub nullptr, jeżeli go nie ma). Węzły powinny posiadać łącze do rodzica.
Napisać funkcję find_predecessor() znajdujący poprzednik danego węzła przy przechodzeniu inorder (lub nullptr, jeżeli go nie ma). Węzły powinny posiadać łącze do rodzica.
Napisać funkcję sprawdzającą, czy drzewo binarne jest drzewem BST. Nie wystarczy sprawdzić dla każdego węzła, czy zachodzi node->left->value <= node->value, oraz node->value <= node->right->value. Musimy do węzła przekazać informację od rodzica o ograniczeniach na wartość przechowywaną w węźle.
| 5 Przykład drzewa binarnego, które nie jest drzewem BST. | / \ Wartość 6 jest większa od 3, ale nie jest mniejsza od 5. | 3 8 | / \ / \ | 1 6 7 9
Zaimplementować algorytm DSW.