AVL Tree

gistfile1.cpp

//
//  main.cpp
//  LAB3_AlDate
//
//  Created by Alexander on 23.11.13.
//  Copyright (c) 2013 AlexO. All rights reserved.
//

#include <iostream>
struct CNode {
    int Key;
	int Height;
    CNode* Left;
	CNode* Right;
    
	CNode(int key) : Key(key), Height(1), Left(0), Right(0) {}
};


extern __inline__ uint64_t rdtsc() {
    uint64_t x;
    __asm__ volatile ("rdtsc\n\tshl $32, %%rdx\n\tor %%rdx, %%rax" : "=a" (x) : : "rdx");
    return x;
}


int Height(CNode* p)
{
	return p == 0 ? 0 : p->Height;
}

int BalanceFactor(CNode* p)
{
	return Height(p->Left) - Height(p->Right);
}

CNode* RotateRight(CNode* p) {
    CNode* q = p->Left;
    p->Left = q->Right;
    q->Right = p;
    p->Height = std::max(Height(p->Left), Height(p->Right)) + 1;
	q->Height = std::max(Height(q->Left), Height(q->Right)) + 1;
	return q;
}

CNode* RotateLeft(CNode* p)
{
	CNode* q = p->Right;
	p->Right = q->Left;
	q->Left = p;
	p->Height = std::max(Height(p->Left), Height(p->Right)) + 1;
	q->Height = std::max(Height(q->Left), Height(q->Right)) + 1;
	return q;
}

CNode* Balance(CNode* p)
{
	int balanceFactor = BalanceFactor(p);
	if( balanceFactor == -2 ) {
		if( BalanceFactor(p->Right) > 0 ) {
			p->Right = RotateRight(p->Right);
		}
		return RotateLeft(p);
	}
	if( balanceFactor == 2 ) {
		if( BalanceFactor(p->Left) < 0 ) {
			p->Left = RotateLeft(p->Left);
		}
		return RotateRight(p);
	}
	p->Height = std::max(Height(p->Left), Height(p->Right)) + 1;
	return p;
}

CNode* Insert(CNode* p, int key)
{
	if( p == 0 ) {
		return new CNode(key);
	}
	if( key < p->Key ) {
		p->Left = Insert(p->Left, key);
	} else {
		p->Right = Insert(p->Right, key);
	}
	return Balance(p);
}

CNode* Findmin(CNode* p) // поиск узла с минимальным ключом в дереве p
{
    return p->Left?Findmin(p->Left):p;
}

CNode* RemoveMin(CNode *p) {
    if( p->Left==0 ) {
        return p->Right;
    }
    p->Left = RemoveMin(p->Left);
    return Balance(p);
}

CNode* Remove(CNode* p, int key) {
    if( p == NULL) return 0;
    if( key < p->Key )
        p->Left = Remove(p->Left,key);
    else if( key > p->Key )
        p->Right = Remove(p->Right,key);
    else {
        CNode* l = p->Left;
        CNode* r = p->Right;
        delete p;
        if (r == NULL)
            return l;
        CNode* min = Findmin(r);
        min->Right = RemoveMin(r);
        min->Left = l;
        return Balance(min);
    }
    return Balance(p);
}


int Count( CNode* AVLTree )
{
    if( AVLTree == NULL )
        return 0;
    return std::max(Count( AVLTree->Left ), Count( AVLTree->Right )) + 1;
}

void free(CNode* node) {
    if (node == NULL)
        return;
    CNode *bufLeft = node->Left;
    CNode *bufRight = node->Right;
    delete node;
    
    free(bufLeft);
    free(bufRight);
}


CNode *find(CNode *tree, int val) {
    if (tree == NULL) {
        return NULL;
    }
    if (tree->Key == val) {
        return tree;
    }
    if( val < tree->Key ) {
		tree->Left = Insert(tree->Left, val);
	} else {
		tree->Right = Insert(tree->Right, val);
	}
    return NULL;
}

int main(int argc, const char * argv[])
{
    long long int start;
    srand(time(NULL));
    

    CNode *tree = NULL;
    freopen("test3.txt","r",stdin);
    int buf;
    int count = 1;
    
    for (int i = 0; i < 25000000; i++) {
        scanf("%i", &buf);
        tree = Insert(tree, buf);
        
        if (!(i % count)) {
            if (count < 25000) {
                count *= 10;
            }
            //std::cout << i << "\n";
           
            start = rdtsc();
            tree = Insert(tree, i);
            std::cout << rdtsc() - start << "\n";
            
            
        }
    }
    
    
    /*for (int i = 0; i < 255; i++) {
        scanf("%i", &buf);
        
        start = rdtsc();
        tree = Remove(tree, buf);
        
        Remove(tree, buf);
        std::cout << (rdtsc() - start) << "\n";
        
        tree = Insert(tree, buf);
        
    }
    
    
    
    for (int i = 0; i < 1000; i++) {
        scanf("%i", &buf);
        tree = Insert(tree, buf);
        if (!(i % 10)) {
            //std::cout << i << "\n";
            std::cout << tree->Height << "\n";
        }
    }*/

    
    // insert code here...
    //std::cout << tree->Height;
    free(tree);
    
    return 0;
}