首页 > 代码库 > Poj Double Queue 3481 AVL解法
Poj Double Queue 3481 AVL解法
本题应该挺经典的,因为可以使用好多方法过,适合训练多种高级数据结构和算法。
这里使用AVL平衡二叉树的解法,时间还可以,大概300ms吧,内存很省188k,因为这里使用指针,没有浪费内存。
这里使用Geeks上面的AVL的做法,使用递归更新树,而不使用双亲指针,试了下使用双亲指针,真的好麻烦,要维护多一个指针,容易出错很多。
递归操作二叉树是非常优雅的。
而且不需要使用任何STL容器,非常原始,直接的解法,呵呵,可以控制任何一个细节,还是很好的。
#include <stdio.h> #include <algorithm> using std::max; class DoubleQueue3481_2 { struct Node { int key, num; Node *left, *right; int h; Node(int k, int n) : key(k), num(n), left(NULL), right(NULL), h(1) {} ~Node() { if (left) delete left; if (right) delete right; } }; void updateHeight(Node *n) { n->h = max(getHeight(n->left), getHeight(n->right)) + 1; } int getHeight(Node *n) { if (!n) return 0; return n->h; } Node *leftRotate(Node *y) { Node *x = y->right; y->right = x->left; x->left = y; updateHeight(y); updateHeight(x); return x; } Node *rightRotate(Node *y) { Node *x = y->left; y->left = x->right; x->right = y; updateHeight(y); updateHeight(x); return x; } int getBalance(Node *n) { if (!n) return 0; return getHeight(n->left) - getHeight(n->right); } Node *balanceNode(Node *n) { if (!n) return n; updateHeight(n); int balance = getBalance(n); if (balance > 1 && getBalance(n->left) >= 0) return rightRotate(n); if (balance < -1 && getBalance(n->right) <= 0) return leftRotate(n); if (balance > 1 && getBalance(n->left) < 0) { n->left = leftRotate(n->left); return rightRotate(n); } if (balance < -1 && getBalance(n->right) > 0) { n->right = rightRotate(n->right); return leftRotate(n); } return n; } Node *insert(Node *n, int key, int num) { if (!n) return new Node(key, num); if (key < n->key) n->left = insert(n->left, key, num); else n->right = insert(n->right, key, num); return balanceNode(n); } Node *minValueNode(Node *n) { if (!n) return n; Node *cur = n; while (cur->left) cur = cur->left; return cur; } Node *maxValueNode(Node *n) { if (!n) return n; Node *cur = n; while (cur->right) cur = cur->right; return cur; } Node *delNode(Node *r, int key) { if (!r) return r; if (key < r->key) r->left = delNode(r->left, key); else if (r->key < key) r->right = delNode(r->right, key); else { if (!r->left || !r->right) { Node *t = r->left? r->left : r->right; if (!t) { t = r; r = NULL; } else *r = *t;//copy content, be careful about the * delete t; t = NULL; } else { //key step: get inorder successor Node *t = minValueNode(r->right); r->key = t->key; r->right = delNode(r->right, t->key); } } return balanceNode(r); } void preOrder(Node *root) { if(root != NULL) { preOrder(root->left); printf("%d ", root->key); preOrder(root->right); } } public: DoubleQueue3481_2() { Node *root = NULL; int req = 0; while (scanf("%d", &req) != EOF) { if (0 == req) break; else if (1 == req) { int k, p; scanf("%d %d", &k, &p); root = insert(root, p, k); } else if (2 == req) { Node *maxNode = maxValueNode(root); if (!maxNode) printf("0\n"); else printf("%d\n", maxNode->num); //写少了个root = if (maxNode) root = delNode(root, maxNode->key); } else if (3 == req) { Node *minNode = minValueNode(root); if (!minNode) printf("0\n"); else printf("%d\n", minNode->num); if (minNode) root = delNode(root, minNode->key); } } if (root) delete root; } ~DoubleQueue3481_2() { } };
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。