Balanced trees

Balanced trees ppt in DS

1. Active Learning Assignment Data Structures Prepared By:-Darji meet B (160120107025) Topic :- Balanced trees Gandhinagar Institute of Technology

2. What is Balanced Tree ?

3. A binary tree is balanced if for each node it holds that the number of inner nodes in the left subtree and the number of inner nodes in the right subtree differ by at most 1.

4. Example 7 8 5 12 6 11 4 9 13 10 T3 T1 T4 T2 X Y Z

5. (b) Z X Y T1 T2 T4 11 5 4 9 8 6 12 7 13 10 T3

6. BALANCED TREES ALGORITHM Procedure:- CREATE_LEAF(NAME,INFO,NEW) 1[Create a new leaf node and initialize] NEW NODE LPTR(NEW) RPTR(NEW) NULL BI(NEW) ‘B’ K(NEW) NAME DATA(NEW) INFO 2[Finished] Return

7. Function BALANCED_INSEAT(HEAD, NAME,INFO) 1.[Is this a first insertion?] If LPTR(HEAD)=HEAD then Call CREATE_LEAF(NAME,INFO,NEW) LPTR(HEAD) NEW Return(NEW) 2.[Initialize] LEVEL 0 DIRECTION(LEVEL) ‘L’ PATH[LEVEL] HEAD T LPTR(HAND) 3.[Compare until found or inserted] Repeat step 4 forever 4.[Compare and insert, if required] If NAME<K(T)

8. then If LPTR(T) NULL then LEVEL LEVEL+1 PATH[LEVEL] T DIRECTION[LEVEL] ‘L’ T LPTR(T) else Call CREATE_LEAF(NAME,INFO,NEW) LPTR(T) NEW LEVEL LEVEL +1 PATH[LEVEL] T DIRECTION[LEVEL] ‘L’ Exitloop else If NAME>K(T) then If RPTR(T) NULL then LEVEL LEVEL+1 PATH[LEVEL] T DIRECTION[LEVEL] ‘R’ T RPTR(T) Else call CREATE_LEAF(NAME,INFO,NEW) RPTR(T) NEW LEVEL LEVEL+1  

9. PATH[LEVEL] T DIRECTION[LEVEL] ‘R’ Exitloop else (A match; NAME=K(T)) write(‘ITEM ALREADY THERE’) Return(NULL) 5.[search for an unbalanced node] MARK 0 Repeat for l= LEVEL,LEVEL-1,….,1 P PATH[1] if Bl (P) B then MARK 1 Exitloop 6.[Adjust balance indicators] Report for l= MARK+1,MARK+2,….LEVEL lf NAME<K(PATH[L]) then Bl (PATH[l]) ‘L’ else Bl (PATH[l]) ‘R’  

10. 7.[Is there a critical node?] If MARK=0 then Return(NEW) D DIRECTION[MARK] X PATH[ MARk ] Y PATH[MARK+1] If Bl (X) D then (the node was heavy and now becomes balanced) Bl (X) ‘B’ Return(NEW) 8.[Rebalancing: case1] If Bl (Y)=D then (the node was heavy and now becomes balanced) If D=‘L’ then LPTR(X) RPTP(Y) RPTR(Y) X  

11. else RPTR(X) LPTR(Y) LPTR(Y) X Bl (X) Bl (Y) ‘B’ F PATH[MARK-1] If X=LPTR(F) then LPTR(F) Y else RPTR(F) Y Return(NEW) 9.[Rebalancing tree: case 2] (a) (Change structure links) If D=‘L’ then Z RPTR(Y) RPTR(Y) LPTR(Z) LPTR(Z) Y LPTR(X) RPTR(Z) RPTR(Z) X

12. else Z LPTR(Y) LPTR(Y) RPTR(Z) RPTR(Z) Y RPTR(X) LPTR(Z) LPTR(Z) X F PATH[MARK-1] If X = LPTR(F) then LPTR(F) Z else RPTR(F) X (b) (Chang balance indicators) If Bl (Z)=D then Bl (Y) Bl (Z) ‘ B’ If D =‘L’ then Bl (X) ‘R’ else Bl (X) ‘L’

13. else If Bl (Z)=B then Bl (X) Bl (Y) Bl (Z) B else Bl (X) Bl (Z) B Bl (Y) D Return(NEW)