1 00:00:00,130 --> 00:00:02,880 Hello everyone. 2 00:00:02,880 --> 00:00:12,600 This lecture for the data structure and algorithm is balanced binary search tree in 12th chapter advanced data structure. 3 00:00:12,600 --> 00:00:16,460 And we gonna learn about the conception and inserting of AVL tree. 4 00:00:16,460 --> 00:00:22,780 We often use binary search tree to index in memory. 5 00:00:22,780 --> 00:00:30,350 The building process of binary search tree is relate to the input data. 6 00:00:30,350 --> 00:00:42,170 We will get a balanced binary search tree of height log n if the input is random. 7 00:00:42,170 --> 00:00:53,560 But if the input is ordered. We might get a BST of single chain. 8 00:00:53,560 --> 00:01:05,470 So three scientists in Adelson come up with a balanced binary search tree called AVL tree. 9 00:01:05,470 --> 00:01:11,530 This tree can maintain height of log n. 10 00:01:11,530 --> 00:01:19,530 Before introduce AVL, let's review something about BST. 11 00:01:19,530 --> 00:01:26,350 The only thing we care about is that the in-order traversal is ordered. 12 00:01:26,350 --> 00:01:30,700 We don't need to know its exat constructure. 13 00:01:30,700 --> 00:01:35,300 They are equivalent about indexing. 14 00:01:35,300 --> 00:01:38,710 Let's take a look at these two trees. 15 00:01:39,190 --> 00:01:46,540 We can rotate the right tree to get the left tree, vice versa. 16 00:01:46,790 --> 00:01:54,220 These two tree are equivalent about indexing. 17 00:01:54,220 --> 00:02:00,230 Let's take a closer look. 18 00:02:04,750 --> 00:02:14,150 We can get the tree at the bottom. 19 00:02:14,150 --> 00:02:18,800 Use the mid node as a pivot. 20 00:02:18,800 --> 00:02:25,740 Rotate left then right or rotate right then left. 21 00:02:25,740 --> 00:02:35,740 These two kind of structure can be rotate to obtain a balanced structure. 22 00:02:35,740 --> 00:02:40,700 AVL tree is defined as 23 00:02:40,700 --> 00:02:42,650 first it could be empty. 24 00:02:42,650 --> 00:02:52,650 If not, we restrain that the difference of height between the left subtree and the right subtree is no more than 1. 25 00:02:52,650 --> 00:02:59,080 Any node of AVL tree must have this property. 26 00:02:59,080 --> 00:03:09,080 Once this property is guaranteed, the height of AVL tree will be log n. 27 00:03:09,080 --> 00:03:17,040 Now we give some special examples of AVL tree. 28 00:03:17,040 --> 00:03:21,450 We remove any node in this tree. 29 00:03:21,450 --> 00:03:25,580 That would cause the height to reduce by one. 30 00:03:25,580 --> 00:03:32,160 Then let's define balance factor of AVL tree : 31 00:03:32,160 --> 00:03:37,740 the height of right subtree minus the height of left subtree. 32 00:03:37,740 --> 00:03:45,240 So balance factor remains −1, 0, or +1. 33 00:03:45,240 --> 00:03:51,350 What about inserting of AVL tree. 34 00:03:51,350 --> 00:03:59,590 First we need to consider the property of BST. 35 00:03:59,590 --> 00:04:05,940 So we have to insert as binary search tree's way. 36 00:04:05,940 --> 00:04:12,470 First find the posistion of the node that need to be inserted. 37 00:04:12,470 --> 00:04:17,290 We don't need to insert if we find the node with the same keycode. 38 00:04:17,290 --> 00:04:23,860 But if it failed, it must be the failure position. 39 00:04:23,860 --> 00:04:30,560 Insert this node at that position. 40 00:04:30,560 --> 00:04:34,580 After inserting. 41 00:04:34,580 --> 00:04:38,400 Balance need to be considered. 42 00:04:42,490 --> 00:04:52,520 Especially the new node is inserted to the side which has more nodes before. 43 00:04:52,520 --> 00:04:58,890 That's the situation we need to adjust. 44 00:04:58,890 --> 00:05:03,480 We want the adjustment to be local not to spread to the all AVL tree. 45 00:05:03,480 --> 00:05:08,180 Look at this example. 46 00:05:08,180 --> 00:05:13,920 The node with value 17 is inserted in the left tree. 47 00:05:13,920 --> 00:05:21,170 After inserting, the balance factor of the node with value 12 become 2. 48 00:05:21,170 --> 00:05:25,040 Then local adjustment is needed. 49 00:05:25,040 --> 00:05:30,350 After adjusting, 50 00:05:30,350 --> 00:05:37,470 the height of new subtree, which has the same height before inserting node with value 17, is 2. 51 00:05:37,470 --> 00:05:40,480 So we consider to adjust locally. 52 00:05:42,310 --> 00:05:47,140 Let's reconsider. Insert node S. 53 00:05:47,140 --> 00:05:54,350 What are the nodes that need to be adjusted after inserting? 54 00:05:54,350 --> 00:06:00,320 Let's take a look at the nodes between node S and the root. 55 00:06:00,320 --> 00:06:11,930 The node , which close to S and its balance factor is not zero, 56 00:06:11,930 --> 00:06:15,570 is denoted by a. 57 00:06:15,570 --> 00:06:23,050 Then analyse the balance factor of node a. 58 00:06:23,050 --> 00:06:29,870 We suppose its balace factor is not zero before. 59 00:06:29,870 --> 00:06:34,120 So it might be +1 or -1. 60 00:06:34,120 --> 00:06:40,180 Balance factor equal to zero is a special consideration. 61 00:06:40,180 --> 00:06:50,180 That is the balance factor of ancestors of S is not zero. 62 00:06:50,180 --> 00:06:56,500 We regard node a as root in this situation. 63 00:06:56,500 --> 00:06:59,020 And the balance factor of root is also zero. 64 00:06:59,180 --> 00:07:04,230 The height of subtree of node a has changed. 65 00:07:04,230 --> 00:07:15,100 And the balance factors of the path from node a to node s have been adjusted. 66 00:07:15,100 --> 00:07:25,100 It will be -1 if node S is inserted to its left.1 if right. 67 00:07:25,100 --> 00:07:30,210 If the balance factor equal to -1 68 00:07:30,210 --> 00:07:36,970 The balance factor become zero if node S is inserted to right. 69 00:07:36,970 --> 00:07:45,040 The heights of its subtrees don't change.It won't influent other nodes in the tree. 70 00:07:45,040 --> 00:07:46,120 Then we don't have to adjust. 71 00:07:46,120 --> 00:07:50,940 If the balance factor of a is 1, so node s is inserted to the right 72 00:07:50,940 --> 00:07:55,770 It become to +2, then it need to be adjusted. 73 00:07:55,770 --> 00:08:01,620 How to adjust? It includes four situations. 74 00:08:01,620 --> 00:08:05,350 Actually it's two situations. 75 00:08:05,350 --> 00:08:15,590 The balance factor of a equaled to -1 before, that is left subtree has more nodes. 76 00:08:15,590 --> 00:08:19,340 Now new node s is inserted. 77 00:08:19,340 --> 00:08:24,020 If it is inserted to node a's left. 78 00:08:24,020 --> 00:08:26,770 What about node b? 79 00:08:26,770 --> 00:08:31,810 If it is inserted to the left of the left child, it is LL. 80 00:08:31,810 --> 00:08:36,220 If it's inserted to right of the child, it's LR. 81 00:08:36,220 --> 00:08:40,920 We can do some adjustment later. 82 00:08:40,920 --> 00:08:48,290 If the balance factor of node a is +1 before, that is the right has more nodes. 83 00:08:48,290 --> 00:08:57,780 It turns to +2 cause the new node is inserted to its right. 84 00:08:57,780 --> 00:09:04,360 There are two other situations that are similar to these. 85 00:09:04,360 --> 00:09:07,480 That is RR or RL. 86 00:09:07,480 --> 00:09:13,080 Let's take a look at LL and RR. 87 00:09:13,080 --> 00:09:20,540 We call it single rotation cause only two nodes need to be adjusted. 88 00:09:20,540 --> 00:09:28,020 We regard the child 'b' of node 'a' as new root of the subtree in these two situations. 89 00:09:28,020 --> 00:09:32,220 And regard 'a' as the child of node 'b'. 90 00:09:32,220 --> 00:09:34,870 Then adjustment is accomplished. 91 00:09:34,870 --> 00:09:40,610 Let's take a look at single rotation LL. 92 00:09:51,410 --> 00:10:02,320 Single rotation is needed now. Rotate 'b' to the new root, and use 'a' as its right child 93 00:10:02,320 --> 00:10:08,830 The balance factor of 'a' and 'b' become zero after adjustment. 94 00:10:08,830 --> 00:10:18,840 And the height of the subtree, whch is the same as the subtree a before inserting new node s, is h+2. 95 00:10:18,840 --> 00:10:25,730 So adjustment can be happened locally, it won't influent other nodes in AVL tree. 96 00:10:27,590 --> 00:10:33,170 Let's take a look at the adjustment. 97 00:10:33,170 --> 00:10:37,220 It becomes structure like this after inserting. 98 00:10:37,220 --> 00:10:44,150 We regard node b as the father of node a after adjustment. 99 00:10:44,150 --> 00:10:54,390 It has the property of in-order travesal both before and after adjustment. 100 00:10:54,390 --> 00:10:59,540 Before it's T0aT1cT2bT3 101 00:10:59,540 --> 00:11:06,050 The new structure is still ordered after adjustment. 102 00:11:06,050 --> 00:11:15,110 Here, a, b and c doesn't have the property of in-order traversal. 103 00:11:15,110 --> 00:11:23,040 We regard 'a' as a unbalanced node that need to be adjusted. 104 00:11:23,040 --> 00:11:28,150 'b' is a local node that need to be adjusted. 105 00:11:28,150 --> 00:11:36,170 And node c is an auxiliary grandson node. 106 00:11:36,170 --> 00:11:41,100 Let's take a look at a process of double rotation. 107 00:11:41,100 --> 00:11:48,280 For RL or Lr, these are three nodes that need to be adjusted. 108 00:11:48,280 --> 00:11:56,170 The adjustment of RL is similar to the adjustment of LR. 109 00:11:56,170 --> 00:12:01,260 About the rotation of RL 110 00:12:01,260 --> 00:12:08,280 The height of subtree a is h+2 before inserting. 111 00:12:08,280 --> 00:12:13,870 Cause it's inserting of RL 112 00:12:13,870 --> 00:12:23,430 The height of left or right subtree of c increased by one. 113 00:12:23,430 --> 00:12:30,860 Their heights are h-1 before. Now one subtree's height becomes h. 114 00:12:30,860 --> 00:12:40,060 There are two steps of adjustment. First rotate 'c' to the root of 'b'. 115 00:12:40,060 --> 00:12:48,330 Then rotate around 'a'. Rotate 'c' to a new root. 116 00:12:48,330 --> 00:12:51,180 'a' is its left child. 117 00:12:51,180 --> 00:12:57,820 The balance factor of subtree c must be zero after rotation. 118 00:12:57,820 --> 00:13:01,910 What's the balance factor of 'a' and 'b'? 119 00:13:01,910 --> 00:13:09,070 It's mainly about the new node whether it's in the subtree of T1 or T2. 120 00:13:09,070 --> 00:13:15,540 And after adjustment 121 00:13:15,540 --> 00:13:25,800 The height of the subtree, whose root is 'c', must be h+2. It's exactly same as the subtree a before inserting. 122 00:13:25,800 --> 00:13:30,030 So adjustment is done here. 123 00:13:30,030 --> 00:13:37,350 These nodes from the path from node c to the root don't need to be adjusted. 124 00:13:37,350 --> 00:13:47,080 During the inserting, inserting to subtree T1 or subtree T2. 125 00:13:47,080 --> 00:13:57,260 The balance factor of ancestors upon node s and node a is zero before. 126 00:13:57,260 --> 00:14:09,820 It becomes to +1 or -1 depending on that it's inserted to the left subtree or right subtree. 127 00:14:10,810 --> 00:14:14,390 Let's look at this example. 128 00:14:14,390 --> 00:14:22,040 After inserting 7 characters continuously we got the structure of LR. 129 00:14:22,040 --> 00:14:28,940 Structure like this is built after double rotation. 130 00:14:28,940 --> 00:14:34,820 Then insert hit and hi 131 00:14:34,820 --> 00:14:45,530 The structure, whose root is cop, needs to be adjusted. And it's adjustment of RL. 132 00:14:45,530 --> 00:14:56,960 After double rotation the new subtree has the same height as it inserting before. 133 00:14:56,960 --> 00:14:59,270 The adjustment is done. 134 00:14:59,270 --> 00:15:06,220 Insert his. 135 00:15:06,220 --> 00:15:14,930 The 'copy' root is unbalanced after inserting. 136 00:15:14,930 --> 00:15:19,360 So we need a RL single rotation. 137 00:15:19,360 --> 00:15:27,270 Finally rotate hi to the root of a subtree. 138 00:15:27,270 --> 00:15:31,490 Then insert hia. 139 00:15:31,490 --> 00:15:41,750 Here subtree of hit is unbalanced of LL. 140 00:15:41,750 --> 00:15:47,870 Single rotate 141 00:15:47,870 --> 00:15:57,000 Let's think about this. Can we change the definition of balance factor of AVL? 142 00:15:57,000 --> 00:16:02,970 Can we change the difference of height from 1 to 2? 143 00:16:02,970 --> 00:16:13,050 Second, if the input is 1, 2, 3 ... 2^k -1. 144 00:16:13,050 --> 00:16:28,690 Complete and full binary tree of height k is built if we use the adjustment of AVL tree. 145 00:16:28,690 --> 00:16:32,150 For instance, if the input is 1234567. 146 00:16:32,150 --> 00:16:41,790 We can prove the it's full and complete binary tree using mathematical induction. 147 00:16:41,790 --> 00:16:56,460 Mathematical induction 148 00:16:56,460 --> 00:17:06,460 Thank you.