Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <conio.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 = new node(10);
- p = insert(p, 44);
- p = insert(p, 66);
- p = insert(p, 152);
- p = insert(p, 0);
- p = insert(p, 55);
- p = insert(p, 11);
- printGL(p);
- cout << search(p, 111);
- ch = _getch();
- } while (ch != 27);
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement