testrb.cpp

红黑树数据结构的c实现

#include <stdio.h>

#include "rb_tree.h"

struct node_type: rb_tree_node<node_type> {
    typedef int key_type;
    static int Comp_key_node(key_type Key, cp_node_type Node) {return Key-Node->m_Key;}
    static int Comp_node_node(cp_node_type Node_1, cp_node_type Node_2) {return Node_1->m_Key-Node_2->m_Key;}
    void Set_key(key_type Key) {m_Key = Key;}
    key_type Get_key() const {return m_Key;}

    p_node_type Next;
private:
    key_type m_Key;
};

typedef rb_tree<node_type> tree;

void In_order_print_struct(tree::p_node_type Tree, int Level)
{
    if ( Tree ) {
        In_order_print_struct(node_type::Get_left(Tree), Level+1);
        for ( int i = 0; i < Level; ++i )
            printf("  ");
        printf("%d %c (%d)\n", Tree->Get_key(), node_type::Is_red_node(Tree)? 'R' : 'B', Level);
        In_order_print_struct(node_type::Get_right(Tree), Level+1);
    }
}

const int N = 10000;

node_type P[N];

int main()
{
    tree::p_node_type Tree = 0;
    node_type::p_node_type List = 0;

    for ( int i = 0; i < N; ++i ) {
        P[i].Set_key(i);
        P[i].Next = List;
        List = P+i;
        Tree = tree::Insert(Tree, P+i);
    }
    
    In_order_print_struct(Tree, 0);
    printf("\n");

    while ( List ) {
        Tree = tree::Delete(Tree, List);
        List = List->Next;
    }

    return 0;
}