br-tree

br-tree.c

#include "br-tree.h"
#include <stdlib.h>

int cmp(KEY_TYPE a, KEY_TYPE b) {
    return a < b;
}

void init_tree(BR_Tree* tree) {
    tree->end = (Node)malloc(sizeof(struct _Node));
    tree->end->color = BLACK;
    tree->root = tree->end;
}

int insert_key(BR_Tree *tree, KEY_TYPE key) {
    Node e = (Node)malloc(sizeof(struct _Node));
    e->key = key;
    return insert_node(tree, e);
}

int delete_key(BR_Tree *tree, KEY_TYPE key) {
    Node temp = tree->root;
    int ret = 0;
    while(temp != tree->end) {
        if(temp->key == key) {
            delete_node(tree, temp);
            ret = 1;
            break;
        }
        if(cmp(key, temp->key)) {
            temp = temp->left;
        } else {
            temp = temp->right;
        }
    }
    return ret;
}

static void delete_node(BR_Tree *tree, Node e) {
    Node y = e;
    Node x;
    int temp_color = y->color;
    if(e->left == tree->end) {
        x = e->right;
        trans_parent(tree, e, x);
    } else if(e->right == tree->end) {
        x = e->left;
        trans_parent(tree, e, x);
    } else {
        y = tree_min(tree, e->right);
        temp_color = y->color;
        x = y->right;
        if(y->p == e) {
            x->p=y;
        }else{
            trans_parent(tree, y, y->right);
            y->right = e->right;
            y->right->p = y;
        }
        trans_parent(tree, e, y);
        y->left = e->left;
        y->left->p = y;
        y->color = e->color;
    }
    if(temp_color == BLACK) {
        fixup_delete_node(tree, x);
    }
}
static void fixup_delete_node(BR_Tree *tree, Node x) {
    while(x != tree->root && x->color == BLACK) {
        if(x == x->p->left) {
            Node w = x->p->right;
            if(w->color == RED) {
                w->color = BLACK;
                x->p->color = RED;
                left_rotate(tree, 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;
                    right_rotate(tree, w);
                    w = x->p->right;
                }
                w->color = x->p->color;
                x->p->color = BLACK;
                w->right->color = BLACK;
                left_rotate(tree, x->p);
                x = tree->root;
            }
        } else {
            Node w = x->p->left;
            if(w->color == RED) {
                w->color = BLACK;
                x->p->color=RED;
                right_rotate(tree,x->p);
                w=x->p->left;
            }
            if(w->right->color == BLACK && w->left->color==BLACK){
                w->color=RED;
                x=x->p;
            }else{
                if(w->left->color==BLACK){
                    w->right->color=BLACK;
                    w->color=RED;
                    left_rotate(tree,w);
                    w=x->p->left;
                }
                w->color=x->p->color;
                x->p->color=BLACK;
                w->left->color=BLACK;
                right_rotate(tree,x->p);
                x=tree->root;
            }
        }
    }
    x->color = BLACK;
}

static int insert_node(BR_Tree *tree, Node e) {
    Node temp = tree->root;
    Node y = tree->end;
    while(temp != tree->end) {
        y = temp;
        if(e->key == temp->key) {
            return 0;
        }
        if(cmp(e->key, temp->key)) {
            temp = temp->left;
        } else {
            temp = temp->right;
        }
    }
    e->p = y;
    e->left = e->right = tree->end;
    e->color = RED;
    if(y == tree->end) {
        tree->root = e;
    } else if(cmp(e->key, y->key)) {
        y->left = e;
    } else {
        y->right = e;
    }
    fixup_insert_node(tree, e);
    return 1;
}

static void fixup_insert_node(BR_Tree *tree, Node e) {
    while(e->p->color == RED) {
        if(e->p == e->p->p->left) {
            Node u = e->p->p->right;
            if(u->color == RED) {
                e->p->color = BLACK;
                u->color = BLACK;
                e->p->p->color = RED;
                e = e->p->p;
            } else {
                if(e->p->right == e) {
                    e = e->p;
                    left_rotate(tree, e);
                }
                e->p->color = BLACK;
                e->p->p->color = RED;
                right_rotate(tree, e->p->p);
            }
        } else {
            Node u = e->p->p->left;
            if(u->color == RED) {
                e->p->color = BLACK;
                u->color = BLACK;
                e->p->p->color = RED;
                e = e->p->p;
            } else {
                if(e->p->left == e) {
                    e = e->p;
                    right_rotate(tree, e);
                }
                e->p->color = BLACK;
                e->p->p->color = RED;
                left_rotate(tree, e->p->p);
            }
        }
    }
    tree->root->color = BLACK;
}



static void left_rotate(BR_Tree* tree, Node e) {
    Node y = e->right;
    // move child
    e->right = y->left;
    if(y->left != tree->end) {
        y->left->p = e;
    }
    // set parent
    y->p = e->p;
    if(e->p == tree->end) {
        tree->root = y;
    } else if(e->p->left == e) {
        e->p->left = y;
    } else {
        e->p->right = y;
    }
    // end
    e->p = y;
    y->left = e;
}

static void right_rotate(BR_Tree* tree, Node e) {
    Node y = e->left;
    // move child
    e->left = y->right;
    if(y->right != tree->end) {
        y->right->p = e;
    }
    // set parent
    y->p = e->p;
    if(e->p == tree->end) {
        tree->root = y;
    } else if(e->p->left == e) {
        e->p->left = y;
    } else {
        e->p->right = y;
    }
    // end
    e->p = y;
    y->right = e;
}

static void trans_parent(BR_Tree* tree, Node a, Node b) {
    if(a->p == tree->end) {
        tree->root = b;
    } else if(a->p->left == a) {
        a->p->left = b;
    } else {
        a->p->right = b;
    }
    b->p = a->p;
}

static Node tree_min(BR_Tree* tree, Node a) {
    while(a->left != tree->end) {
        a = a->left;
    }
    return a;
}

br-tree.h

#ifndef BR_TREE_H
#define BR_TREE_H
#define BLACK 1
#define RED 0
#define KEY_TYPE int

struct _Node{
    KEY_TYPE key;
    struct _Node* p;
    struct _Node* left;
    struct _Node* right;
    int color;
};

typedef struct _Node* Node;


struct BR_Tree{
    Node root;
    Node end;
};

typedef struct BR_Tree BR_Tree;


static void left_rotate(BR_Tree *,Node);
static void right_rotate(BR_Tree *,Node);
static void trans_parent(BR_Tree *,Node,Node);
int cmp(KEY_TYPE a,KEY_TYPE b);


static void fixup_insert_node(BR_Tree *,Node);
static void fixup_delete_node(BR_Tree *,Node);

static int insert_node(BR_Tree *,Node);
static void delete_node(BR_Tree *,Node);
static Node tree_min(BR_Tree*, Node);


void init_tree(BR_Tree*);
int insert_key(BR_Tree *,KEY_TYPE);
int delete_key(BR_Tree *tree,KEY_TYPE key);

#endif

main.c

#include <stdio.h>
#include "br-tree.h"

void print_tree(BR_Tree *tree,Node e){
    if(tree->root!=tree->end){
        if(e->left !=tree->end){
            print_tree(tree,e->left);
        }
        printf("Node %10p,key:%2d,left:%2d  right %2d  parent %2d color %d\n",e,e->key,e->left->key,
        e->right->key,e->p->key,e->color);
        if(e->right!=tree->end){
            print_tree(tree,e->right);
        }
    }
}

int main(){
    BR_Tree tree;
    init_tree(&tree);
    int array[]={12,1,9,2,0,11,7,19,4,15,18,5,14,13,10,16,6,3,8,17};
    for(int i=0;i<sizeof(array)/sizeof(int);i++){
        insert_key(&tree,array[i]);
    }
    print_tree(&tree,tree.root);
    for(int i=0;i<sizeof(array)/sizeof(int)/2;i++){
        delete_key(&tree,array[i]);
    }
    print_tree(&tree,tree.root);
}