【洛谷 P3369】【模板】普通平衡树

目录题目解法一、AVL树题目解法一、AVL树#include stdio.h #include stdlib.h #include limits.h /**********************************************************************/ int max(int a, int b) { return a b ? a : b; } int min(int a, int b) { return a b ? a : b; } /**********************************************************************/ struct avl_node { int key; int height; int size; int cnt; struct avl_node *left; struct avl_node *right; }; struct avl_node *avl_alloc_node(int key) { struct avl_node *node malloc(sizeof(*node)); node-key key; node-height 1; node-size 1; node-cnt 1; node-left NULL; node-right NULL; return node; } int avl_height(struct avl_node *root) { if (!root) return 0; return root-height; } int avl_size(struct avl_node *root) { if (!root) return 0; return root-size; } int avl_cnt(struct avl_node *root) { if (!root) return 0; return root-cnt; } int avl_calc_height(struct avl_node *root) { return 1 max(avl_height(root-left), avl_height(root-right)); } int avl_calc_size(struct avl_node *root) { return avl_cnt(root) avl_size(root-left) avl_size(root-right); } void avl_update(struct avl_node *root) { root-size avl_calc_size(root); root-height avl_calc_height(root); } int avl_balance_factor(struct avl_node *root) { return avl_height(root-left) - avl_height(root-right); } struct avl_node *avl_left_rotation(struct avl_node *root) { struct avl_node *new_root root-right; root-right new_root-left; new_root-left root; avl_update(root); avl_update(new_root); return new_root; } struct avl_node *avl_right_rotation(struct avl_node *root) { struct avl_node *new_root root-left; root-left new_root-right; new_root-right root; avl_update(root); avl_update(new_root); return new_root; } struct avl_node *avl_balance(struct avl_node *root) { int bf avl_balance_factor(root); if (bf 1) { // LL if (avl_balance_factor(root-left) 0) return avl_right_rotation(root); // LR if (avl_balance_factor(root-left) 0) { root-left avl_left_rotation(root-left); return avl_right_rotation(root); } } if (bf -1) { // RR if (avl_balance_factor(root-right) 0) return avl_left_rotation(root); // RL if (avl_balance_factor(root-right) 0) { root-right avl_right_rotation(root-right); return avl_left_rotation(root); } } return root; } struct avl_node *avl_insert(struct avl_node *root, int key) { if (!root) return avl_alloc_node(key); if (key root-key) root-left avl_insert(root-left, key); else if (key root-key) root-right avl_insert(root-right, key); else root-cnt; avl_update(root); return avl_balance(root); } struct avl_node *avl_remove(struct avl_node *root, int key) { if (!root) return NULL; if (key root-key) { root-left avl_remove(root-left, key); } else if (key root-key) { root-right avl_remove(root-right, key); } else { if (avl_cnt(root) 1) { root-cnt--; } else { struct avl_node *tmp_node root; if (!root-left !root-right) { // 无左无右叶子 root NULL; free(tmp_node); } else if (root-left !root-right) { // 有左无右 root root-left; free(tmp_node); } else if (!root-left root-right) { // 有右无左 root root-right; free(tmp_node); } else { // 有左有右 tmp_node root-right; while (tmp_node-left) tmp_node tmp_node-left; root-key tmp_node-key; root-right avl_remove(root-right, tmp_node-key); } } } if (!root) return NULL; avl_update(root); return avl_balance(root); } int avl_count_less(struct avl_node *root, int x) { if (!root) return 0; if (x root-key) return avl_count_less(root-left, x); return avl_cnt(root) avl_size(root-left) avl_count_less(root-right, x); } int avl_get_rank(struct avl_node *root, int x) { return avl_count_less(root, x) 1; } int avl_get_kth(struct avl_node *root, int kth) { int left_size avl_size(root-left); int node_cnt avl_cnt(root); if (left_size kth) return avl_get_kth(root-left, kth); else if (left_size node_cnt kth) return avl_get_kth(root-right, kth - left_size - node_cnt); return root-key; } int avl_get_pre(struct avl_node *root, int x) { if (!root) return INT_MIN; if (x root-key) return avl_get_pre(root-left, x); return max(root-key, avl_get_pre(root-right, x)); } int avl_get_post(struct avl_node *root, int x) { if (!root) return INT_MAX; if (x root-key) return avl_get_post(root-right, x); return min(root-key, avl_get_post(root-left, x)); } /**********************************************************************/ struct opt_info { int opt; int x; }; void read_opt_num(int *num) { scanf(%d, num); } void read_opt_info(struct opt_info *opt_info) { scanf(%d %d, opt_info-opt, opt_info-x); } /**********************************************************************/ int main(void) { int opt_num; struct opt_info opt_info; struct avl_node *root NULL; int ans; read_opt_num(opt_num); for (int i 0; i opt_num; i) { read_opt_info(opt_info); switch (opt_info.opt) { case 1: root avl_insert(root, opt_info.x); break; case 2: root avl_remove(root, opt_info.x); break; case 3: ans avl_get_rank(root, opt_info.x); printf(%d\n, ans); break; case 4: ans avl_get_kth(root, opt_info.x); printf(%d\n, ans); break; case 5: ans avl_get_pre(root, opt_info.x); printf(%d\n, ans); break; case 6: ans avl_get_post(root, opt_info.x); printf(%d\n, ans); break; default: break; } } return 0; }