- /**
- * 目的:实现AVL
- * 利用数组对左右儿子简化代码,但是对脑力难度反而增大不少,只适合acm模板
- * 其实avl在acm中基本不用,基本被treap取代
- * avl一般只要求理解思路,不要求写出代码,因为真心很烦
- */
- #include <iostream>
- #include <cstdio>
- #include <algorithm>
- #include <cstring>
- #include <string>
- #include <time.h>
- #include <queue>
- 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 << "***************" << endl;
- cout << "data: " << data << endl;
- }
- };
- //treap的节点
- template<class T>
- class AVLNode{
- private:
- int hgt; //节点的高度
- public:
- T data;
- int count;
- AVLNode<T> *son[2]; //0是左儿子,1是右儿子
- AVLNode<T>(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 << "c hgt: " << this->height() << endl;
- cout << "l hgt: " << this->son[0]->height() << endl;
- cout << "r hgt: " << this->son[1]->height() << endl;
- cout << "count: " << count << endl;
- cout << endl;
- }
- int height(){
- if(NULL == this)
- return 0;
- return _getHeight(this);
- }
- int _getHeight(AVLNode<T> * 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 T>
- class AVLTree{
- private:
- AVLNode<T> * root; //根节点
- int hgt; //树的高度
- int size; //树中不重复节点数量
- void _insert(AVLNode<T> *& cur, T data);
- void _mid_travel(AVLNode<T> *cur);
- //层次遍历
- void _cengci_travel(AVLNode<T> *cur);
- //单旋转(左左,右右), 左旋不是想左旋转的意思, 而是由于左子树的左儿子的高度太大
- //与treap的旋转命名相反
- void _singleRoate(AVLNode<T> *& cur, int dir);
- //双旋转(两次单旋转)
- void _doubleRoate(AVLNode<T> *& 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<class T>
- void AVLTree<T>::_insert(AVLNode<T> *& cur, T data){
- if(NULL == cur){
- cur = new AVLNode<T>(data);
- }else if(data == cur->data){
- cur->count++;
- }else{
- int dir = (data > cur->data);
- _insert(cur->son[dir], data);
- if(2 <= cur->son[dir]->height() - cur->son[!dir]->height()){
- bool lr = (data > cur->data);
- lr ? _singleRoate(cur, dir) : _doubleRoate(cur, dir);
- }
- }
- cur->setHeight();
- //cout << "set height: " << endl;
- //cur->show();
- }
- template<class T>
- void AVLTree<T>::_mid_travel(AVLNode<T> * cur){
- if(NULL != cur){
- //先查找做子树
- _mid_travel(cur->son[0]);
- //if(abs(cur->son[0]->height() - cur->son[1]->height()) >= 2)
- {
- cur->show();
- }
- _mid_travel(cur->son[1]);
- }
- }
- //层次遍历,
- //如果节点为空就输出0 来占位
- template<class T>
- void AVLTree<T>::_cengci_travel(AVLNode<T> * cur){
- if(NULL == cur)
- return;
- queue<AVLNode<T>*> q;
- q.push(cur);
- AVLNode<T> *top = NULL;
- queue<AVLNode<T>*> tmp;
- while(!q.empty()){
- while(!q.empty()){
- top = q.front();
- q.pop();
- if(NULL == top){
- //用#代表该节点是空,#的后代还是#
- cout << '#' << " ";
- tmp.push(top);
- }else{
- cout << top->data.data << " ";
- tmp.push(top->son[0]);
- tmp.push(top->son[1]);
- }
- }
- bool flag = false;
- while(!tmp.empty()){
- if(NULL != tmp.front())
- flag = true;
- q.push(tmp.front());
- tmp.pop();
- }
- cout << endl;
- if(!flag)
- break;
- }
- }
- //单旋转,即只旋转一次
- //dir = 0时,左左旋转;否则为右右旋转
- template<class T>
- void AVLTree<T>::_singleRoate(AVLNode<T> *& cur, int dir){
- AVLNode<T> *& k2 = cur, * k1 = k2->son[dir]; //k2 必须是引用
- k2->son[dir] = k1->son[!dir];
- k1->son[!dir] = k2;
- k2 = k1;
- k2->setHeight();
- k1->setHeight();
- }
- //双旋转,即调两次单旋转
- //dir = 0是左右情况; 否则为右左情况
- template<class T>
- void AVLTree<T>::_doubleRoate(AVLNode<T> *& cur, int dir){
- _singleRoate(cur->son[dir], !dir);
- _singleRoate(cur, dir);
- }
- /************* 公有方法(接口)开始**********************/
- template<class T>
- void AVLTree<T>::insert(const T & data){
- _insert(root, data);
- }
- template<class T>
- void AVLTree<T>::mid_travel(){
- _mid_travel(root);
- }
- int main(){
- AVLTree<DNode>* avlt = new AVLTree<DNode>();
- const int num = 30;
- for(int i = 0; i < num; i++){
- DNode * d = new DNode(i);
- avlt->insert(*d);
- }
- cout << "*************中序遍历***************" << endl;
- avlt->mid_travel();
- cout << "**************中序遍历结束**********" << endl;
- cout << "*************层次遍历开始***************" << endl;
- avlt->cengci_travel();
- cout << "**************层次遍历结束**********" << endl;
- cout << "树的高度是: " << avlt->height() << endl;
- return 0;
- }
- //该片段来自于http://www.codesnippet.cn/detail/3107201410068.html
来源: http://www.codesnippet.cn/detail/3107201410068.html