平衡二叉树AVL操作模板模板

平衡二叉树AVL操作模板

这篇文章主要介绍了平衡二叉树AVL操作模板,需要的朋友可以参考下 复制代码 代码如下: /**

* 目的：实现AVL

* 利用数组对左右儿子简化代码，但是对脑力难度反而增大不少，只适合acm模板 * 其实avl在acm中基本不用，基本被treap取代

* avl一般只要求理解思路，不要求写出代码，因为真心很烦 */

#include #include #include #include #include #include #include using namespace std;

int COUNT; //统计树中不重复节点的个数 int HEIGHT; //统计数的高度

//数据节点 class DNode {

public: int data;

DNode():data(0){}; DNode(int d):data(d){}

bool operator = (const DNode &d){ return data = d.data; }

bool operator == (const DNode &d){ return data == d.data; }

bool operator > (const DNode &d){ return data > d.data; }

bool operator < (const DNode &d){ return data < d.data;

}

void show(){ cout << endl;

cout << \ cout << \ } };

//treap的节点 template class AVLNode{ private:

int hgt; //节点的高度 public: T data; int count;

AVLNode *son[2]; //0是左儿子，1是右儿子 AVLNode(T data):data(data), count(1){ son[0] = son[1] = NULL; hgt = 1; }

int max(int a, int b){return a > b ? a : b;} void show(){ data.show();

cout << \

cout << \ cout << \ cout << \ cout << endl; }

int height(){ if(NULL == this) return 0;

return _getHeight(this); }

int _getHeight(AVLNode * cur){ if(NULL == cur) return 0;

return 1 + max(_getHeight(cur->son[0]), _getHeight(cur->son[1])); }

void setHeight(){

hgt = _getHeight(this); }

};

//AVL Tree

//这里的T是节点中的数据类型 template class AVLTree{ private:

AVLNode * root; //根节点 int hgt; //树的高度

int size; //树中不重复节点数量

void _insert(AVLNode *& cur, T data); void _mid_travel(AVLNode *cur); //层次遍历

void _cengci_travel(AVLNode *cur);

//单旋转（左左，右右）, 左旋不是想左旋转的意思， 而是由于左子树的左儿子的高度太大

//与treap的旋转命名相反

void _singleRoate(AVLNode *& cur, int dir); //双旋转（两次单旋转）

void _doubleRoate(AVLNode *& cur, int dir); int max(int a, int b){ return a > b ? a : b; } public:

AVLTree():root(NULL), hgt(0){} void insert(const T & data); void mid_travel(); int height(){

return root->height(); }

//层次遍历

void cengci_travel(){ _cengci_travel(root); }; };

/************* 私有方法开始**********************/ template

void AVLTree::_insert(AVLNode *& cur, T data){ if(NULL == cur){

cur = new AVLNode(data); }else if(data == cur->data){ cur->count++;