AVL Tree Files: avl.c, avl.h If n keys are inserted into a binary search tree in increasing order, then it takes O(n^2) time. This is because the tree becomes unbalanced, causing each insertion to take O(n) time rather than O(log n) time. In order to avoid this worst case time, the tree's balance needs to be maintained. One such balanced binary tree scheme is the AVL tree, invented by Adel'son-Velskii and Landis in 1962. An avl tree is a binary search tree which enforces the following condition at each node: - The length of the longest path to leaves in the left subtree and the length of the longest path to leaves in the right subtree differ by at most 1. An example AVL tree is illustrated below, with the longest left and right path lengths given beside each node. 2(24)3 / \ / \ / \ 1(21)0 1(41)2 / / \ / / \ / / \ 0(11)0 0(36)0 1(69)1 / \ / \ / \ 0(64)0 0(76)0 For an actual AVL tree implementation, instead of storing separate left and right path lengths for each node, it is more space efficient to store just the difference (or balance). Balance information for the same example tree shown above, is illustrated below: 1(24) / \ / \ / \ -1(21) 1(41) / / \ / / \ / / \ 0(11) 0(36) 0(69) / \ / \ / \ 0(64) 0(76) As items are inserted into an AVL tree, the condition of balancing may be violated; that is, the balance information for a node reaches 2 or -2. Let the markers L, E, R denote the situations at each node as follows. L - left subtree is higher. R - right subtree is higher. E - left an right subtree are equal in height. AVL tree operations are the same as for the binary tree, except that the balance of the tree needs to be maintained after inserting or deleting a node. After insertion, we trace the path back to the root of the tree, updating balance information for each node. The following possible changes occur during updates to balance information of a node, p, on the path up to the root node: - If the balance of p changes from 0 to -1 or 1, then the length of the longest path has increased by 1, and tracing proceeds to the parent of node p. - If the balance of p changes from -1 or 1 to 0, then there has been no change in the length of the longest path, and tracing towards the root stops. - If the balance of p changes from -1 to -2 or from 1 to 2, then a rotation case is selected according to the balance of the child of p, which was traced from. After performing rotation, tracing stops. Tracing stops after the root node has been reached. For insertion, there are two different rotation cases that may result. A typical situation of each rotation case is given below (other situations are similar). Case 1: -2(L) p 0(E) q / \ / \ / \ / \ / \ rotate / \ / \ --------> / \ -1(L) q \ / 0(E) p / \ \ / / \ / \ \ / / \ / \ \ / / \ / \ /\ /\ / \ /\ /\ / \ / \ /\ /\ / \ / \ / C \ / \ / \ / \ / \ / B \ /______\ / A \ / B \ / C \ / A \ /______\ /________\ /______\ /______\ /________\ inserted Notes: - This also applies for the situation where subtrees B and C are empty and subtree A consists of only the inserted node. - A symmetric situation has R instead of L for nodes p and q. Case 2: -2(L) p 0(E) r / \ / \ / \ / \ / \ / \ / \ rotate / \ 1(R) q \ --------> / \ / \ \ / \ / \ \ / \ / \ \ 0(E) q 1(R) p / \ \ / \ / \ / -1(L) r \ / \ / \ / / \ \ / \ / \ / / \ /\ / \ / \ /\ / \ / \ /\ /\ /\ /\ / \ /\ /\ / D \ / \ / \ / C\ / \ / A \ / \ / C\ /______\ / A \ / B \ /____\ / D \ /______\ / B \ /____\ /______\ /______\ /______\ /______\ inserted Notes: - This kind of rotation also applies: - if we have R for node r. (when subtree C is inserted into rather than subtree B.) - if we have E for node r. (when r was the node inserted and all subtrees are empty.) - A symmetric situation has R for node p and L for node q. For deleting a node, p, from an AVL tree, the node is first deleted using the same deletion process as for a binary search tree. Note if node p has two child subtrees, then the minimum node, m, in the right subtree of p will be used for replacing p (refer to the binary search tree description in the file bst.txt). For this case the position of the delete is treated as being at node m when maintaining the trees balance. After deletion, we trace the path back from the position of the delete towards the root of the tree, updating balance information for each node. The following possible changes occur during updates to balance information of a node, p, on the path up to the root node: - If the balance of p changes from 0 to -1 or 1, then there has been no change in the length of the longest path, and tracing towards the root stops. - If the balance of p changes from -1 or 1 to 0, then the length of the longest path has decreased by 1, and tracing proceeds to the parent of node p. - If the balance of p changes from -1 to -2 or from 1 to 2, then a rotation case is selected according to the balance of the child of p, which was traced from. After performing rotation, tracing continues at the parent of node p. Tracing stops after the root node has been reached. The rotation cases for deletion are almost identical to the insertion rotation cases. For delete there are two different rotation cases that may result. A typical situation of each rotation case is given below (other situations are similar). Case 1: -2(L) p 0(E) q / \ / \ / \ / \ / \ rotate / \ / \ --------> / \ -1(L) q \ / 0(E) p / \ \ / / \ / \ \ / / \ / \ \ / / \ / \ /\ /\ / \ /\ /\ / \ / \ /\ /\ / \ / \ / C \ / \ / \ / \ / \ / B \ /______\ / A \ / B \ / C \ / A \ /______\ deletion /________\ /______\ /______\ /________\ Notes: - This also applies for the situation where subtrees B and C are empty and subtree A consists of one node. - The similar situations for nodes (p,q) are: (L,L) (shown), (L,E), (R,R), and (R,E). Case 2: -2(L) p 0(E) r / \ / \ / \ / \ / \ / \ / \ rotate / \ 1(R) q \ --------> / \ / \ \ / \ / \ \ / \ / \ \ 0(E) q 1(R) p / \ \ / \ / \ / -1(L) r \ / \ / \ / / \ \ / \ / \ / / \ /\ / \ / \ /\ / \ / \ /\ /\ /\ /\ / \ /\ /\ / D \ / \ / \ / C\ / \ / A \ / \ / C\ /______\ / A \ / B \ /____\ / D \ /______\ / B \ /____\ deletion /______\ /______\ /______\ /______\ Notes: - The similar situations for nodes (p,q,r) are: (L,R,L) (shown), (L,R,E), (L,R,R), (R,L,L), (R,L,E), and (R,L,R). Refer to the source files avl.c and avl.h for details of an AVL tree implementation. This description serves as an introduction to understanding the rotation code in the source files.