Комменты к реализации Красно-черного и АВЛ дерева

//
//  main.cpp
//  RBTree
//
//  Created by Alexander on 15.02.14.
//  Copyright (c) 2014 Alexander. All rights reserved.
//
 
//======================================================================================================
 
#include <stdio.h>
#include <stdlib.h>
#include <iostream>
 
using std::max;
 
extern __inline__ uint64_t rdtsc() {
    uint64_t x;
    __asm__ volatile ("rdtsc\n\tshl $32, %%rdx\n\tor %%rdx, %%rax" : "=a" (x) : : "rdx");
    return x;
}
 
 
#define RED     1
#define BLACK   2
 
struct node {
    int key;
    struct node *left, *right, *p;
    int color;
};
 
typedef struct node *NODEPTR;
struct node NIL;
NODEPTR NILPTR = &NIL;
 
void inorder(NODEPTR x) {
    if (x != NILPTR) {
        inorder(x->left);
        printf("%d ", x->key);
        inorder(x->right);
    }
}
 
NODEPTR search(NODEPTR root, int k) {
    if (root == NILPTR || root->key == k)
        return root;
    if (k < root->key)
        return search(root->left, k);
    else
        return search(root->right, k);
}
 
NODEPTR minimum(NODEPTR root) {
    while (root->left != NILPTR)
        root = root->left;
    return root;
}
 
NODEPTR maximum(NODEPTR root) {
    while (root->right != NILPTR)
        root = root->right;
    return root;
}
 
NODEPTR successor(NODEPTR root, int x) {
    NODEPTR temp = search(root, x);
    if (temp == NILPTR) {
        printf("%d not in tree\n", x);
        return temp;
    }
    if (temp->right != NILPTR)
        return minimum(temp->right);
    NODEPTR y = temp->p;
    while (y != NILPTR && temp == y->right) {
        temp = y;
        y = y->p;
    }
    return y;
}
 
NODEPTR predecessor(NODEPTR root, int x) {
    NODEPTR temp = search(root, x);
    if (temp == NILPTR) {
        printf("%d not in tree\n", x);
        return temp;
    }
    if (temp->left != NILPTR)
        return maximum(temp->left);
    NODEPTR y = temp->p;
    while (y != NILPTR && temp == y->left) {
        temp = y;
        y = y->p;
    }
    return y;
}
void leftrotate(NODEPTR *treeroot, NODEPTR x) {
    NODEPTR y = x->right;
    x->right = y->left;
    if (y->left != NILPTR)
        y->left->p = x;
    y->p = x->p;
    if (x->p == NILPTR)
        *treeroot = y;
    else if (x->p->left == x)
        x->p->left = y;
    else
        x->p->right = y;
    y->left = x;
    x->p = y;
}
 
void rightrotate(NODEPTR *treeroot, NODEPTR y) {
    NODEPTR x = y->left;
    y->left = x->right;
    if (x->right != NILPTR)
        x->right->p = y;
    x->p = y->p;
    if (y->p == NILPTR)
        *treeroot = x;
    else if (y->p->left == y)
        y->p->left = x;
    else
        y->p->right = x;
    x->right = y;
    y->p = x;
}
 
void rbinsertfixup(NODEPTR *treeroot, NODEPTR z) {
    while (z->p->color == RED) {
        if (z->p == z->p->p->left) {
            NODEPTR y = z->p->p->right;
            if (y->color == RED) {
                z->p->color = BLACK;
                y->color = BLACK;
                z->p->p->color = RED;
                z = z->p->p;
            }
            else {
                if (z == z->p->right) {
                    z = z->p;
                    leftrotate(treeroot,z);
                }
                z->p->color = BLACK;
                z->p->p->color = RED;
                rightrotate(treeroot,z->p->p);
            }
        }
        else {
            NODEPTR y = z->p->p->left;
            if (y->color == RED) {
                z->p->color = BLACK;
                y->color = BLACK;
                z->p->p->color = RED;
                z = z->p->p;
            }
            else {
                if (z == z->p->left) {
                    z = z->p;
                    rightrotate(treeroot,z);
                }
                z->p->color = BLACK;
                z->p->p->color = RED;
                leftrotate(treeroot,z->p->p);
            }
        }
    }
    (*treeroot)->color = BLACK;
}
 
void rbinsert(NODEPTR *treeroot, int z) {
    NODEPTR Z = (NODEPTR) malloc(sizeof(struct node));
    Z->key = z;
    NODEPTR y = NILPTR;
    NODEPTR x = *treeroot;
    while (x != NILPTR) {
        y = x;
        if (Z->key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    Z->p = y;
    if (y == NILPTR)
        *treeroot = Z;
    else if (Z->key < y->key)
        y->left = Z;
    else
        y->right = Z;
    Z->left = NILPTR;
    Z->right = NILPTR;
    Z->color = RED;
    rbinsertfixup(treeroot,Z);
}
 
void rbtransplant(NODEPTR *treeroot, NODEPTR u, NODEPTR v) {
    if (u->p == NILPTR)
        *treeroot = v;
    else if (u == u->p->left)
        u->p->left = v;
    else
        u->p->right = v;
    v->p = u->p;
}
 
void rbdeletefixup(NODEPTR *treeroot, NODEPTR x) {
    while (x != *treeroot && x->color == BLACK) {
        if (x == x->p->left) {
            NODEPTR w = x->p->right;
            if (w->color == RED) {
                w->color = BLACK;
                x->p->color = RED;
                leftrotate(treeroot,x->p);
                w = x->p->right;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                w->color = RED;
                x = x->p;
            }
            else {
                if (w->right->color == BLACK) {
                    w->left->color = BLACK;
                    w->color = RED;
                    rightrotate(treeroot,w);
                    w = x->p->right;
                }
                w->color = x->p->color;
                x->p->color = BLACK;
                w->right->color = BLACK;
                leftrotate(treeroot,x->p);
                x = *treeroot;
            }
        }
        else {
            NODEPTR w = x->p->left;
            if (w->color == RED) {
                w->color = BLACK;
                x->p->color = RED;
                rightrotate(treeroot,x->p);
                w = x->p->left;
            }
            if (w->left->color == BLACK && w->right->color == BLACK) {
                w->color = RED;
                x = x->p;
            }
            else {
                if (w->left->color == BLACK) {
                    w->right->color = BLACK;
                    w->color = RED;
                    leftrotate(treeroot,w);
                    w = x->p->left;
                }
                w->color = x->p->color;
                x->p->color = BLACK;
                w->left->color = BLACK;
                rightrotate(treeroot,x->p);
                x = *treeroot;
            }
        }
    }
    x->color = BLACK;
}
 
void rbdelete(NODEPTR *treeroot, int z) {
    NODEPTR Z = search(*treeroot, z);
    if (Z == NILPTR) {
        printf("Node to be deleted not found\n");
        return;
    }
    NODEPTR y = Z;
    int yoc = y->color;
    NODEPTR x;
    if (Z->left == NILPTR) {
        x = Z->right;
        rbtransplant(treeroot,Z,Z->right);
    }
    else if (Z->right == NILPTR) {
        x = Z->left;
        rbtransplant(treeroot,Z,Z->left);
    }
    else {
        y = minimum(Z->right);
        yoc = y->color;
        x = y->right;
        if (y->p == Z)
            x->p = y;
        else {
            rbtransplant(treeroot,y,y->right);
            y->right = Z->right;
            y->right->p = y;
        }
        rbtransplant(treeroot,Z,y);
        y->left = Z->left;
        y->left->p = y;
        y->color = Z->color;
    }
    if (yoc == BLACK)
        rbdeletefixup(treeroot,x);
}
 
 
int Count( NODEPTR Tree )
{
    if( Tree == NILPTR)
        return 0;
    return std::max(Count( Tree->left ), Count( Tree->right )) + 1;
}
 
 
 
int main(int argc, const char * argv[])
{
    NIL.left = NIL.right = NIL.p = NILPTR;
    NIL.color = BLACK;
    NODEPTR tree = NILPTR;
    
    
    freopen("/Users/alexander/Xcode/tests/test3.txt","r",stdin);
    int buf;
    
    srand(time(NULL));
 
    
    int count = 1;
    long long int start;
    
 
    for (int i = 0; i < 25000000; i++) {
        scanf("%i", &buf);
        rbinsert(&tree, buf);
 
        if (!(i % count)) {
            if (count < 25000) {
                count *= 10;
            }
            //std::cout << i << "\n";
            start = rdtsc();
            rbdelete(&tree, buf);
            //search(tree, buf);
            //rbinsert(&tree, i);
            std::cout << rdtsc() - start << "\n";
            
            
        }
    }
    
    /*for (int i = 0; i < 100000; i++) {
        scanf("%i", &buf);
        rbinsert(&tree, buf);
        if (!(i % 1000)) {
            //std::cout << i << "\n";
            printf("%i\n", Count(tree));
 
        }
    }*/
 
    
    
    
    return 0;
}

//
//  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;
}