APNA "Tele id - @msgmeheree" COLLEGE A Red-Black Tree is a self-balancing binary search tree in which each node has an extra bit, which represents its color (red or black). (Every Red Black Tree is a binary search tree but all the Binary Search Trees need not to be Red Black trees.) There are few properties associated with Red-Black Trees: - The root is black. (Root Property) - Every external node is black. (External Property) - The children of a red node are black. (Red Property) - All external nodes have the same black depth.(Depth Property) - Every New node must be inserted with Red color. - Every leaf (i.e. NULL node) must be colored Black. Example The following is a Red Black Tree which is created by inserting numbers from 1 to 9 and every node is satisfying all the properties of the Red Black Tree. “Tele id - @msgmeheree"APNA "Tele id - @msgmeheree" COLLEGE Most of the Binary Search Tree operations (e.g., search, max, min, insert, delete. etc) take O(h) time where h is the height of the Binary Search Tree The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that height of the tree remains O(Logn) after every insertion and deletion, then we can guarantee an upper bound of O(Logn)for all these operations. The height of a Red-Black tree is always O(Logn) where nis the number of nodes in the tree. Height of a Red-Black Tree Proving the height of the red-black tree is especially important because the height of the red-black tree is what allows us to calculate it asymptotic complexity and performance. This is one method of doing so. First imagine a red-black tree with height. Now, we merge all red nodes into their black parents. A given black node can either have: 1. 2 black children, in which ease the black parent still has 2 children. 2.1 black child and 1 red child, in which case the black parent now has 3 children. 3. 2 red children, in which case the black parent now has 4 children. Here is a graphical example of that merging process (assume any stray arrow points to a black node). We merge all the red odes into their parents nodes. Ire = number of red children a red node has then each black node will now have 2rc pointers coming out of it. “Tele id - @msgmeheree""Tele id - @msgmeheree" COLLEGE As you can see, every black node has either 2, 3, or 4 children. This new tree has a height, h1. Because any given path in the original red-black tree had at most half its*nodes red, we know that this new height is at least half the original height. So, H1 >=H/2 The number of leaves in a tree is exactly equal to n+1, so n¥1 > 24(H1) log(N+1) >= H1 >= H/2 H < 2log(n+1) Insertion in Red Black Trees In the Red-Black tree, we use two steps to do the balancing: 1. Recoloring 2. Rotation Recolouring is the change in color of the node i.e. if it is red then change it to black and vice versa. it must be noted that the color of the NULL node is. always black. Moreover, we always try recolouring first, if recolouring doesn't work, then we go for rotation. Following is a detailed algorithm. The “Tele id - @msgmeheree""Tele id- @msgmeheree" COLLEGE algorithms have mainly two cases depending upon the color of the uncle. If the uncle is red, we do recolour. if the uncle is black, we do rotations and/or recolouring. x's grandfather x's father x's uncle x's sibling Process: Let x be the newly inserted node. Perform standard BST insertion and make the color of newly inserted nodes as RED. If x is the root, change the color of x as BLACK (Black height of complete tree increases by 1). Do the following if the color of x's parent is not BLACK and x is not the root. a) If x's uncle is RED (Grandparent must have been black from property 4) (i) Change the color of parent and uncle as BLACK. (ii) Color of a grandparent as RED. (iii) Change x = x’s grandparent, repeat steps 2 and 3 for new x. b) If x's uncle is BLACK, then there can be four configurations for x, x's parent (p) and x’s grandparent (g) (This is similar to AVL Tree) (i) Left Left Case (p is left child of g and x is left child of p) “Tele id - @msgmeheree"(ii) Left Right Case (p is left child of g and x is the right child of p) (iil) Right Right Case (Mirror of case i) (iv) Right Left Case (Mirror of case ii) Recoloring after rotations: For Left Left Case [3.b (i)] and Right Right case [3.b (iii)], swap colors of grandparent and parent after rotations For Left Right Case [3.b (ii)Jand Right Left Case [3.b (iv)], swap colors of grandparent and inserted node after rotations Codesearspase see poset