本文共 4107 字，大约阅读时间需要 13 分钟。
/* * ===================================================================================== * * Filename: avl.cpp * * Description: AVL借鉴Mark Allen Weiss的《数据结构与算法分析C++描述》跟网上 * 一些大牛的模板写的，写的操作还比较简单，后续有机会会添加更强 * 大的功能的～ * * Version: 1.0 * Created: 2012年02月04日 21时41分02秒 * Revision: none * Compiler: gcc * * Author: SphinX (Whisper), * Organization: HFUT * * ===================================================================================== */#include#include #include using namespace std;struct AvlNode{ int element; AvlNode * left; AvlNode * right; int height; AvlNode(const int & _element, AvlNode * lt, AvlNode * rt, int h = 0) : element(_element), left(lt), right(rt), height(h) {}};int height(AvlNode * t){ return NULL == t ? -1 : t->height;}void rotateWithLeftChild(AvlNode * & k2){ AvlNode * k1 = k2->left; k2->left = k1->right; k1->right = k2; k2->height = max(height(k2->left), height(k2->right)) + 1; k1->height = max(height(k1->left), k2->height) + 1; k2 = k1; return ;}void rotateWithRightChild(AvlNode * & k2){ AvlNode * k1 = k2->right; k2->right = k1->left; k1->left = k2; k2->height = max(height(k2->left), height(k2->right)) + 1; k1->height = max(height(k1->right), k2->height) + 1; k2 = k1; return ;}void doubleWithLeftChild(AvlNode * & k){ rotateWithRightChild(k->left); rotateWithLeftChild(k); return ;}void doubleWithRightChild(AvlNode * & k){ rotateWithLeftChild(k->right); rotateWithRightChild(k); return ;}AvlNode * findMin(AvlNode * t){ if (NULL == t) { return NULL; } if (NULL == t->left) { return t; } return findMin(t->left);}AvlNode * findMax(AvlNode * t){ if (NULL == t) { return NULL; } if (NULL == t->right) { return t; } return findMax(t->right);}void insert(const int & x, AvlNode * & t){ if (NULL == t) { t = new AvlNode(x, NULL, NULL); } else if (x < t->element) { insert(x, t->left); if (height(t->left) - height(t->right) == 2) { if (x < t->left->element) { rotateWithLeftChild(t); } else { doubleWithLeftChild(t); } } } else if (x > t->element) { insert(x, t->right); if (height(t->right) - height(t->left) == 2) { if (t->right->element < x) { rotateWithRightChild(t); } else { doubleWithRightChild(t); } } } t->height = max(height(t->left), height(t->right)) + 1; return ;}void remove(const int & x, AvlNode * & t){ if (NULL == t) { return ; } if (x < t->element) { remove(x, t->left); if (height(t->right) - height(t->left) == 2) { AvlNode * rt = t->right; if (height(rt->right) > height(rt->left)) { rotateWithRightChild(t); } else { doubleWithRightChild(t); } } else { t->height = max(height(t->left), height(t->right)) + 1; } } else if (t->element < x) { remove(x, t->right); if (height(t->left) - height(t->right) == 2) { AvlNode * lt = t->left; if (height(lt->left) > height(lt->right)) { rotateWithLeftChild(t); } else { doubleWithLeftChild(t); } } else { t->height = max(height(t->left), height(t->right)) + 1; } } else { if (t->left != NULL && t->right != NULL) { if (height(t->right) > height(t->left)) { t->element = findMin(t->right)->element; remove(t->element, t->right); } else { t->element = findMax(t->left)->element; remove(t->element, t->left); } } else { AvlNode * oldNode = t; t = (NULL == t->left) ? t->right : t->left; delete oldNode; oldNode = NULL; } } return ;}bool empty(AvlNode * t){ return NULL == t;}void clear(AvlNode * & t){ while (!empty(t)) { remove(t->element, t); } return ;}int main(){ int n, m; AvlNode * root = NULL; while (cin >> n >> m) { for (int i = 0; i < n; ++i) { int data; cin >> data; insert(data, root); } while (m--) { int op, data; cin >> op; switch(op) { case 0: cout << findMin(root)->element << endl; break ; case 1: cout << findMax(root)->element << endl; break ; case 2: cin >> data; insert(data, root); break ; case 3: cin >> data; remove(data, root); break ; default: break; } } } return 0;}
转载地址：http://eibqb.baihongyu.com/