算法笔记》9.5小节——数据结构专题(2)

数据结构专题(2)"/>

算法笔记》9.5小节——数据结构专题(2)

《算法笔记》9.5小节——数据结构专题(2)->平衡二叉树（AVL）

#include<cstdio>
#include<math.h>
#include<algorithm>
using namespace std;struct node {int data,height;node* lchild;node* rchild;
};
node* newNode(int v) {node* Node = new node;Node->data = v;Node->height = 1;Node->lchild = NULL;Node->rchild = NULL;return Node;
}
int getHeight(node* root) {if (root == NULL) return 0;else return root->height;
}
int getBalanceFactor(node* root) {return getHeight(root->lchild) - getHeight(root->rchild);
}
void updataHeight(node* root) {root->height = max(getHeight(root->lchild), getHeight(root->rchild)) + 1;
}
void R_rotate(node* &root) {node* temp = root->lchild;root->lchild = temp->rchild;temp->rchild = root;updataHeight(root);updataHeight(temp);root = temp;
}
void L_rotate(node* &root) {node* temp = root->rchild;root->rchild = temp->lchild;temp->lchild = root;updataHeight(root);updataHeight(temp);root = temp;
}
void insert(node*& root, int v) {if (root == NULL) {root = newNode(v);return;}if (v < root->data) {insert(root->lchild, v);updataHeight(root);if (getBalanceFactor(root) == 2) {if (getBalanceFactor(root->lchild) == 1) {R_rotate(root);}if (getBalanceFactor(root->lchild) == -1) {L_rotate(root->lchild);R_rotate(root);}}}else {insert(root->rchild, v);updataHeight(root);if (getBalanceFactor(root)==-2) {if (getBalanceFactor(root->rchild) == -1) {L_rotate(root);}if (getBalanceFactor(root->rchild) == 1) {R_rotate(root->rchild);L_rotate(root);}}}
}
int query(int v, node* root) {if (root == NULL) return 0;if (root->data == v) return 1;if (v < root->data) query(v, root->lchild);else query(v, root->rchild);
}
int main() {int n, m,t;while (scanf("%d %d", &n, &m) != EOF) {node* root=NULL;for (int i = 0; i < n; i++) {scanf("%d", &t);insert(root, t);}for (int i = 0; i < m; i++) {scanf("%d", &t);printf("%d\n",query(t, root));}}
}