AVL-Trees COMP171 Fall 2005

AVL Trees / Slide 2 Balanced binary tree * The disadvantage of a binary search tree is that its height can be as large as N-1 * This means that the time needed to perform insertion and deletion and many other operations can be O(N) in the worst case * We want a tree with small height * A binary tree with N node has height at least (log N) * Thus, our goal is to keep the height of a binary search tree O(log N) * Such trees are called balanced binary search trees. Examples are AVL tree, red-black tree.

AVL Trees / Slide 3 AVL tree Height of a node * The height of a leaf is 1. The height of a null pointer is zero. * The height of an internal node is the maximum height of its children plus 1 Note that this definition of height is different from the one we defined previously (we defined the height of a leaf as zero previously).

AVL Trees / Slide 4 AVL tree * An AVL tree is a binary search tree in which n for every node in the tree, the height of the left and right subtrees differ by at most 1. AVL property violated here

AVL Trees / Slide 5 AVL tree * Let x be the root of an AVL tree of height h * Let N h denote the minimum number of nodes in an AVL tree of height h * Clearly, N i N i-1 by definition * We have * By repeated substitution, we obtain the general form * The boundary conditions are: N 1 =1 and N 2 =2. This implies that h = O(log N h ). * Thus, many operations (searching, insertion, deletion) on an AVL tree will take O(log N) time.

AVL Trees / Slide 6 Rotations * When the tree structure changes (e.g., insertion or deletion), we need to transform the tree to restore the AVL tree property. * This is done using single rotations or double rotations. x y A B C y x A B C Before Rotation After Rotation e.g. Single Rotation

AVL Trees / Slide 7 Rotations * Since an insertion/deletion involves adding/deleting a single node, this can only increase/decrease the height of some subtree by 1 * Thus, if the AVL tree property is violated at a node x, it means that the heights of left(x) ad right(x) differ by exactly 2. * Rotations will be applied to x to restore the AVL tree property.

AVL Trees / Slide 8 Insertion * First, insert the new key as a new leaf just as in ordinary binary search tree * Then trace the path from the new leaf towards the root. For each node x encountered, check if heights of left(x) and right(x) differ by at most 1. * If yes, proceed to parent(x). If not, restructure by doing either a single rotation or a double rotation [next slide]. * For insertion, once we perform a rotation at a node x, we wont need to perform any rotation at any ancestor of x.

AVL Trees / Slide 9 Insertion * Let x be the node at which left(x) and right(x) differ by more than 1 * Assume that the height of x is h+3 * There are 4 cases n Height of left(x) is h+2 (i.e. height of right(x) is h) Height of left(left(x)) is h+1 single rotate with left child Height of right(left(x)) is h+1 double rotate with left child n Height of right(x) is h+2 (i.e. height of left(x) is h) Height of right(right(x)) is h+1 single rotate with right child Height of left(right(x)) is h+1 double rotate with right child Note: Our test conditions for the 4 cases are different from the code shown in the textbook. These conditions allow a uniform treatment between insertion and deletion.

AVL Trees / Slide 10 Single rotation The new key is inserted in the subtree A. The AVL-property is violated at x l height of left(x) is h+2 l height of right(x) is h.

AVL Trees / Slide 11 Single rotation Single rotation takes O(1) time. Insertion takes O(log N) time. The new key is inserted in the subtree C. The AVL-property is violated at x.

AVL Trees / Slide Insert 0.8 AVL Tree x y A B C After rotation

AVL Trees / Slide 13 Double rotation The new key is inserted in the subtree B1 or B2. The AVL-property is violated at x. x-y-z forms a zig-zag shape also called left-right rotate

AVL Trees / Slide 14 Double rotation The new key is inserted in the subtree B1 or B2. The AVL-property is violated at x. also called right-left rotate

AVL Trees / Slide Insert 3.5 AVL Tree After Rotation x y Az B C 8

AVL Trees / Slide 16 An Extended Example Insert 3,2,1,4,5,6,7, 16,15,14 3 Fig Fig Fig Fig Fig Fig 6 Single rotation

AVL Trees / Slide Fig Fig Fig Fig Fig 11 Single rotation

AVL Trees / Slide Fig Fig Fig 14 Double rotation

AVL Trees / Slide Fig Fig 15 Double rotation

AVL Trees / Slide 20 Deletion * Delete a node x as in ordinary binary search tree. Note that the last node deleted is a leaf. * Then trace the path from the new leaf towards the root. * For each node x encountered, check if heights of left(x) and right(x) differ by at most 1. If yes, proceed to parent(x). If not, perform an appropriate rotation at x. There are 4 cases as in the case of insertion. * For deletion, after we perform a rotation at x, we may have to perform a rotation at some ancestor of x. Thus, we must continue to trace the path until we reach the root.

AVL Trees / Slide 21 Deletion * On closer examination: the single rotations for deletion can be divided into 4 cases (instead of 2 cases) n Two cases for rotate with left child n Two cases for rotate with right child

AVL Trees / Slide 22 Single rotations in deletion rotate with left child In both figures, a node is deleted in subtree C, causing the height to drop to h. The height of y is h+2. When the height of subtree A is h+1, the height of B can be h or h+1. Fortunately, the same single rotation can correct both cases.

AVL Trees / Slide 23 Single rotations in deletion rotate with right child In both figures, a node is deleted in subtree A, causing the height to drop to h. The height of y is h+2. When the height of subtree C is h+1, the height of B can be h or h+1. A single rotation can correct both cases.

AVL Trees / Slide 24 Rotations in deletion * There are 4 cases for single rotations, but we do not need to distinguish among them. * There are exactly two cases for double rotations (as in the case of insertion) * Therefore, we can reuse exactly the same procedure for insertion to determine which rotation to perform