Height balanced Tree

Types of Binary Trees and definitions of Height Balanced Tree

1. HEIGHT BALANCED TREE M.NIVETHITHA, DEPARTMENT OF INFORMATION TECHNOLOGY, V.V.VANNIAPERUMAL COLLEGE FOR WOMEN, VIRUDHUNAGAR.

2. BINARY TREE 2 a binary tree is  a tree data structure in which each node has at most two children , which are referred to as the left child and the right child. 

3. Types of binary trees 1. Height balanced tree 2.Binary search tree 3.Heap tree 4.Threaded binary tree 5.Expression tree 3

4. 1. He ight balanced tree

5. “ Height-balanced binary tree : is defined as  a binary tree in which the depth of the two sub trees of every node never differ by more than 1 .” 5

6. definition A binary search tree is said to be a height balanced binary search tree if all its nodes have a balance factor of 1,0 or -1. That is, |bf|=|h L – h R | ≤ 1 For every node in tree. 6

7. example 7

8. T he basic objectives of the height balanced tree 8 1.Searching 2.Insertion 3.deletion These operations may not be with the minimum time but the time involved is less than that of in an unbalanced binary search tree.

9. 9 How an unbalanced binary tree converted into a height balanced tree Suppose initially there is a height balanced tree

10. 10 The mechanism to balance an unbalance tree due to the insertion of a node into it. Steps : 1.Insert node into a binary search tree : insert the node into its proper position following the properties of binary tree 2.Compute the balance factors: on the path starting from the root node to the node newly inserted, compute the balance factors of each node. 3.Decide the pivot node : on the path as traced in step 2, determine whether the absolute value of any nodes balance factor is switched from 1 to 2.if so, the tree

11. 11 b ecomes unbalanced. It is called Pivot node. 4.Balance the unbalance tree : to manipulate pointers centred at the pivot node to bring the tree back into height balance. This pointer manipulation is known as AVL Rotation AVL ROTATIONS: An elegant method was devised in 1962 By two Russian mathematicians , G.M.Adelson-Velskii E.M.Landis

12. 12 There are four cases of rotations CASE 1 : LEFT TO LEFT INSERTION RIGHT SUB TREE OF LEFT CHILD OF PIVOT NODE BECOMES THE LEFT SUB TREE OF P. P BECOMES THE RIGHT CHILD OF A LEFT SUB TREE OF A REMAINS THE SAME A P P R A R A L A P A R A L P R

13. ALGORITHM 13 INPUT : Pointer Pptr to the pivot node OUTPUT : AVL rotations corresponding to the unbalance due to insertion in the left sub tree of the left child of Pptr STEPS : 1.Aptr = Pptr - > LCHILD 2.Pptr-> LCHILD = Aptr->RCHILD 3.Aptr->RCHILD=Pptr 4.Pptr->HEIGHT=Compute Height(Pptr) 5.Aptr->HEIGHT=Compute Height(Aptr) 6.Pptr=Aptr 7.Stop

14. CASE 2 : RIGHT TO RIGHT INSERTION 14 LEFT SUB TREE OF RIGHT CHILD OF PIVOT NODE BECOMES THE RIGHT SUB TREE OF P. P BECOMES THE LEFT CHILD OF A RIGHT SUB TREE OF A REMAINS THE SAME A P A R A L P L A P

15. ALGORITHM 15 INPUT : Pointer Pptr to the pivot node OUTPUT : AVL rotations corresponding to the unbalance due to insertion in the right sub tree of the right child of Pptr STEPS : 1.Aptr = Pptr - > RCHILD 2.Pptr-> RCHILD = Aptr->LCHILD 3.Aptr->LCHILD=Pptr 4.Pptr->HEIGHT=Compute Height(Pptr) 5.Aptr->HEIGHT=Compute Height(Aptr) 6.Pptr=Aptr 7.Stop

16. CASE 3 : LEFT TO RIGHT INSERTION 16 ROTATION 1 : LEFT SUB TREE OF THE RIGHT CHILD OF THE LEFT CHILD OF PIVOT NODE BECOMES THE RIGHT SUB TREE OF THE LEFT CHILD. LEFT CHILD OF THE PIVOT NODE BECOMES THE LEFT CHILD OF B ROTATION 2 : RIGHT SUBTREE OF THE RIGHT CHILD OF THE LEFT CHILD OF THE PIVOT NODE BECOMES THE LEFT SUBTREE OF P P BECOMES THE RIGHT CHILD OF B P P R A L A B B L B R B A A L B L P B R P R

17. ALGORITHM 17 INPUT : Pointer Pptr to the pivot node OUTPUT : AVL rotations corresponding to the unbalance due to insertion in the right sub tree of the left child of Pptr STEPS : 1.Aptr = Pptr - > LCHILD 2.RightToRightRotation(Aptr) 3.LeftToLeftRotation(Pptr) 4.Stop

18. CASE 4 : RIGHT TO LEFT INSERTION 18 ROTATION 1 : RIGHT SUB TREE OF THE LEFT CHILD OF THE RIGHTCHILD OF PIVOT NODE BECOMES THE LEFT SUB TREE OF A . RIGHT CHILD OF THE PIVOT NODE BECOMES THE RIGHT CHILD OF B. ROTATION 2 : LEFT SUBTREE OF THE RIGHT CHILD OF THE RIGHT CHILD OF THE PIVOT NODE BECOMES THE RIGHT SUBTREE OF P P BECOMES THE LEFT CHILD OF B P A A R P L B B L B R B P P L B L A B R A R

19. ALGORITHM 19 INPUT : Pointer Pptr to the pivot node OUTPUT : AVL rotations corresponding to the unbalance due to insertion in the left sub tree of the right child of Pptr STEPS : 1.Aptr = Pptr - > RCHILD 2. LeftToLeftRotation (Aptr) 3.RightToRightRotation(Pptr) 4.Stop

20. IMPLEMENTATION FOR HEIGHT BALANCING TREE LCHILD DATA HEIGHT RCHILD

21. ALGORITHM 21 INPUT : Pointer PTR to the tree whose height has to be calculated OUTPUT : Height of the tree DATA STRUCTURE : Linked Structure of Height STEPS : 1.If (PTR=NULL) then Height = 0 Return(height) 4.Else lptr =PTR->LCHILD Rptr =PTR->RCHILD Hl=Compute Height( lptr ) Hr =Compute Height( Rptr ) If(Hl <= H r ) then height = 1 + H r Else height = 1 + Hl Endif Return(height) Endif stop

22. 22