Balanced Tree (AVL Tree & Red-Black Tree)

This presentation is based on Algorithm.

1. Balanced Tree AVL Tree & RED - BLACK Tree By Samrin Ahmed Riya ID : 011142021 Sanzida Akter ID : 011142032

2. Balanced Tree Node based binary search tree Automatically balance it’s height in the face of arbitrary item insertions and deletions Fig : Balanced Tree

3. AVL Tree

4. AVL Tree A special kind of binary search tree Self balancing tree H eight of right sub tree ˞ ˞ height of left sub tree ≤ 1 Features : Georgy A delson - V elsky and Evgenii L andis' tree N amed after the inventors (1962)

5. Examples

6. AVL Tree or not YES Each left sub-tree has height 1 greater than each right sub-tree NO Left sub-tree has height 3, but right sub-tree has height 1

7. Operations Insertion Deletion Traversal Searching

8. Rotation for Balancing

9. It is performed as in binary search trees. For insertions, one rotation is sufficient. Sometimes it needs two rotations. Insertion

10. Insertion (0,0) 1 Insert 1 Elements : 1 2 3 6 15 -2 -5 -8

11. Insertion (0,0) 2 (0,1) 1 Insert 2 Elements : 1 2 3 6 15 -2 -5 -8

12. Insertion Rotation needed  (0,0) 3 (0,1) 2 (0, 2 ) 1 Insert 3 Elements : 1 2 3 6 15 -2 -5 -8

13. 1 (0,0) 3 (1,1) 2 Insert 3 (0,0) Insertion Elements : 1 2 3 6 15 -2 -5 -8

14. 1 (0,1) 3 (1,2) 2 Insert 6 (0,0) (0,0) 6 Insertion Elements : 1 2 3 6 15 -2 -5 -8

15. 1 (0, 2 ) 3 (1, 3 ) 2 Insert 15 (0,0) (0,1) 6 (0,0) 15 Rotation needed  Insertion Elements : 1 2 3 6 15 -2 -5 -8

16. 1 (1,1) 6 (1,2) 2 Insert 15 (0,0) (0,0) 15 3 (0,0) Insertion Elements : 1 2 3 6 15 -2 -5 -8

17. 1 (1,1) 6 ( 2 ,2) 2 Insert -2 ( 1 ,0) (0,0) 15 3 (0,0) -2 (1,0) Insertion Elements : 1 2 3 6 15 -2 -5 -8

18. 1 (1,1) 6 ( 3 ,2) 2 Insert -5 ( 2 ,0) (0,0) 15 3 (0,0) -2 (1,0) -5 (0,0) Rotation needed  Insertion Elements : 1 2 3 6 15 -2 -5 -8

19. -2 (1,1) 6 (2,2) 2 Insert -5 (1,1) (0,0) 1 3 (0,0) -5 (0,0) (0,0) (0,0) 15 Insertion Elements : 1 2 3 6 15 -2 -5 -8

20. -2 (1,1) 6 (3,2) 2 Insert -8 (2,1) (0,0) 1 3 (0,0) -5 (1,0) (0,0) (0,0) 15 -8 (0,0) Insertion Elements : 1 2 3 6 15 -2 -5 -8

21. Deletion Deletion can make the tree unbalanced One rotation is needed for rebalancing Sometimes it needs two rotations

22. Insertion & Deletion (Algorithms) LeftRotationAVL (x: BinTree) { x := ( x. rightChild .key , ( x.key , x. leftChild , x. rightChild . leftChild ) , x . rightChild . rightChild ); } RightRotation (x: BinTree) { x := ( x. leftChild .key , x . leftChild . leftChild , ( x.key , x. leftChild . rightChild , x. rightChild ) ); }

23. Insertion & Deletion (Algorithms) RightLeftRotation (x: BinTree) { x := ( x. rightChild . leftChild .key , ( x.key , x. leftChild , x. rightChild . leftChild . leftChild ) , ( x. rightChild .key , x. rightChild . leftChild . rightChild , x. rightChild . rightChild ) ); } LeftRightRotation(x : BinTree) { x := ( x. leftChild . rightChild .key , ( x. leftChild .key , x. leftChild . leftChild , x . leftChild . rightChild . leftChild ) , ( x.key , x. leftChild . rightChild . rightChild , x. rightChild ) ); }

24. Traversal Maintains preorder, inorder and postorder traversal Depends on the height of the tree

25. Traversal (Algorithms) Preorder Traversal void preorder(node *t) { if (t != NULL) { printf (“%d ”, t->element ); preorder(t- >leftChild); preorder(t- >rightChild); } }

26. Traversal (Algorithms) Inorder Traversal void inorder(node *t) { if (t != NULL) { inorder(t- >leftChild); printf (“%d ”, t->element); inorder(t- >rightChild); } }

27. Traversal (Algorithms) Postorder Traversal void postorder(node *t) { if (t != NULL) { postorder(t- >leftChild); /* L */ postorder(t- >rightChild); /* R */ printf (“%d ”, t->element); /* V */ } }

28. Searching Similar to normal unbalanced binary search tree. Successful searches are limited by the height  of the tree. Unsuccessful searching time is very close to  the height of the tree.

29. AVL Tree

30. Applications of AVL Tree Used in many search applications where data is constantly entering/leaving. To security concerns and to parallel code. Creating new types of data structures .

31. Red-Black Tree

32. A balancing binary search tree. A data structure requires an extra one bit color field in each node which is red or black. Leonidas J. Guibas  and Robert Sedgewick  derived the red-black tree from the symmetric binary B-tree . Introduction

33. Example of Red-Black Tree

34. The root and leaves (NIL’s) are black. A RED parent never has a RED child. in other words: there are never two successive RED nodes in a path Every path from the root to an empty subtree contains the same number of BLACK nodes called the black height We can use black height to measure the balance of a red-black tree. Properties of Red-Black Tree

35. Average Space O(n ) Search O( log 2  n) Traversal O(n ) Insertion O( log 2  n) Deletion O( log 2  n) Red-black tree Operations

36. Basic operation for changing tree structure is called rotation : Red-Black Trees: Rotation

37. x y y x x keeps its left child y keeps its right child x ’s right child becomes y ’s left child x ’s and y ’s parents change A B C A B C Red-Black Trees: Rotation

38. Rotation Example Rotate left about 9: 12 5 9 7 8 11

39. Rotation Example Rotate left about 9: 5 12 7 9 11 8

40. LEFT-ROTATE(T, x) y ← x->right x->right← y->left y->left->p ← x y->p ← x->p if x->p = Null then T->root ← y else if x = x->p->left then x->p->left ← y else x->p->right ← y y->left ← x x->p ← y RIGHT-ROTATE(T, x) y ← x->left x->left← y->right y->right->p ← x y->p ← x->p if x->p = Null then T->root ← y else if x = x->p->right then x->p->right ← y else x->p->left ← y y->right ← x x->p ← y Runtime : O(1) for Both. Rotation Algorithm

41. Red-Black Trees: Insertion Insertion: the basic idea Insert x into tree, color x red Only r-b property 3 might be violated (if p[ x ] red) If so, move violation up tree until a place is found where it can be fixed Total time will be O(log n )

42. Red-Black Insertion: Case 1 B   x Case 1: “uncle” is red In figures below, all ’s are equal-black-height subtrees C A D    C A D   y new x Same action whether x is a left or a right child B   x  case 1

43. Red-Black Insertion: Case 2 B   x Case 2: “Uncle” is black Node x is a right child Transform to case 3 via a left-rotation C A  C B y A   x  case 2  y  Transform case 2 into case 3 (x is left child) with a left rotation This preserves property 4: all downward paths contain same number of black nodes

44. Red-Black Insertion: Case 3 Case 3: “Uncle” is black Node x is a left child Change colors; rotate right B A x  case 3 C B A   x  y  C    Perform some color changes and do a right rotation Again, preserves property 4: all downward paths contain same number of black nodes

45. Red-Black Insert: Cases 4-6 Cases 1-3 hold if x ’s parent is a left child If x ’s parent is a right child, cases 4-6 are symmetric (swap left for right)

46. Insertion Example Insert 65 47 71 32 93

47. Insertion Example Insert 65 47 71 32 65 93

48. Insert 65 47 71 32 65 93 Insert 82 Insertion Example

49. 82 Insert 65 47 71 32 65 93 Insert 82 Insertion Example

50. 82 Insert 65 47 71 32 65 93 Insert 82 65 71 93 change nodes’ colors Insertion Example

51. 93 65 71 82 Insert 65 47 32 Insert 82 Insert 87 87 Insertion Example

52. 93 65 71 82 Insert 65 47 32 Insert 82 Insert 87 87 Insertion Example

53. 93 65 71 87 Insert 65 47 32 Insert 82 Insert 87 82 Insertion Example

54. 93 65 87 Insert 65 47 32 Insert 82 Insert 87 82 71 87 93 change nodes’ colors Insertion Example

55. 87 93 65 Insert 65 47 32 Insert 82 Insert 87 82 71 Insertion Example

56. TreeNode <T> rbInsert ( TreeNode <T> root,TreeNode <T> x )// returns a new root{ root= bstInsert ( root,x ); // a modification of BST insertItem x.setColor (red); while (x != root and x.getParent (). getColor () == red) { if ( x.getParent () == x.getParent (). getParent (). getLeft ()) { //parent is left child y = x.getParent (). getParent (). getRight () //uncle of x if ( y.getColor () == red) {// uncle is red x.getParent (). setColor (black); y.setColor (black); x.getParent (). getParent (). setColor (red); x = x.getParent (). getParent (); } else { // uncle is black if (x == x.getParent (). getRight ()) { x = x.getParent (); root = left_rotate ( root,x ); } x.getParent (). setColor (black); x.getParent (). getParent (). setColor (red); root = right_rotate ( root,x.getParent (). getParent ()); }} } else // ... symmetric to if } // end while root.setColor (black); return root; } Insertion Algorithm

57. Red-Black Tree Deletion If n has no children, we only have to remove n from the tree. If n has a single child, we remove n and connect its parent to its child. If n has two children, we need to : Find the smallest node that is larger than n, call it m. Remove m from the tree  and Replace the value of n with m. T hen restores the red-black tree properties.

58. Red-Black Tree Deletion Algorithm TreeNode <T> rbDelete ( TreeNode <T> root,TreeNode <T> z) //return new root, z contains item to be deleted { TreeNode <T> x,y ; // find node y, which is going to be removed if ( z.getLeft () == null || z.getRight () == null ) y = z; else { y = successor(z); // or predecessor z.setItem ( y.getItem ); // move data from y to z } // find child x of y if ( y.getRight () != null ) x = y.getRight (); else x = y.getLeft (); // Note x might be null; create a pretend node if (x == null ) { x = new TreeNode <T>( null ); x.setColor (black); }

59. Red-black tree Searching : Searching a node from a red-black tree doesn’t require more than the use of the BST procedure, which takes O(log n) time .

60. Red-Black Trees efficiency All operations work in time O(height) hence, all operations work in time O(log n)! – much more efficient than linked list or arrays implementation of sorted list !

61. Red-Black Tree Application Completely Fair Scheduler  in Linux Kernel. Computational Geometry Data structures . To keep track of the virtual memory segments for a process - the start address of the range serves as the key. Red–black trees are also particularly valuable in functional programming.

62. Comparison For small data : I nsert : RB tree will be faster because on average it uses less rotation . L ookup : AVL tree is faster, because it has less depth . D elete : RB tree is faster for it’s runtime. For large data : I nsert : AVL tree is faster, because it maintains O(log n) which is better than RB tree. Lookup : AVL tree is faster. (same as in small data case) Delete : AVL tree is faster on average, but in worst case RB tree is faster.

63. Thank You