AVL 平衡二叉树 AVL 平衡二叉树在 BST 的基础上要求左右两子树的高度差不超过 1
插入新的元素可能影响树的平衡性,为了使插入元素后的树继续满足 AVL 性质,要对树进行一些调整。
插入新的元素后,有四种情况,分别为 LL
, LR
,RR
,RL
调整的方法是对最小不满足AVL性质的子树进行旋转操作。
左旋和右旋
1 2 3 4 5 6 7 8 9 10 11 12 T1, T2 and T3 are subtrees of the tree rooted with y (on the left side ) or x (on the right side) y x / \ Right Rotation / \ x T3 - - - - - - - > T1 y / \ < - - - - - - - / \ T1 T2 Left Rotation T2 T3 Keys in both of the above trees follow the following order keys (T1) < key(x) < keys (T2) < key(y) < keys (T3) So BST property is not violated anywhere.
左旋和右旋操作后,子树仍然满足 BST 的性质,但是某些情况下可以降低子树的高度。
插入新的元素后,找到最小不满足 AVL 性质的子树,有以下四种情况(左侧)
主要关注 Z, Y, X
Left Left Case (LL)
1 2 3 4 5 6 7 8 T1, T2, T3 and T4 are subtrees. z y / \ / \ y T4 Right Rotate (z) x z / \ - - - - - - - - -> / \ / \ x T3 T1 T2 T3 T4 / \ T1 T2
具体例子
Left Right Case (LR)
1 2 3 4 5 6 7 z z x / \ / \ / \ y T4 Left Rotate (y) x T4 Right Rotate(z) y z / \ - - - - - - - - -> / \ - - - - - - - -> / \ / \ T1 x y T3 T1 T2 T3 T4 / \ / \ T2 T3 T1 T2
具体例子
Right Right Case (RR)
1 2 3 4 5 6 7 z y / \ / \ T1 y Left Rotate(z) z x / \ - - - - - - - -> / \ / \ T2 x T1 T2 T3 T4 / \ T3 T4
Right Left Case
1 2 3 4 5 6 7 z z x / \ / \ / \ T1 y Right Rotate (y) T1 x Left Rotate(z) z y / \ - - - - - - - - -> / \ - - - - - - - -> / \ / \ x T4 T2 y T1 T2 T3 T4 / \ / \ T2 T3 T3 T4
实现 leetcode 题
https://leetcode-cn.com/problems/balance-a-binary-search-tree/
非递归版本….xjb 手写能过 leetcode
插入过程:
遍历找插入位置 -> 插入 -> 更新高度 -> 发现左右子树高度差大于 2 -> 判断旋转类型 -> 旋转
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 void insert (int key) { printf ("%d\n" , key); AVLTreeNode * new_node = _alloca_node(); new_node->key = key; new_node->height = 1 ; if ( root == nullptr ) { root = new_node; return ; } AVLTreeNode * insert_node = root; while ( (key <= insert_node->key && insert_node->left) || (key > insert_node->key && insert_node->right) ) { insert_node = key<=insert_node->key?insert_node->left:insert_node->right; } new_node->parent = insert_node; if ( key <= insert_node->key ) insert_node->left = new_node; else insert_node->right = new_node; AVLTreeNode * travel = new_node->parent; AVLTreeNode * lastBugTree = nullptr ; int balance; while (travel) { int height_r, height_l; height_l = travel->left ? travel->left->height : 0 ; height_r = travel->right ? travel->right->height : 0 ; travel->height = max(height_l, height_r) + 1 ; balance = height_l - height_r; if (abs (balance) > 1 ) { lastBugTree = travel; break ; } travel = travel->parent; } AVLTreeNode * new_root; if (lastBugTree) { AVLTreeNode * lastBugParent; lastBugParent = lastBugTree->parent; if (balance > 1 && new_node->key < lastBugTree->left->key) { printf ("Type1\n" ); new_root = right_rotate(lastBugTree); }else if (balance > 1 && new_node->key > lastBugTree->left->key){ printf ("Type2\n" ); new_root = left_right_rotate(lastBugTree); }else if (balance < 0 && new_node->key > lastBugTree->right->key) { printf ("type3\n" ); new_root = left_rotate(lastBugTree); } else if (balance < 0 && new_node->key < lastBugTree->right->key) { printf ("Type4\n" ); new_root = right_left_rotate(lastBugTree); } if (!lastBugParent) { root = new_root; }else { if (lastBugParent->key > lastBugTree->key) lastBugParent->left = new_root; else lastBugParent->right = new_root; }; } }
旋转相关的代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 AVLTreeNode * right_rotate (AVLTreeNode * z) { AVLTreeNode * y = z->left; AVLTreeNode * x = y->left; y->parent = z->parent; z->left = y->right; if (z->left) z->left->parent = z; y->right = z; z->parent = y; z->height = get_height(z) + 1 ; y->height = get_height(y) + 1 ; return y; }AVLTreeNode * left_rotate (AVLTreeNode * z) { AVLTreeNode * y = z->right; AVLTreeNode * x = y->right; z->right = y->left; if (z->right) z->right->parent = z; y->parent = z->parent; z->parent = y; y->left = z; z->height = get_height(z) + 1 ; y->height = get_height(y) + 1 ; return y; }AVLTreeNode * left_right_rotate (AVLTreeNode * z) { AVLTreeNode * y = z->left; AVLTreeNode * x = y->right; z->left = left_rotate(y); return right_rotate(z); }AVLTreeNode * right_left_rotate (AVLTreeNode * z) { AVLTreeNode * y = z->right; AVLTreeNode * x = y->left; z->right = right_rotate(y); return left_rotate(z); }
参考 [1] AVL 数据可视化 https://www.cs.usfca.edu/~galles/visualization/AVLtree.html [2] AVL Tree | Set 1 (Insertion) https://www.geeksforgeeks.org/avl-tree-set-1-insertion/ [3] Data Structure and Algorithms - AVL Trees https://www.tutorialspoint.com/data_structures_algorithms/avl_tree_algorithm.htm
[4] leetcode 1382. 将二叉搜索树变平衡 https://leetcode-cn.com/problems/balance-a-binary-search-tree/