rbtree.h

红黑树和二叉查找树数据结构的实现以及二者的性能比较的C语言实现代码

#ifndef RBTREE_H
#define RBTREE_H

typedef int rbKEY;
typedef struct rbTreeNode *rbTreeNode;
typedef struct rbTree *rbTree;
typedef enum NODECOLOR NODECOLOR;


typedef void (*rbProcess) (rbTreeNode);
typedef void (*rbVisit) (rbTreeNode,rbProcess);


rbTree RB_NewTree();
rbTree RB_Insert(rbTree T, rbKEY key);
rbTree RB_Insert_Fixup(rbTree T, rbTreeNode z);
rbTree RB_Delete(rbTree T, rbKEY key);
rbTree RB_Delete_Fixup(rbTree T, rbTreeNode x);
rbTreeNode RB_Search(rbTreeNode x, rbKEY key);
rbTreeNode RB_Search_Iterative(rbTreeNode x, rbKEY key);
rbTreeNode RB_SearchInTree(rbTree T, rbKEY key);
rbTreeNode RB_Search_IterativeInTree(rbTree T, rbKEY key);
rbTreeNode RB_Minimum(rbTreeNode x);
rbTreeNode RB_Maximum(rbTreeNode x);
rbTreeNode RB_Successor(rbTreeNode x);
rbTreeNode RB_Predecessor(rbTreeNode x);
void Left_Rotate(rbTree T, rbTreeNode x);
void Right_Rotate(rbTree T, rbTreeNode x);
void RB_Pre_Visit(rbTreeNode node,rbProcess process);
void RB_In_Visit(rbTreeNode T,rbProcess process);
void RB_Post_Visit(rbTreeNode T,rbProcess process);
void RB_Pre_Disply(rbTreeNode node, rbProcess process);
void RB_Free_Node(rbTreeNode node);
void RB_Print_Node(rbTreeNode node);
void RB_Displiy_Tree(rbTree T, rbVisit visit);
void RB_Delete_Tree(rbTree T, rbVisit visit);
int  Bh_Node(rbTreeNode node);
int  Bh_Tree(rbTree T);
int  RB_OS_Key_Rank(rbTreeNode node, rbKEY k);
int  OS_Key_Rank(rbTree T, rbKEY k);
rbTree RB_NewTree_Rand(int a[], int n);
void newRandArray(int a[], int nMinNum, int nCount); 


#endif