Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- //
- // main.cpp
- // AiSD34
- //
- // Created by Andrey Bondar on 19.12.14.
- // Copyright (c) 2014 Andrey Bondar. All rights reserved.
- //
- #include <iostream>
- using namespace std;
- struct node // структура для представления узлов дерева
- {
- int key;
- unsigned char height;
- node* left;
- node* right;
- node(int k) { key = k; left = right = 0; height = 1; }
- };
- unsigned int height(node* r)
- {
- return r ? r->height:0;
- }
- int bfactor(node* r)
- {
- return height(r->right)-height(r->left);
- }
- void fixheight(node* r)
- {
- unsigned int hl = height(r->left);
- unsigned int hr = height(r->right);
- r->height = (hl>hr?hl:hr)+1;
- }
- class AVLtree {
- public:
- void insert(int k) {
- root = insert_real(root, k);
- }
- void remove(int k) {
- root = delete_elem(root, k);
- }
- AVLtree();
- node *root;
- void deleteNode(node*& r) {
- if( r->left != 0 ) {
- deleteNode(r->left);
- }
- if( r->right != 0 ) {
- deleteNode(r->right);
- }
- delete r;
- }
- ~AVLtree() {
- if( root != 0 ) {
- deleteNode(root);
- }
- }
- private:
- node* rightRot(node *r);
- node* leftRot(node *r);
- node* balance(node *r);
- node* insert_real(node *r, int k);
- node* find_min(node *r);
- node* del_min(node *r);
- node* delete_elem(node *r, int k);
- };
- AVLtree::AVLtree() : root(0) {}
- node* AVLtree::rightRot(node *r) {
- node *newRoot = r->left;
- r->left = newRoot->right;
- newRoot->right = r;
- fixheight(r);
- fixheight(newRoot);
- return newRoot;
- }
- node* AVLtree::leftRot(node *r) {
- node *newRoot = r->right;
- r->right = newRoot->left;
- newRoot->left = r;
- fixheight(r);
- fixheight(newRoot);
- return newRoot;
- }
- node* AVLtree::balance(node *r)
- {
- fixheight(r);
- if( bfactor(r) == 2 ) {
- if (bfactor(r->right) < 0)
- {
- r->right = rightRot(r->right);
- }
- return leftRot(r);
- }
- if( bfactor(r) == -2) {
- if( bfactor(r->left) > 0)
- {
- r->left = leftRot(r->left);
- }
- return rightRot(r);
- }
- return r;
- }
- node* AVLtree::insert_real(node *r, int k)
- {
- if (!r) return new node(k);
- if (k < r->key)
- {
- r->left = insert_real(r->left, k);
- }
- else {
- r->right = insert_real(r->right, k);
- }
- return balance(r);
- }
- node* AVLtree::find_min(node *r) {
- return r->left ? find_min(r->left) : r;
- }
- node* AVLtree::del_min(node *r) {
- if (r->left == 0) {
- return r->right;
- }
- r->left = del_min(r->left);
- return balance(r);
- }
- node* AVLtree::delete_elem(node *r, int k) {
- if( !r ) return 0;
- if( k < r->key )
- r->left = delete_elem(r->left,k);
- else if( k > r->key )
- {
- r->right = delete_elem(r->right,k);
- }
- else
- {
- node* left = r->left;
- node* right = r->right;
- delete r;
- if( !right ) return left;
- node* min = find_min(right);
- min->right = del_min(right);
- min->left = left;
- return balance(min);
- }
- return balance(r);
- }
- int main(int argc, const char * argv[]) {
- int input = 0;
- AVLtree* tree = new AVLtree();
- while (cin >> input) {
- if (input > 0) {
- tree->insert(input);
- }
- else{
- tree->remove(-input);
- }
- }
- cout << height(tree->root);
- delete tree;
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement