I-APG1, Lektion 7 Bent Bruun KristensenBalanced Binary Search TreesAVL TreeBalance FactorsHeightPowerPoint PresentationSlide 7AVL Search TreeSlide 9AVL Search Tree: Putput(9)put(29)Slide 13Slide 14AVL Rotations (put)LL (and RR) RotationLLSlide 18Slide 19Slide 20LR (and RL) RotationLRSlide 23Slide 24Slide 25Disclaimer …Slide 27AVL Search Tree: RemoveSlide 29Slide 30Node “q”AVL Rotations (remove)R0Slide 34R1Slide 36R-1Slide 38AVL RotationsI-APG1, Lektion 7Bent Bruun Kristensen Balanced Binary Search Trees•Ch. 16: – Oplæg: 16.1–Opgave: 1, 5Balanced Binary Search Trees •height is O(log n), where n is the number of elements in the tree•AVL (Adelson-Velsky and Landis) trees•red-black trees•get, put, and remove take O(log n) timeAVL Tree•binary tree•for every node x, define its balance factorbalance factor of x = height of left subtree of x - height of right subtree of x• balance factor of every node x is -1, 0, or 1Balance Factors0 00010-1 010-11-1This is an AVL tree.HeightThe height of an AVL tree that has n nodes is at most 1.44 log2 (n+2).The height of every n node binary tree is at least log2 (n+1).N5N6N1N0N3N2N4Minimal AVL trees:Nh = Nh-1 + Nh-2 + 1, N0 = 0, N1 = 1Fibonacci numbers:Fn = Fn-1 + Fn-2, F0 = 0, F1 = 1Nh = Fh+2 – 1 for h ≥ 0n nodes: h ≤ 1.44 log2(n+2) = O(log n)Minimal AVL Treesn 0 1 2 3 4 5 6 7 8 9 10 …Fn 0 1 1 2 3 5 8 13 21 34 55 …Nh 0 1 2 4 7 12 20 33 54 88 143 …AVL Search Tree0 00010-1 010-11-1107831530402025354560AVL Search Tree: Put0 00010-1 010-11-1107831530402025354560Put an element into a binary search tree and …put(9)0 00010-1 010-11-190-10107831530402025354560put(29)0 00010010-11-1107831530402025354560290-1-1-2RR imbalance => new node is in right subtree of right subtree of blue node (node with bf = -2)put(29)0 00010010-11-110783153040253545600RR rotation. 20029AVL Rotations (put)•RR•LL•RL•LRsymmetricsymmetricLL (and RR) RotationABBA0+1ALLB+1h h+2 AR BL BR+2hLLBA 0 h+2 BL AR BR 0hALLB+1h h+2 AR BL BR+2LL(rA): rB = rA.left; rA.left = rB.right; rB.right = rA; rA.height = max(rA.left.height, rA.right.height) + 1 rB.height = max(rB.left.height, rA.height) + 1 return rB;rArBhLR (and RL) RotationACBCABABCALRCh h+2 AR CL CR BLBhh-1 0 0+1-1-1+20 0+1ALRC+1h h+2 AR CL CR BLB-1+2hh-1CLRA-1 h+2 AR CL CR BLB 0 0hhh-1ALRC+1h h+2 AR CL CR BLB-1+2hLR(rA): rA.Left = RR(rA.left): rC = rB.right; rB.right = rC.left; rC.left = rB; rB.height = … rC.height = … return rC; LL(rA): rC = rA.left; rA.left = rC.right; rC.right = rA; rA.height = … rC.height = … return rC; rArCrBh-1private AvlNode insert( Comparable x, AvlNode t ) { if( t == null ) t = new AvlNode( x, null, null ); else if( x.compareTo( t.element ) < 0 ) { t.left = insert( x, t.left ); if( height( t.left ) - height( t.right ) == 2 ) if( x.compareTo( t.left.element ) < 0 ) t = rotateWithLeftChild( t ); else t = doubleWithLeftChild( t ); } else if( x.compareTo( t.element ) > 0 ) { t.right = insert( x, t.right ); if( height( t.right ) - height( t.left ) == 2 ) if( x.compareTo( t.right.element ) > 0 ) t = rotateWithRightChild( t ); else t = doubleWithRightChild( t ); } else ; // Duplicate; do nothing t.height = max( height( t.left ), height( t.right ) ) + 1; return t; } private static AvlNode rotateWithLeftChild( AvlNode k2 ) { AvlNode k1 = k2.left; k2.left = k1.right; k1.right = k2; k2.height = max( height( k2.left ), height( k2.right ) ) + 1; k1.height = max( height( k1.left ), k2.height ) + 1; return k1; } private static AvlNode doubleWithLeftChild( AvlNode k3 ) { k3.left = rotateWithRightChild( k3.left ); return rotateWithLeftChild( k3 ); } private static AvlNode rotateWithRightChild( AvlNode k1 ) { AvlNode k2 = k1.right; k1.right = k2.left; k2.left = k1; k1.height = max( height( k1.left ), height( k1.right ) ) + 1; k2.height = max( height( k2.right ), k1.height ) + 1; return k2; } private static AvlNode doubleWithRightChild( AvlNode k1 ) { k1.right = rotateWithLeftChild( k1.right ); return rotateWithRightChild( k1 ); }Disclaimer …AVL Search Tree: Remove0 00010-1 010-11-1107831530402025354560Remove an element from a binary search tree and …Remove Leaf Node:Remove Degree 1 Node:Remove Degree 2 Node:Remove:Degree 2 NodeRemove 2 degree node: • Replace red with green• Remove degree 1 nodeNode “q”“q” is the parent node of the node physically deleted.qqBalance factor of “q” as the result of a deletion:D1: -1 → 0 or 1 → 0: q tree is decreased by 1: Change ancestors …D2: 0 → 1 or 0 → -1: q tree is same sizes: Ancestors are unchanged …D3: 1 → 2 or -1 → -2: q tree is unbalanced: Change q …AVL Rotations (remove)•R0 symmetric with L0•R1 symmetric with L1•R-1 symmetric with L-1AR0B 0h-1 AR BL BR+1h+2h+2AR0Bh-1 AR BL BR+1h-1h+2AR1B +1 AR BL BR+1hh-1+2h-1 h+2AR1B AR BL BR 0hh-1h-1h+2 0h+1AR-1C b AR CL CR BLB-1+1h-1h-2+2h-1h+2AR-1C AR CL CR BLB b bh-1h-2h-1h+2 0h+1AVL RotationsAccording to Sahni:Put: Remove:LL R0 differ only in the final balance factorsLL R1 are identicalRR L0 differ only in the final balance factorsRR L1 are identicalLR R-1 are identicalRL L-1 are