btree.h

btree算法

//为了防止出现线性二叉树， 必须要注意二叉树的平衡

#ifndef __BTREE_H__ //__BTREE_H__
#define __BTREE_H__

template<typename T> struct node
{
	T data;
	int bf;    //balance flag
	node<T> *lnext,*rnext;
};

enum
{
	RH = -1,
	EH = 0,
	LH = 1
};

template<class T> class CBTree
{
private:
	void RotateLeft(node<T> **root);
	void RotateRight(node<T> **root);
	void LeftBalance(node<T> **root);
	void RightBalance(node<T> **root);

public:
	int InsertAVL(node<T> **p_root, T key,node<T> **p_keypos, bool &taller);
	int DeleteAVL(node<T> **p_root, T key,node<T> **p_keyparentpos, bool &lower);
	int SearchAVL(node<T> *p_root, T key,node<T> **p_keypos);
	CBTree();
	~CBTree();
};




#endif //__BTREE_H__