Introduction to Red Black Tree | Properties of Red Black trees | RB Tree | Data structure

#rbtree, #redblacktree, #thegatehub Contact Datils (You can follow me at) Instagram:   / ahmadshoebkhan   LinkedIn:   / ahmad-shoeb-957b6364   Facebook:   / ahmadshoebkhan   Watch Complete Playlists: Data Structures:    • Introduction to Data Structures || Basics ...   Theory of Computation:    • Introduction to Theory of Computation || G...   Compiler Design:    • Ambiguous Grammar || Introduction to Ambig...   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 way nodes can be colored on any path from the root to a leaf, red-black trees ensure that no such path is more than twice as long as any other, so that the tree is approximately balanced. Each node of the tree now contains the fields color, key, left, right, and p. If a child or the parent of a node does not exist, the corresponding pointer field of the node contains the value NIL. We shall regard these NIL'S as being pointers to external nodes (leaves) of the binary search tree and the normal, key-bearing nodes as being internal nodes of the tree. A binary search tree is a red-black tree if it satisfies the following red-black properties: 1. Every node is either red or black. 2. Every leaf (NIL) is black. 3. If a node is red, then both its children are black. 4. Every simple path from a node to a descendant leaf contains the same number of black nodes. Why Red-Black Trees? Most of the BST operations (e.g., search, max, min, insert, delete.. etc) take O(h) time where h is the height of the BST. The cost of these operations may become O(n) for a skewed Binary tree. If we make sure that the height of the tree remains O(log n) after every insertion and deletion, then we can guarantee an upper bound of O(log n) for all these operations. The height of a Red-Black tree is always O(log n) where n is the number of nodes in the tree. Comparison with AVL Tree: The AVL trees are more balanced compared to Red-Black Trees, but they may cause more rotations during insertion and deletion. So if your application involves frequent insertions and deletions, then Red-Black trees should be preferred. And if the insertions and deletions are less frequent and search is a more frequent operation, then AVL tree should be preferred over Red-Black Tree. what is red black tree,red black tree in data structure,introduction to red black tree in data structure,properties of red black tree,avl tree vs red black tree,red black tree,red black tree in daa,rb tree insertion algorithm,rb tree insertion,rb tree deletion,red black tree in data structure in hindi,red black tree deletion,red black tree insert,red black tree,red black tree in hindi,red black tree algorithm,red black tree insertion algorithm,rb tree properties,rb tree insertion and deletion,red-black tree vs avl,red-black tree example, red-black tree simulator,red black tree c++,red-black tree properties, red-black tree implementation,red-black tree deletion,red-black tree ppt