Please disable Adblockers and enable JavaScript for domain CEWebS.cs.univie.ac.at! We have NO ADS, but they may interfere with some of our course material.
[Projekt]
Binärer Suchbaum als ADS_set
Als grobe Orientierung wird im folgenden ein ADS_set auf Basis der Datenstruktur Binärer Suchbaum implementiert. Bei einem binären Suchbaum gibt es nichts zu konfigurieren, der zweite Template-Parameter wird daher ignoriert.
template <typename Key, size_t = 0> class ADS_set
Datenstruktur
struct Node; using Link = Node*;
struct Node {
key_type key;
Link left;
Link right;
Node(const value_type& key, Link left = nullptr, Link right = nullptr) : key(key), left(left), right(right) {}
~Node() { delete left; delete right; }
};
Link root {nullptr};
size_t sz {0};
Die Knoten des Baums werden als struct Node realisiert, jede Instanz enthält ein Element und zwei Zeiger auf die Nachfolger.
Das ADS_set benötigt lediglich einen Zeiger auf die Wurzel des Baumes (root). Um die Laufzeitvorgabe für size() zu erfüllen, wird zusätzlich die Anzahl der Elemente in sz gespeichert.
Member types
using value_type = Key;
using key_type = Key;
using reference = key_type&;
using const_reference = const key_type&;
using size_type = size_t;
using difference_type = std::ptrdiff_t;
using iterator = Iterator;
using const_iterator = Iterator;
using key_compare = std::less<key_type>;
using key_equal = std::equal_to<key_type>;
Member functions
Konstruktoren
ADS_set() {}
ADS_set(std::initializer_list<key_type> ilist) {
insert(ilist);
}
template<typename InputIt> ADS_set(InputIt first, InputIt last) {
insert(first, last);
}
ADS_set(const ADS_set& other) {
root = clone(other.root);
sz = other.sz;
}
Ein leerer Baum wird durch einen nullptr dargestellt. Die korrekte Initialisierung der Instanzvariablen wid durch in-class initializer sichergestellt. Die Kopie eines Baumes wird mit der privaten Klassenmethode clone() realisiert, die rekursiv eine 1:1-Kopie erzeugt.
static Link clone(Link link) {
return link ? new Node(link->key, clone(link->left), clone(link->right)) : nullptr;
}
Alle Elemente von other mittels Iterator und insert() einzufügen, etwa
for (const key_type& key: other) insert(key);
ist bei vielen Datenstrukturen ein guter Anfang. Beim binären Baum hingegen nicht, da der Iterator die Elemente in Sortierreihenfolge liefert und das Einfügen in dieser Reihenfolge einen degenerierten Baum liefert (lineare Liste).
Destruktor
~ADS_set() { delete root; root = nullptr; }
Der Destruktor von ADS_set braucht lediglich den Wurzelknoten (sofern vorhanden) zu löschen. Der rekursive Destruktor von Node (siehe oben) entfernt dann rekursiv den gesamten Baum.
Zuweisungsoperatoren
ADS_set& operator=(const ADS_set& other) {
if (this == &other) return *this;
delete root;
root = clone(other.root);
sz = other.sz;
return *this;
}
ADS_set& operator=(std::initializer_list<key_type> ilist) {
clear();
insert(ilist);
return *this;
}
Der Kopierzuweisungsoperator benutzt clone, siehe oben.
Größe
size_type size() const { return sz; }
bool empty() const { return !sz; }
Einfügen
void insert(std::initializer_list<key_type> ilist) {
for (const key_type& key: ilist) insert_key(key);
}
std::pair<iterator,bool> insert(const key_type& key) {
size_type sz_before {sz};
Link link {insert_key(key)};
return std::make_pair(const_iterator{root, link}, sz != sz_before);
}
template<typename InputIt> void insert(InputIt first, InputIt last) {
while (first != last) insert_key(*first++);
}
Die Methoden rufen die private Methode insert_key auf.
Link insert_key(const key_type& key) {
Link& link {find(key, root)};
if (!link) {
link = new Node(key);
++sz;
}
return link;
}
Diese ruft die private Klassenmethode find auf. find liefert eine Referenz auf jenen Zeiger, der auf den gesuchten Knoten zeigt, falls dieser vorhanden ist. Falls der gesuchte Wert nicht im Baum gespeichert ist, liefert find eine Referenz auf jenen Zeiger, der auf den Knoten zeigen würde, wenn dieser vorhanden wäre.
static Link& find(const key_type& key, Link& link) {
if (!link || key_equal{}(link->key,key)) return link;
return find(key, key_compare{}(key, link->key) ? link->left : link->right);
}
Da die Verwendung von std::equal_to bei uns auch in Bäumen erlaubt ist, verwenden wir hier diese Vergleichsoperation (key_equal), um die Methode etwas zu verkürzen. Andernfalls wäre diese zB so zu implementieren:
static Link& find(const key_type& key, Link& link) {
if (!link) return link;
if (key_compare{}(key, link->key)) return find(key, link->left);
if (key_compare{}(link->key, key)) return find(key, link->right);
return link;
}
Löschen
void clear() {
delete root;
root = nullptr;
sz = 0;
}
size_type erase(const key_type& key) {
return erase_key(key);
}
clear entfernt mit Hilfe des rekursiven Node-Destruktors alle Knoten aus dem Baum. erase entfernt den Knoten mit dem Wert key mit Hilfe der privaten Methode erase_key.
size_type erase_key(const key_type& key) {
if (Link& link {find(key, root)}) {
delete unlink(link);
--sz;
return 1;
}
return 0;
}
erase_key sucht den Knoten mittels find (siehe oben). Ist der gesuchte Knoten vorhanden, wird er mittels unlink aus dem Baum entfernt und dann gelöscht.
static Link unlink(Link& link) {
Link old_link = link;
if (!old_link->left) {
link = old_link->right;
} else if (!old_link->right) {
link = old_link->left;
} else {
link = unlink_min(link->right);
link->left = old_link->left;
link->right = old_link->right;
}
old_link->left = old_link->right = nullptr;
return old_link;
}
unlink unterscheidet beim Entfernen eines Knotens vier Fälle (wobei Fall 1 und 2 im Code gleich behandelt werden):
- Der Knoten ist ein Blatt: Er kann einfach entfernt werden.
- Der Knoten hat keinen linken Nachfolger: Er wird durch seinen rechten Nachfolger ersetzt.
- Der Knoten hat keinen rechten Nachfolger: Er wird durch seinen linken Nachfolger ersetzt.
- Der Knoten hat zwei Nachfolger: Er wird durch den kleinsten Knoten im rechten Teilbaum ersetzt (alternativ wäre der größte im linken möglich). Die Entfernung des kleinsten Knoten im rechten Teilbaum wird von unlink_min erledigt.
static Link unlink_min(Link& link) {
if (link->left) return unlink_min(link->left);
Link min_link = link;
link = min_link->right;
min_link->right = nullptr;
return min_link;
}
Suchen
size_type count(const key_type& key) const {
return !!find_key(key);
}
iterator find(const key_type& key) const {
if (Link link {find_key(key)}) return const_iterator{root, link};
return end();
}
Während count je nach Erfolg 1 oder 0 liefert, liefert find einen Iterator auf das vorhandene Element oder end(). Beide Methoden verwenden find_key, dieses wiederum setzt für die eigentliche Arbeit auf das schon bekannte private find.
Link find_key(const key_type& key) const {
Link root_copy {root};
return find(key, root_copy);
}
Iteratoren
const_iterator begin() const { return const_iterator{root}; }
const_iterator end() const { return const_iterator{}; }
Siehe unten.
Debugging
void dump(std::ostream& o = std::cerr) const {
dump(root, o);
}
Die Methode dump gibt alle im binären Baum gespeicherten Werte auf den als Parameter übergebenen Stream o aus. Um die Struktur des Baumes zu verdeutlichen, geben wir die Werte in inorder-Reihenfolge aus und rücken je nach Ebene des Knotens entsprechend ein, sodass ein von links nach rechts wachsender Baum dargestellt wird. Die eigentliche Ausgabe erfolgt rekursiv durch die private Klassenmethode dump:
static void dump(Link link, std::ostream &o, size_t ind = 0) {
if (!link) return;
dump(link->right, o, ind+1);
o << std::setw(ind*4) << "" << link->key << '\n';
dump(link->left, o, ind+1);
}
Non-member functions
friend bool operator==(const ADS_set& lhs, const ADS_set& rhs) {
if (lhs.size() != rhs.size()) return false;
auto lhs_it = lhs.begin();
auto rhs_it = rhs.begin();
for ( ; lhs_it != lhs.end(); ++lhs_it, ++rhs_it) if (!key_equal{}(*lhs_it, *rhs_it)) return false;
return true;
}
friend bool operator!=(const ADS_set& lhs, const ADS_set& rhs) { return !(lhs==rhs); }
Der Vergleichsoperator prüft, ob die beiden ADS_sets gleich groß sind und alle Elemente von lhs auch in rhs enthalten sind. Da die Iteratoren die Elemente in Sortierreihenfolge liefern, müssen beide Iteratoren dieselbe Sequenz von Elementen liefern, andernfalls sind die beiden ADS_sets nicht gleich.
template <typename Key, size_t N>
void swap(ADS_set<Key,N>& lhs, ADS_set<Key,N>& rhs) { lhs.swap(rhs); }
Iterator für den binären Suchbaum
Gleich vorweg: der Iterator für den binären Suchbaum ist wesentlich aufwändiger als die Iteratoren, die im Rahmen des Projektes zu implementieren sind. Der binäre Suchbaum ist eine rekursive Datenstruktur. Die meisten Operationen lassen sich daher rekursiv sehr elegant implementieren. Für die Iterator-Operationen trifft das leider nicht zu. Insbesondere das Auffinden des jeweils nächsten Elements ist schwieriger als in "linearen" Datenstrukturen[9]. Die brute-force-Methode, alle Elemente bzw. Zeiger auf die Elemente vorübergehend in eine Liste o.ä. zu kopieren, um sie dann abzuarbeiten, werden wir aus Effizienzgründen nicht weiter betrachten. Es bieten sich zwei Optionen an:
- Erweiterung der Datenstruktur zu einem "doppelt verketteten" binären Suchbaum. Jeder Knoten erhält neben den Zeigern auf seine Nachfolger einen zusätzlichen Zeiger auf seinen Vorgänger. Dies verkompliziert die meisten anderen Operationen und verschlechtert die ohnehin nicht berauschende Speicherplatzausnutzung.
- Verwendung einer Hilfsdatenstruktur im Iterator. Dies kann zu erheblichem Speicherbedarf im Iterator führen (bei degenerierten Bäumen entsteht derselbe Aufwand wie bei der brute-force-Methode von oben).
Wir entscheiden uns für Variante 2 und verwenden einen Stack, der jene Knoten auf dem Pfad von der Wurzel bis zum aktuellen Knoten enthält, die "rechts" vom aktuellen Knoten liegen (also noch zu bearbeiten sind). Das oberste Element im Stack (top) ist der aktuelle Knoten. Wir verwenden std::stack aus der STL. Grundsätzlich ist die Verwendung der STL für die Implementierung der Datenstruktur nicht zulässig. In speziellen Fällen wie diesem kann es zulässig sein, bitte unbedingt vorher nachfragen (Forum).
std::stack<Link> path;
Der Konstruktor kann auf drei Arten genutzt werden. Ohne Parameter wird ein end-Iterator erzeugt, mit einem Parameter wird ein begin-Iterator erzeugt. Mit zwei Parametern wird ein Iterator auf den übergebenen Knoten erzeugt.
explicit Iterator(Link root = nullptr, Link current = nullptr) {
if (!root) return; // end
if (!current) { // begin
path.push(root);
while (path.top()->left) path.push(path.top()->left);
return;
}
Link link {root};
while (link != current) {
if (key_compare{}(current->key, link->key)) {
path.push(link);
link = link->left;
} else {
link = link->right;
}
}
path.push(link);
}
Der end-Iterator wir durch einen leeren Stack repräsentiert.
Zur Erzeugung des begin-Iterators wird der kleinste (d.h., der am weitesten links liegende) Knoten gesucht. Alle Knoten auf dem Pfad von der Wurzel zum kleinsten Knoten liegen naturgemäß rechts vom gesuchten Knoten und werden daher in den Stack eingetragen.
Bei einem Iterator für einen "normalen" Knoten wird der Baum wie üblich traversiert um den Knoten zu suchen, und dabei jene Knoten in den Stack eingetragen, die rechts vom gesuchten Knoten liegen.
Der aktuelle Knoten liegt (sofern es einen gibt) immer oben auf dem Stack, die Zugriffsoperationen sind daher einfach:
reference operator*() const { return path.top()->key; }
pointer operator->() const { return &path.top()->key; }
Beim Weiterschalten zum nächsten Knoten wird der aktuelle Knoten vom Stack entfernt. Der linke Nachfolger das aktuellen Knotens ist bereits bearbeitet worden. Es geht daher mit dem rechten Nachfolger weiter, sofern es einen gibt. Zu diesem Zweck wird der kleinste (linkeste) Knoten im rechten Unterbaum gesucht und der Pfad dorthin auf den Stack gelegt (so wie beim begin-Iterator).
Iterator& operator++() {
Link old_top = path.top();
path.pop();
if (old_top->right) {
path.push(old_top->right);
while (path.top()->left) path.push(path.top()->left);
}
return *this;
}
Iterator operator++(int) { Iterator tmp{*this}; ++*this; return tmp; }
Vergleichsoperatoren: zwei Iteratoren sind dann gleich, wenn der Stack path in beiden Iteratoren gleich ist. Um den u.U. aufwändigen Vergleich der beiden Stacks zu vermeiden, beschränken wir uns darauf, den aktuellen Knoten zu vergleichen, sofern es einen gibt. Dies ist in unserem Fall äquivalent.
friend bool operator==(const Iterator& lhs, const Iterator& rhs) {
return lhs.path.size() == rhs.path.size() && (lhs.path.empty() || lhs.path.top() == rhs.path.top());
}
friend bool operator!=(const Iterator& lhs, const Iterator& rhs) { return !(lhs == rhs); }
Download
- 9
- Der B+-Baum ist zwar auch eine Baumstruktur, aber durch das Verketten der Blattknoten kann die Situation massiv vereinfacht werden.
Letzte Änderung: 04.10.2018, 18:56 | 1804 Worte