2-3树的代码实现

//2-3树的介绍参考<<数据结构>>Ellis Horowitz等著，李建中等译P317

/*
 * By YaoJianming 2008/07/18
 * */
#include
#include
#include

struct element {
    int key;
    element() {
        key = INT_MAX;
    }
    bool operator > (element x) {
        return key > x.key ? true : false;
    }
    bool operator < (element x) {
        return key < x.key ? true : false;
    }
    bool operator == (element x) {
        return key == x.key ? true : false;
    }
}MAX;
struct two_three {
    element data_l, data_r;
    two_three *left_child;
    two_three *middle_child;
    two_three *right_child;
    bool has_order;
    two_three() {
        has_order = false;
    }
};

struct stack {
    two_three *data[1024];
    int top;
    stack() {
        top = -1;
    }
    void push(two_three*);
    two_three* pop();
};

void stack::push(two_three *p)
{
    if(top >= 1024) {
        printf("stack full\n");
        exit(1);
    }
    data[++top] = p;
}

two_three* stack::pop()
{
    if(top == -1) {
        printf("stack empty\n");
        exit(1);
    }
    return data[top--];
}

two_three *search23(two_three *t, element x)
{
    while(t) {
        if (x < t->data_l) {
            t = t->left_child;
        } else if (x > t->data_l && x < t->data_r) {
            t = t->middle_child;
        } else if (x > t->data_r) {
            t = t->right_child;
        } else {
            return t;
        }
    }
    return NULL;
}

void new_root(two_three *&left, element y, two_three *middle)
{
    two_three *p = new two_three;
    p->left_child = left;
    p->middle_child = middle;
    p->right_child = NULL;
    p->data_l = y;
    p->data_r = MAX;
    left = p;
}

two_three *find_node(two_three *t, element x, stack *&s)
{
    while(t) {
        s->push(t);
        if (x < t->data_l && t->left_child) {
            t = t->left_child;
        } else if (x > t->data_l && x < t->data_r && t->middle_child) {
            t = t->middle_child;
        } else if (x > t->data_r && t->right_child) {
            t = t->right_child;
        } else if (x == t->data_l || x == t->data_r) {
            return NULL;
        } else {
            return s->pop();
        }
    }
}

void put_in(two_three *p, element x, two_three *q)
{
    if(p->data_l < x) {
        p->data_r = x;
        p->right_child = q;
    } else {
        p->right_child = p->middle_child;
        p->middle_child = q;
        p->data_r = p->data_l;
        p->data_l = x;
    }
}

void split(two_three *p, element &x, two_three *&q)
{
    element min, max;
    if(x < p->data_l) {
        min = x;
        max = p->data_r;
        x = p->data_l;
    } else if (x > p->data_r) {
        min = p->data_l;
        max = x;
        x = p->data_r;
    } else {
        min = p->data_l;
        max = p->data_r;
    }

    two_three *n = new two_three;
    n->data_l = max;
    n->data_r = MAX;
    n->left_child = p->right_child;
    n->middle_child = q;
    n->right_child = NULL;

    p->data_l = min;
    p->data_r = MAX;
    p->right_child = NULL;

    q = n;
}

void insert(two_three *&t, element x)
{
    two_three *p, *q;
    if(!t) {
        new_root(t, x, NULL);
    } else {
        stack *s = new stack;
        p = find_node(t, x, s);
        if(!p) return;

        q = NULL;
        for(;;) {
            if(p->data_r.key == INT_MAX) { //2-node
                put_in(p, x, q);
                break;
            } else { //3-node
                split(p, x, q);
                if(p == t) {
                    new_root(t, x, q);
                    break;
                } else {
                    p = s->pop();
                }
            }
        }
    }
}

int del_leaf(two_three *&p, element x)
{
    if(x == p->data_l) {
        if(p->data_r.key != INT_MAX) {
            p->data_l = p->data_r;
            p->data_r.key = INT_MAX;
        } else {
            p->data_l.key = INT_MAX;
            return 1;
        }
    } else {
        p->data_r.key = INT_MAX;
    }
    return 0;
}

two_three *find_del_node(two_three *t, element x, stack *&s)
{
    two_three *temp;
    while(t) {
        s->push(t);
        if(x < t->data_l && t->left_child) {
            t = t->left_child;
        } else if(x > t->data_r && t->right_child) {
            t = t->right_child;
        } else if(x > t->data_l && x < t->data_r && t->middle_child) {
            t = t->middle_child;
        } else if(x == t->data_l || x == t->data_r) {
            if(!t->left_child) {
                return s->pop();
            } else {
                temp = t;
                if(x == t->data_l) {
                    t = t->middle_child;
                } else {
                    t = t->right_child;
                }
                s->push(t);
                while(t->left_child) {
                    t = t->left_child;
                    s->push(t);
                }
                element el = temp->data_l;
                temp->data_l = t->data_l;
                t->data_l = el;
                return s->pop();
            }
        } else {
            return NULL;
        }
    }
}

void rotate_left_child(two_three *p, two_three *r, two_three *q)
{
    p->data_l = r->data_l;
    r->data_l = q->data_l;
    q->data_l = q->data_r;
    q->data_r.key = INT_MAX;
    p->middle_child = q->left_child;
    q->left_child = q->middle_child;
    q->middle_child = q->right_child;
}

void rotate_middle_child(two_three *p, two_three *r, two_three *q)
{
    p->data_l = r->data_l;
    r->data_l = q->data_r;
    q->data_r.key = INT_MAX;
    p->middle_child =p->left_child;
    p->left_child = q->right_child;
}

void rotate_right_child(two_three *p, two_three *r, two_three *q)
{
    p->data_l = r->data_r;
    r->data_r = q->data_r;
    q->data_r.key = INT_MAX;
    p->middle_child = p->left_child;
    p->left_child = q->right_child;
}

int combine_left_child(two_three *p, two_three *r, two_three *q)
{
    p->data_l = r->data_l;
    p->data_r = q->data_l;
    p->middle_child = q->left_child;
    p->right_child = q->middle_child;
    if(r->data_r.key == INT_MAX) {
        r->data_l.key = INT_MAX;
        r->middle_child = NULL;
        return 1;
    } else {
        r->data_l = r->data_r;
        r->data_r.key = INT_MAX;
        r->middle_child = r->right_child;
    }
    return 0;
}

int combine_middle_child(two_three *p, two_three *r, two_three *q)
{
    q->data_r = r->data_l;
    q->right_child = p->left_child;
    if(r->data_r.key == INT_MAX) {
        r->data_l.key = INT_MAX;
        r->middle_child = NULL;
        return 1;
    } else {
        r->data_l = r->data_r;
        r->data_r.key = INT_MAX;
        r->middle_child = r->right_child;
    }
    return 0;
}

int combine_right_child(two_three *p, two_three *r, two_three *q)
{
    q->data_r = r->data_r;
    r->data_r.key = INT_MAX;
    q->right_child = p->left_child;
    r->right_child = NULL;
    return 0;
}

void del(two_three *&t, element x)
{
    two_three *p;
    if(!t->left_child) {
        int ret = del_leaf(t, x);
        if(ret == 1) t = NULL;
    } else {
        stack *s = new stack;
        p = find_del_node(t, x, s);
        if(!p) return;
        int ret = del_leaf(p, x);
        if(ret == 0) return;
        for(;;) {
            two_three *r = s->pop();
            if(p == r->left_child) {
                if(r->middle_child->data_r.key != INT_MAX) {
                    rotate_left_child(p, r, r->middle_child);
                    break;
                } else {
                    int ret = combine_left_child(p, r, r->middle_child);
                    if(ret == 0) break;
                    else {
                        if(r == t) {
                            t = p;
                            break;
                        }
                        else p = r;
                    }
                }
            } else if(p == r->middle_child) {
                if(r->left_child->data_r.key != INT_MAX) {
                    rotate_middle_child(p, r, r->left_child);
                    break;
                } else {
                    int ret = combine_middle_child(p, r, r->left_child);
                    if(ret == 0) break;
                    else {
                        if(r == t) {
                            t = p;
                            break;
                        }
                        else p = r;
                    }
                }
            } else if(p == r->right_child) {
                if(r->middle_child->data_r.key != INT_MAX) {
                    rotate_right_child(p, r, r->middle_child);
                    break;
                } else {
                    combine_right_child(p, r, r->middle_child);
                    break;
                }
            }
        }
    }
}

void inorder(two_three *root);
int main()
{
    two_three *root = NULL;
    for(int i=1; i<100; ++i) {
        element x;
        x.key = i;
        insert(root, x);
    }

    inorder(root);
    printf("\n");

    element x;
    x.key = 3;
    del(root, x);

    inorder(root);
    printf("\n");
}

void inorder(two_three *root)
{
    stack s;
    while(root != NULL || s.top != -1) {
        if(root != NULL) {
            s.push(root);
            root = root->left_child;
        } else {
            root = s.pop();
            if(root->data_r == MAX) { //2-node
                printf("%d ", root->data_l.key);
                root = root->middle_child;
            } else {
                if(!root->has_order) {
                    printf("%d ", root->data_l.key);
                    root->has_order = true;
                    s.push(root);
                    root = root->middle_child;
                } else {
                    printf("%d ", root->data_r.key);
                    root->has_order = false;
                    root = root->right_child;
                }
            }
        }
    }
}