Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <conio.h>
- #include <stdlib.h>
- using namespace std;
- const unsigned char KEY_MAX_LENGTH = 5;
- struct node {
- int key;
- unsigned char height;
- node* left;
- node* right;
- node(int k) { key = k; left = right = 0; height = 1; }
- };
- unsigned char height(node* p)
- {
- return p ? p->height : 0;
- }
- int bfactor(node* p)
- {
- return height(p->right) - height(p->left);
- }
- void fixheight(node* p)
- {
- unsigned char hl = height(p->left);
- unsigned char hr = height(p->right);
- p->height = (hl > hr ? hl : hr) + 1;
- }
- node* rotateright(node* p) // правый поворот вокруг p
- {
- node* q = p->left;
- p->left = q->right;
- q->right = p;
- fixheight(p);
- fixheight(q);
- return q;
- }
- node* rotateleft(node* q) // левый поворот вокруг q
- {
- node* p = q->right;
- q->right = p->left;
- p->left = q;
- fixheight(q);
- fixheight(p);
- return p;
- }
- node* balance(node* p) // балансировка узла p
- {
- fixheight(p);
- if (bfactor(p) == 2)
- {
- if (bfactor(p->right) < 0)
- p->right = rotateright(p->right);
- return rotateleft(p);
- }
- if (bfactor(p) == -2)
- {
- if (bfactor(p->left) > 0)
- p->left = rotateleft(p->left);
- return rotateright(p);
- }
- return p; // балансировка не нужна
- }
- node* insert(node* p, int k) // вставка ключа k в дерево с корнем p
- {
- if (!p) return new node(k);
- if (k < p->key)
- p->left = insert(p->left, k);
- else
- p->right = insert(p->right, k);
- return balance(p);
- }
- node* findmin(node* p) // поиск узла с минимальным ключом в дереве p
- {
- return p->left ? findmin(p->left) : p;
- }
- node* removemin(node* p) // удаление узла с минимальным ключом из дерева p
- {
- if (p->left == 0)
- return p->right;
- p->left = removemin(p->left);
- return balance(p);
- }
- node* remove(node* p, int k) // удаление ключа k из дерева p
- {
- if (!p) return 0;
- if (k < p->key)
- p->left = remove(p->left, k);
- else if (k > p->key)
- p->right = remove(p->right, k);
- else // k == p->key
- {
- node* q = p->left;
- node* r = p->right;
- delete p;
- if (!r) return q;
- node* min = findmin(r);
- min->right = removemin(r);
- min->left = q;
- return balance(min);
- }
- return balance(p);
- }
- bool search(node* p, int k) {
- bool res = false;
- if (p) {
- if (k == p->key)
- return true;
- if (k < p->key) {
- res = search(p->left, k);
- }
- if (k > p->key) {
- res = search(p->right, k);
- }
- }
- return res;
- }
- void printGL(node* p) {
- if (p) {
- if (p->left) {
- printGL(p->left);
- }
- for (int i = 0; i < p->height - 1; i++)
- cout << "\t";
- cout << p->key;
- cout << endl;
- if (p->right) {
- printGL(p->right);
- }
- }
- }
- void printSH(node* p) {
- if (p) {
- cout << p->key;
- for (int i = 0; i < p->height; i++) {
- cout << "*";
- }
- if (p->left)
- if (p->right)
- printGL(p->right);
- }
- }
- int main()
- {
- char ch = 0;
- do {
- node* p = nullptr;
- system("cls");
- cout << "Choose your destiny!\n";
- cout << "[1] - add\n[2] - remove\n[3] - search\n[4] - print\n";
- ch = _getch();
- switch (ch) {
- case '1':
- int a;
- cout << "Enter a key: ";
- cin >> a;
- if (!p) {
- p = new node(a);
- }
- else
- insert(p, a);
- cout << "insertion of " << a << " has been made succesfully";
- break;
- case '2':
- if (p) {
- cout << "Enter a key that you wanna remove: ";
- int a;
- cin >> a;
- remove(p, a);
- cout << "remove of " << a << " has been made succesfully";
- }
- else {
- cout << "Your tree is empty\n";
- }
- break;
- case '3':
- if (p) {
- cout << "Enter a key that you wanna remove: ";
- int a;
- cin >> a;
- remove(p, a);
- cout << "remove of " << a << " has been made succesfully";
- }
- else {
- cout << "Your tree is empty\n";
- }
- break;
- case '4':
- break;
- }
- } while (ch != 27);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement