107 lines
2.8 KiB
C++
Executable File
107 lines
2.8 KiB
C++
Executable File
#include <ctime>
|
|
#include <iostream>
|
|
|
|
using namespace std;
|
|
|
|
struct Node {
|
|
int key;
|
|
int count;
|
|
Node *left;
|
|
Node *right;
|
|
int height;
|
|
Node(int value) : key(value), left(nullptr), right(nullptr), height(0), count(1) {}
|
|
};
|
|
|
|
int getHeight(Node *node) {
|
|
return (node == nullptr) ? -1 : node->height;
|
|
}
|
|
|
|
void updateHeight(Node *&node) {
|
|
node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
|
|
}
|
|
|
|
void insert(Node *&node, int key) {
|
|
if (node->key > key) {
|
|
if (node->left == nullptr) node->left = new Node(key);
|
|
else insert(node->left, key);
|
|
}
|
|
else if (node->key < key) {
|
|
if (node->right == nullptr) node->right = new Node(key);
|
|
else insert(node->right, key);
|
|
}
|
|
else node->count++;
|
|
|
|
updateHeight(node);
|
|
}
|
|
|
|
Node *search(Node *&node, int key) {
|
|
if (node == nullptr) return nullptr;
|
|
if (node->key == key) return node;
|
|
return search((node->key > key) ? node->left : node->right, key);
|
|
}
|
|
|
|
Node *getMin(Node *&node) {
|
|
if (node == nullptr) return nullptr;
|
|
if (node->left == nullptr) return node;
|
|
return getMin(node->left);
|
|
}
|
|
|
|
Node *getMax(Node *&node) {
|
|
if (node == nullptr) return nullptr;
|
|
if (node->right == nullptr) return node;
|
|
return getMax(node->right);
|
|
}
|
|
|
|
Node *deleteNode(Node *&node, int key) {
|
|
if (node == nullptr) return nullptr;
|
|
else if (node->key > key) node->left = deleteNode(node->left, key);
|
|
else if (node->key < key) node->right = deleteNode(node->right, key);
|
|
else if (node->key == key && node->count != 1) node->count--;
|
|
else {
|
|
if (node->left == nullptr || node->right == nullptr)
|
|
node = (node->left == nullptr) ? node->right : node->left;
|
|
else {
|
|
Node *maxLeft = getMax(node->left);
|
|
node->key = maxLeft->key;
|
|
node->left = deleteNode(node->left, maxLeft->key);
|
|
}
|
|
}
|
|
if (node != nullptr) updateHeight(node);
|
|
return node;
|
|
}
|
|
|
|
void printTree(Node *node) {
|
|
if (node == nullptr) return;
|
|
printTree(node->left);
|
|
cout << node->key << " (" << node->count << ") ";
|
|
printTree(node->right);
|
|
}
|
|
|
|
Node *generateRandomTree(int countOfNodes) {
|
|
Node *root = new Node(rand() % 100);
|
|
for (; countOfNodes > 0; countOfNodes--) insert(root, rand() % 100);
|
|
return root;
|
|
}
|
|
|
|
int main() {
|
|
srand(time(0));
|
|
|
|
Node *root = generateRandomTree(10);
|
|
cout << "root: " << root->key << endl;
|
|
printTree(root);
|
|
cout << endl;
|
|
insert(root, 9);
|
|
cout << "root: " << root->key << endl;
|
|
printTree(root);
|
|
cout << endl;
|
|
cout << "height: " << root->height + 1 << endl;
|
|
Node *buffer = search(root, 9);
|
|
cout << buffer << endl;
|
|
cout << "root: " << root->key << endl;
|
|
root = deleteNode(root, 9);
|
|
printTree(root);
|
|
cout << endl;
|
|
|
|
return 0;
|
|
}
|