rbt.h

多功能的红黑树和压缩算法

// RBT.h: interface for the CRBT class.
//
//////////////////////////////////////////////////////////////////////

#if !defined(AFX_RBT_H__120B076B_EF2E_4BCF_8D66_E0E6C0A15F2C__INCLUDED_)
#define AFX_RBT_H__120B076B_EF2E_4BCF_8D66_E0E6C0A15F2C__INCLUDED_

#if _MSC_VER > 1000
#pragma once
#endif // _MSC_VER > 1000

typedef enum { BLACK, RED } NodeColor;

typedef enum {
    RBT_STATUS_OK,
    RBT_STATUS_MEM_EXHAUSTED,
    RBT_STATUS_DUPLICATE_KEY,
    RBT_STATUS_KEY_NOT_FOUND
} RbtStatus;

//##ModelId=444B25140030
typedef void *RbtIterator;
//##ModelId=444B2514003A
typedef void *RbtHandle;

typedef struct NodeTag {
    struct NodeTag *left;       // left child
    struct NodeTag *right;      // right child
    struct NodeTag *parent;     // parent
    NodeColor color;            // node color (BLACK, RED)
    void *key;                  // key used for searching
    void *val;                // user data
} NodeType;

//##ModelId=444B252100C4
typedef struct RbtTag {
    NodeType *root;   // root of red-black tree
    NodeType sentinel;
    int (*compare)(void *a, void *b);    // compare keys
} RbtType;


#ifdef MYKERNEL_EXPORTS
#define KERNEL_EXPORT __declspec(dllexport)
#else
#ifdef WIN_DLL
#define KERNEL_EXPORT __declspec(dllimport)
#else
#define KERNEL_EXPORT 
#endif
#endif

class KERNEL_EXPORT CRBT  
{
public:
	CRBT();
	virtual ~CRBT();
public:
 
	/// 函数名: rbtNew
	/// 编程  : 王明松 2008-10-15 9:02:16
	/// 返回  : bool 
	/// 参数  : int(*compare)(void *a, void *b)  比较方法 return 0   if a == b  return < 0 if a < b return > 0 if a > b
	/// 描述  : 生成一个新的红黑树
    bool rbtNew(int(*compare)(void *a, void *b));

	/// 函数名: rbtDelete
	/// 编程  : 王明松 2008-10-15 9:09:40
	/// 返回  : void 
	/// 描述  : 销毁红黑树,但不销毁数据，需要通过rbtBegin rbtEnd rbtNext  rbtKeyValue来取出数据然后delete ,最后再调用本方法
    void rbtDelete();

	/// 函数名: rbtInsert
	/// 编程  : 王明松 2008-10-15 9:21:27
	/// 返回  : RbtStatus 
	/// 参数  : void *key  查找索引
	/// 参数  : void *value 数据
	/// 描述  : 插入一个节点至红黑树
    RbtStatus rbtInsert(void *key, void *value);

    // returns key/value pair associated with iterator

	/// 函数名: rbtKeyValue
	/// 编程  : 王明松 2008-10-15 9:30:02
	/// 返回  : void 
	/// 参数  : RbtIterator i 节点
	/// 参数  : void **key 索引
	/// 参数  : void **value 数值
	/// 描述  : 取个节点的索引及数值
    void rbtKeyValue(RbtIterator i, void **key, void **value);



	/// 函数名: rbtFind
	/// 编程  : 王明松 2008-10-15 9:30:49
	/// 返回  : RbtIterator 
	/// 参数  : void *key 索引
	/// 描述  : 通过索引查找节点
    RbtIterator rbtFind(void *key);
	/// 函数名: rbtErase
	/// 编程  : 王明松 2008-10-15 9:23:17
	/// 返回  : RbtStatus 
	/// 参数  : RbtIterator i
	/// 描述  : 删除一个节点，通过iterator, this function does not free the key/value pointers
    RbtStatus rbtErase(RbtIterator i);
	
	/// 函数名: rbtNext
	/// 编程  : 王明松 2008-10-15 9:46:04
	/// 返回  : RbtIterator 
	/// 参数  : RbtIterator i
	/// 描述  : 下一个节点 return ++i
    RbtIterator rbtNext(RbtIterator i);
	
	

	/// 函数名: rbtPrev
	/// 编程  : 王明松 2008-10-15 9:46:13
	/// 返回  : RbtIterator 
	/// 参数  : RbtIterator it
	/// 描述  : 上一个节点  return --i
    RbtIterator rbtPrev(RbtIterator it);
	
	/// 函数名: rbtBegin
	/// 编程  : 王明松 2008-10-15 9:46:36
	/// 返回  : RbtIterator 
	/// 描述  : 第一个节点 return pointer to first node
    RbtIterator rbtBegin();
	
	/// 函数名: rbtEnd
	/// 编程  : 王明松 2008-10-15 9:47:01
	/// 返回  : RbtIterator 
	/// 描述  : 最后一个节点，固定为NULL return pointer to one past last node
    RbtIterator rbtEnd();

	char m_errMsg[256];

private:
	void insertFixup(NodeType *x);
	void rotateRight(NodeType *x);
	void deleteTree(NodeType *p);
	void rotateLeft(NodeType *x);
	void deleteFixup(NodeType *x);

	

	RbtHandle m_pTreeHandle;//红黑树指针
};

#endif // !defined(AFX_RBT_H__120B076B_EF2E_4BCF_8D66_E0E6C0A15F2C__INCLUDED_)