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

Heapify

-
Image
 After insertion we perform correction from last to first element and after deletion we perform correction from first to last element. Heapify is method to convert any array to correct head. We can apply heapify anytime in the array. This is the best way to correct the heap.
Read more

Binary Search Tree

-
Image
Introduction:            A Binary Search Tree or BST is a binary tree in which left child of every node contain child whose value is smaller than current node and right child will contain child whose value is greater than current node. Binary Search Tree Insertion:          There are many cases which must be consider to run the program without any error.          Function execute: Reursive function -> Node* push(data,current_node)          Every function return node or subtree which contain node to be inserted          We always start from root node           Let us consider an example of inserting 40 in the given tree     Case 1: When data < current_node->data                Step 1: Compere 40 with current_node (here root)->data, 40<50     ...
Read more

Rabin-Karp Algorithm

-
Image
String Matching: A string (say txt) and a pattern( smaller string say pat) are given and ask for finding the position of pat in txt. Let the length of txt = n and length of pat is m. Method 1: Naive Approach     Traverse string txt from 0 to (n-m+1) and in every round check if part of txt match with pat character by character. The time complexity of this algorithm will be O(m*n) . Method 2: Rabin-Karp algorithm     In this method, we use a hash function to hash pat and hash part of txt of size m and apply the rolling hash method and is the hash function of part of txt match with pat then check pat and txt character by character.     Time Complexity: O(n-m+1) Average     Time Complexity: O(n-m+1) Worst           eg: txt : a a a a a b    and      pat: a a b     Let the hashing begin with 1 and end with 26 as:           hash(a): 1      ...
Read more