Löschen eines Knotens aus dem Binärer Suchbaum in C++
In diesem Artikel wird erläutert, wie Sie eine Funktion zum Löschen eines Knotens in der Binärer Suchbaum-Datenstruktur C++ implementieren.
Knoten im Binärer Suchbaum in C++ löschen
Ein binärer Suchbaum ist eine Art von binärem Baum, der einen Schlüsselwert in jedem Knoten speichert. Dieser Schlüssel wird verwendet, um einen geordneten Baum zu konstruieren, so dass der Schlüssel jedes Knotens größer ist als alle Schlüssel in seinem linken Teilbaum und kleiner als Schlüssel in seinem rechten Teilbaum.
Jeder Knoten enthält normalerweise zwei Zeiger auf den left und den right Knoten, aber wir haben auch einen weiteren Zeiger hinzugefügt, um den übergeordneten Knoten zu kennzeichnen, da es einfacher ist, die Member-Funktion remove zu implementieren.
Beachten Sie, dass die folgende binäre Suchbaumimplementierung nur das absolute Minimum der Memberfunktionen enthält, um einen Vorgang zum Entfernen eines Knotens zu demonstrieren.
Die Klasse BinSearchTree kann nur int-Typen als Schlüsselwerte speichern. Die meisten Funktionen außer remove verwenden Rekursion, daher stellen wir entsprechende private Member-Funktionen bereit, die intern aufgerufen werden. Im Allgemeinen ist das Entfernen eines Knotens aus dem Baum ein komplexerer Vorgang als das Einfügen und Suchen, da mehrere Szenarien erforderlich sind.
Das erste und einfachste Szenario ist, wenn wir einen Knoten ohne Kinder entfernen müssen (nachfolgend als Blattknoten bezeichnet). Blattknoten können freigegeben und nullptr dem entsprechenden Zeiger ihres Elternteils zugewiesen werden.
Der zweite Fall ist das Entfernen des Knotens mit nur einem Kind. Letzteres kann gelöst werden, indem das Elternteil des Ziels mit seinem Kind verbunden wird, und dann können wir den zugeordneten Speicher freigeben.
#include <iostream>
using std::cerr;
using std::cout;
using std::endl;
using std::string;
struct BSTreeNode {
int key{};
BSTreeNode *parent{};
BSTreeNode *left{};
BSTreeNode *right{};
} typedef BSTreeNode;
class BinSearchTree {
public:
BinSearchTree() {
root = nullptr;
size = 0;
};
BinSearchTree(std::initializer_list<int> list);
void insert(int k);
BSTreeNode *find(int k);
int remove(int k);
void print();
size_t getSize() const;
~BinSearchTree();
private:
BSTreeNode *root;
size_t size;
void freeNodes(BSTreeNode *&rnode);
void printTree(BSTreeNode *node);
void insertNode(BSTreeNode *&rnode, int k, BSTreeNode *pnode);
BSTreeNode **findNode(BSTreeNode *&rnode, int k);
};
BinSearchTree::BinSearchTree(std::initializer_list<int> list) {
root = nullptr;
size = 0;
for (const auto &item : list) {
insertNode(root, item, nullptr);
}
}
BinSearchTree::~BinSearchTree() { freeNodes(root); }
void BinSearchTree::freeNodes(BSTreeNode *&rnode) {
if (rnode != nullptr) {
freeNodes(rnode->left);
freeNodes(rnode->right);
delete rnode;
}
}
BSTreeNode *BinSearchTree::find(const int k) { return *findNode(root, k); }
BSTreeNode **BinSearchTree::findNode(BSTreeNode *&rnode, const int k) {
if (rnode == nullptr) return nullptr;
if (k == rnode->key) return &rnode;
if (k < rnode->key)
return findNode(rnode->left, k);
else
return findNode(rnode->right, k);
}
void BinSearchTree::print() {
if (size > 0)
printTree(root);
else
cout << "tree is empty!" << endl;
}
void BinSearchTree::printTree(BSTreeNode *rnode) {
if (rnode != nullptr) {
printTree(rnode->left);
cout << rnode->key << "; ";
printTree(rnode->right);
}
}
void BinSearchTree::insert(const int k) { insertNode(root, k, nullptr); }
void BinSearchTree::insertNode(BSTreeNode *&rnode, const int k,
BSTreeNode *pnode) {
if (rnode == nullptr) {
rnode = new BSTreeNode;
rnode->key = k;
rnode->parent = pnode;
rnode->left = nullptr;
rnode->right = nullptr;
size++;
} else {
if (k < rnode->key)
insertNode(rnode->left, k, rnode);
else if (k == rnode->key)
return;
else
insertNode(rnode->right, k, rnode);
}
}
size_t BinSearchTree::getSize() const { return size; }
int BinSearchTree::remove(const int k) {
auto ret = findNode(root, k);
if (ret == nullptr) return -1;
if (size == 1) {
auto tmp = root;
root = nullptr;
delete tmp;
size--;
return 0;
}
if ((*ret)->left == nullptr && (*ret)->right == nullptr) {
auto tmp = *ret;
if ((*ret)->key < (*ret)->parent->key)
(*ret)->parent->left = nullptr;
else
(*ret)->parent->right = nullptr;
delete tmp;
size--;
return 0;
}
if ((*ret)->left != nullptr && (*ret)->right != nullptr) {
auto leftmost = (*ret)->right;
while (leftmost && leftmost->left != nullptr) leftmost = leftmost->left;
(*ret)->key = leftmost->key;
if (leftmost->right != nullptr) {
leftmost->right->parent = leftmost->parent;
auto tmp = leftmost->right;
*leftmost = *leftmost->right;
leftmost->parent->left = leftmost;
delete tmp;
} else {
leftmost->parent->right = nullptr;
delete leftmost;
}
size--;
return 0;
} else {
if ((*ret)->left != nullptr) {
auto tmp = *ret;
*ret = (*ret)->left;
(*ret)->parent = tmp->parent;
delete tmp;
} else {
auto tmp = *ret;
*ret = (*ret)->right;
(*ret)->parent = tmp->parent;
delete tmp;
}
size--;
return 0;
}
}
int main() {
BinSearchTree bst = {6, 5, 11, 3, 2, 10, 12, 4, 9};
cout << "size of bst = " << bst.getSize() << endl;
bst.print();
cout << endl;
bst.insert(7);
bst.insert(8);
cout << "size of bst = " << bst.getSize() << endl;
bst.print();
cout << endl;
bst.remove(6);
bst.remove(2);
bst.remove(12);
cout << "size of bst = " << bst.getSize() << endl;
bst.print();
cout << endl;
return EXIT_SUCCESS;
}
size of bst = 9
2; 3; 4; 5; 6; 9; 10; 11; 12;
size of bst = 11
2; 3; 4; 5; 6; 7; 8; 9; 10; 11; 12;
size of bst = 8
3; 4; 5; 7; 8; 9; 10; 11;
Das komplizierteste Szenario ist, wenn der Zielknoten zwei Kinder hat. In diesem Fall müssen wir die Knoten korrekt verbinden und die Elementreihenfolge beibehalten, wie sie für die binäre Suchbaumstruktur angegeben ist. Wir müssen den Zielknoten durch den kleinsten Schlüssel und einen Teil des rechten Unterbaums des Ziels ersetzen.
Der Knoten mit dem kleinsten Schlüssel befindet sich ganz links. Daher sollten wir den rechten Teilbaum durchlaufen, bis wir diesen Knoten erreichen. Sobald der Knoten gefunden wurde, können wir dem Zielknoten seinen Schlüssel zuweisen und dann versuchen, den ersten zu entfernen, als wäre es ein Knoten mit einem einzigen Kind. Letzteres wird dadurch impliziert, dass dieser Knoten der am weitesten links stehende Knoten im gegebenen Teilbaum ist. Es kann also nur ein right oder gar kein Kind haben.
Diese drei Szenarien werden in einem separaten if...else-Block in der Member-Funktion remove implementiert, aber wir fügen auch zusätzlichen Code hinzu, um auf einige Eckfälle zu prüfen, z. B. wenn das Element nicht im Baum gefunden wird oder der letzte Knoten entfernt wird . Beachten Sie, dass die Funktion remove auch rekursiv implementiert werden kann.
Founder of DelftStack.com. Jinku has worked in the robotics and automotive industries for over 8 years. He sharpened his coding skills when he needed to do the automatic testing, data collection from remote servers and report creation from the endurance test. He is from an electrical/electronics engineering background but has expanded his interest to embedded electronics, embedded programming and front-/back-end programming.
LinkedIn Facebook