AVL TreesBinary Tree IssueSlide 3Balanced TreeAVL TreeSlide 6AVL Tree NodeSlide 8Searching AVL TreesSearching an AVL TreeInserting in AVL TreeSlide 12Slide 13Re-Balancing a TreeSlide 15Case 1Slide 17Case 2Rotating a NodeRotate LeftSlide 21Slide 22Re-Balancing the TreeInserting a NodeAVL TreesCSCI 2720Fall 2005KraemerBinary Tree IssueOne major problem with the binary trees we have discussed thus far:they can become extremely unbalancedthis will lead to long search timesin the worst case scenario, inserts are done in orderthis leads to a linked list structurepossible O(n) performancethis is not likely but it’s performance will tend to be worse than O(log n)Binary Tree IssueBinaryTree tree = new BinaryTree();tree.insert(A);tree.insert(C);tree.insert(F);tree.insert(M);tree.insert(Z);rootACFMZBalanced TreeIn a perfectly balanced treeall leaves are at one leveleach non-leaf node has two childrenrootMCEJ OSWWorst case search time is log nAVL TreeAVL tree definitiona binary tree in which the maximum difference in the height of any node’s right and left sub-trees is 1 (called the balance factor)balance factor = height(right) – height(left)AVL trees are usually not perfectly balancedhowever, the biggest difference in any two branch lengths will be no more than one levelAVL Tree-100000-1001-21-100AVL TreeAVL Tree0 Not an AVL TreeAVL Tree NodeVery similar to regular binary tree nodemust add a balance factor fieldFor this discussion, we will consider the key field to also be the datathis will make things look slightly simplerthey will be confusing enough as it is AVL Tree Nodeclass TreeNode {public Comparable key;public TreeNode left;public TreeNode right;public int balFactor;public TreeNode(Comparable key) {this.key = key;left = right = null;balFactor = 0;}}Searching AVL TreesSearching an AVL tree is exactly the same as searching a regular binary treeall descendants to the right of a node are greater than the nodeall descendants to the left of a node are less than the nodeSearching an AVL TreeObject search(Comparable key, TreeNode subRoot) { I) if subRoot is null (empty tree or key not found)A) return nullII) compare subRoot’s key (Kr) to search key (Ks)A) if Kr < Ks -> recursively call search with right subTreeB) if Kr > Ks -> recursively call search with left subTree C) if Kr == Ks-> found it! return data in subRoot}Inserting in AVL TreeInsertion is similar to regular binary treekeep going left (or right) in the tree until a null child is reachedinsert a new node in this positionan inserted node is always a leaf to start withMajor difference from binary treemust check if any of the sub-trees in the tree have become too unbalancedsearch from inserted node to root looking for any node with a balance factor of ±2Inserting in AVL TreeA few points about tree insertsthe insert will be done recursivelythe insert call will return true if the height of the sub-tree has changedsince we are doing an insert, the height of the sub-tree can only increaseif inse rt() returns true, balance factor of current node needs to be adjustedbalance factor = height(right) – height(left)left sub-tree increases, balance factor decreases by 1right sub-tree increases, balance factor increases by 1if balance factor equals ±2 for any node, the sub-tree must be rebalancedInserting in AVL TreeM(-1)insert(V)E(1)J(0)P(0)M(0)E(1)J(0)P(1)V(0)M(-1)insert(L)E(1)J(0)P(0)M(-2)E(-2)J(1)P(0)L(0)This tree needs to be fixed!Re-Balancing a TreeTo check if a tree needs to be rebalancedstart at the parent of the inserted node and journey up the tree to the rootif a node’s balance factor becomes ±2 need to do a rotation in the sub-tree rooted at the nodeonce sub-tree has been re-balanced, guaranteed that the rest of the tree is balanced as wellcan just return false from the insert() method4 possible cases for re-balancingonly 2 of them need to be consideredother 2 are identical but in the opposite directionRe-Balancing a TreeCase 1a node, N, has a balance factor of 2this means it’s right sub-tree is too longinserted node was placed in the right sub-tree of N’s right child, NrightN’s right child have a balance factor of 1to balance this tree, need to replace N with it’s right child and make N the left child of NrightCase 1M(1)insert(Z)E(0)V(0)R(1)M(2)E(0)V(1)R(2)Z(0)rotate(R, V)M(1)E(0)Z(0)V(0)R(0)Re-Balancing a TreeCase 2a node, N, has a balance factor of 2this means it’s right sub-tree is too longinserted node was placed in the left sub-tree of N’s right child, NrightN’s right child have a balance factor of -1to balance this tree takes two stepsreplace Nright with its left child, Ngrandchildreplace N with it’s grandchild, NgrandchildCase 2M(1)insert(T)E(0)V(0)R(1)M(2)E(0)V(-1)R(2)rotate(V, T)T(0)M(2)E(0)T(1)R(2)V(0)rotate(T, R)M(1)E(0)V(0)T(0)R(0)Rotating a NodeIt can be seen from the previous examples that moving nodes really means rotating them aroundrotating lefta node, N, has its right child, Nright, replace itN becomes the left child of NrightNright’s left sub-tree becomes the right sub-tree of Nrotating righta node, N, has its left child, Nleft, replace itN becomes the right child of NleftNleft’s right sub-tree becomes the left sub-tree of NRotate LeftV(1)R(2)X(1)T(0)N(0)rotateLeft(R)X(1)V(0)Z(0)T(0)R(0)N(0)Z(0)Re-Balancing a TreeNotice that Case 1 can be handled by a single rotation leftor in the case of a -2 node, a single rotation rightCase 2 can be handled by a single rotation right and then leftor in the case of a -2 node, a rotation left and then rightRotate Leftvoid rotateLeft(TreeNode subRoot, TreeNode prev) {I) set tmp equal to subRoot.rightA) not necessary but makes things look nicerII) set prev equal to tmpA) caution: must consider rotating around rootIII) set subRoot’s right child to tmp’s left childIV) set tmp’s left child equal to subRootV) adjust balance factorsubRoot.balFactor -= (1 + max(tmp.balFactor, 0));tmp.balFactor -= (1 – min(subRoot.balFactor, 0)); }Re-Balancing the Treevoid balance(TreeNode subRoot, TreeNode prev) {I) if the right sub-tree is out of balance (subRoot.factor = 2)A) if subRoot’s right child’s balance factor is -1-> do a rotate right and then leftB) otherwise (if child’s balance factor is 1 or 0)-> do a rotate