Red-Black Trees

-

Properties:

  1. It's a height balanced BST, similar to 2-3-4 Tree.
  2. Every Node is either Red or Black
  3. Root of  a tree is Black
  4. Null is also Black
  5. Number of Blacks on paths from Root to Leaf are same
  6. No 2 consecutive Red, children and parent of Red is Black
  7. New inserted node is Red
  8. Height in logn <= h <= 2*logn (height of AVL is 1.44logn)

Comments

Post a Comment

Popular posts from this blog

Insertion/Deletion in 2-3 Tree

-
Image
Insertion:               Let we create 2-3 tree by inserting elements:                                                                      20, 30, 40, 50, 60, 10, 15, 70, 80                Insert 20,30:               Now we insert these two element in a single node as it can hold 2 elements so,       Insert 40:               Node is already full so split the node             In splitting: We take two nodes left and right and a root node Left node contain smallest element Right node contain greatest element Root node contain middle element and take lest and right as child               So the final tree will be:      Insert 50:               50 is greater than 40 and after 40 a blank space so insert 50 in that blank space:     Insert 60:               60 is greater than 50 but there is no space for 60 so split, after splitting the root element will move to the root that contain 30 b/c there is an empty space in that node, so final tree will be:     Insert 10:               10 is smal
Read more