Red black trees

A red-black tree is a binary search tree with one extra bit of storage per node: its color, which can be either RED or BLACK.

1. Red-Black Trees Name : TCHAYE-KONDI JUDE Simulator Link : https://www.cs.usfca.edu/~galles/visualization/RedBlack.html

2. RESUME INTRODUCTION TREE BINARY TREE BINARY SEARCH TREE RED BLACK TREE OPERATIONS

3. INTRODUCTION

4. Tree Tree is a non-linear data structure which organizes data in hierarchical structure and this is a recursive definition.

5. Root Edge

6. Leaf

7. Internal Nodes

8. Level

9. Height

10. Path

11. BINARY TREE A tree in which every node can have a maximum of two children is called as Binary Tree. A binary tree has the following time complexities : Search Operation - O(n) Insertion Operation - O(n) Deletion Operation - O(n)

12. BINARY SEARCH TREE Binary Search Tree is a binary tree in which every node contains only smaller values in its left subtree and only larger values in its right subtree.

13. BINARY SEARCH TREE  left subtree of every node contains nodes with smaller values and right subtree of every node contains larger values. Algorithm Average Worst case Search O(log  n ) O( n ) Insert O(log  n ) O( n ) Delete O(log  n ) O( n ) Time complexity

14. EG Worse Case Input : 7, 10, 13, 15 Average Case Input : 10 , 7 ,15 ,13 We can easily prove this by counting nodes on each level, starting with the root, assuming that each level has the maximum number of nodes: Geometrical sequence sum : n = 1 + 2 + 4 + ... + 2 h-1 + 2 h = 2 h+1 - 1

15. Balanced Binary Search Trees A Binary Search Tree (BST) of N nodes is balanced if height is in O(log N) A balanced tree supports efficient operations, There are many implementations of balanced BSTs, including AVL trees, RedBlack trees and AA trees.

16. RED BLACK TREE A red-black tree is a binary search tree with one extra bit of storage per node: its color , which can be either RED or BLACK . By constraining the node colors on any simple path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other. Each node of the tree now contains the attributes color, key, left, right, and p. If a child or the parent of a node does not exist, the corresponding pointer attribute of the node contains the value NIL.

17. PROPERTIES A red-black tree is a binary tree that satisfies the following red-black properties : Every node is either red or black. The root is black. Every leaf (NIL) is black. If a node is red, then both its children are black. For each node, all simple paths from the node to descendant leaves contain the same number of black nodes.

18. BLACK-HEIGHT the number of black nodes on any simple path from, but not including, a node x down to a leaf the black-height of the node, denoted bh (x) or B We define the black-height of a red-black tree to be the black-height of its root.

19. OPERATIONS & COMPLEXITY

20. OPERATIONS INSERTION, DELETION, ROTATIONS SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, AND PREDECESSOR…

21. THE NUMBER OF INTERNAL NODES OF A NODE X N(X) ≤  

22. INTERNAL NODES OF X Let prove by induction that : the subtree rooted at any node x contains at least internal nodes.   If the height of x is 0 then x must be a leaf = 0   For the inductive step, consider a node x that has positive height and is an internal node with two children : Each child has a black-height of either bh (x) or bh (x) - 1 , depending on whether its color is red or black , respectively. We conclude that each child has at least : internal nodes ( the height of a child of x is less than the height of x itself )   each child has at least internal nodes.(and we have 2 childs ) Then the subtree rooted at x contains at least ( )+( ) +1 = (+1 because of the root node)  

23. INTERNAL NODES OF X Let prove by induction that : the subtree rooted at any node x contains at least internal nodes.   If the height of x is 0 then x must be a leaf = 0   For the inductive step, consider a node x that has positive height and is an internal node with two children : Each child has a black-height of either bh (x) or bh (x) - 1 , depending on whether its color is red or black , respectively. We conclude that each child has at least : internal nodes ( the height of a child of x is less than the height of x itself )   each child has at least internal nodes. Then the subtree rooted at x contains at least ( )+( ) +1 =  

24. Conclusion THE NUMBER OF INTERNAL NODES OF A NODE X ( N(X) ) N(X) ≤  

25. HEIGHT OF A RB TREE Knowing the number of internal nodes (n)

26. HEIGHT OF A RB TREE(H) A red-black tree with n internal nodes has height at most .   According to property 4( If a node is red, then both its children are black. ) , at least half the nodes on any simple path from the root to a leaf, not including the root, must be black. Consequently, the black-height of the root must be at least h=2 ; thus, As an immediate consequence of this lemma, we can implement the dynamic-set operations SEARCH, MINIMUM, MAXIMUM, SUCCESSOR, and PREDECESSOR in Olg (n) time on red-black trees,

27. OPERATIONS They do not directly support the dynamic-set operations INSERT and DELETE, since they do not guarantee that the modified binary search tree will be a red-black tree.

28. EG Input : 8 18 5 15 Violation of the property saying : If a node is red, then both its children are black. Thus, the set operations are fast if the height of the search tree is small.

29. ROTATIONS

30. LEFT ROTATION :

31. RIGHT ROTATION

32. Rotation is followed by Recolor operation

33. INSERTION

34. INSERTION We can insert a node into an n-node red-black tree in Olg (n) time.

35. INSERTION

36. Example Input : 8 18 5 15 17 25 40 80

37. Big-O Complexity Chart