Heap

Heap data structure is a specialized binary tree based data structure. Heap is a binary tree with special characteristics. In a heap data structure, nodes are arranged based on thier value. A heap data structure, some time called as Binary Heap.

There are two types of heap data structures and they are as follows...
  1. Max Heap
  2. Min Heap
Every heap data structure has the following properties...
Property #1 (Ordering): Nodes must be arranged in a order according to values based on Max heap or Min heap.
Property #2 (Structural): All levels in a heap must full, except last level and nodes must be filled from left to right strictly.

Max Heap

Max heap data structure is a specialized full binary tree data structure except last leaf node can be alone. In a max heap nodes are arranged based on node value.

Max heap is defined as follows...
Max heap is a specialized full binary tree in which every parent node contains greater or equal value than its child nodes. And last leaf node can be alone.

Example

Above tree is satisfying both Ordering property and Structural property according to the Max Heap data structure.

Operations on Max Heap

The following operations are performed on a Max heap data structure...
  1. Finding Maximum
  2. Insertion
  3. Deletion

Finding Maximum Value Operation in Max Heap

Finding the node which has maximum value in a max heap is very simple. In max heap, the root node has the maximum value than all other nodes in the max heap. So, directly we can display root node value as maximum value in max heap.

Insertion Operation in Max Heap

Insertion Operation in max heap is performed as follows...
  • Step 1: Insert the newNode as last leaf from left to right.
  • Step 2: Compare newNode value with its Parent node.
  • Step 3: If newNode value is greater than its parent, then swap both of them.
  • Step 4: Repeat step 2 and step 3 until newNode value is less than its parent nede (or) newNode reached to root.
Example
Consider the above max heap. Insert a new node with value 85.
  • Step 1: Insert the newNode with value 85 as last leaf from left to right. That means newNode is added as a right child of node with value 75. After adding max heap is as follows...
  • Step 2: Compare newNode value (85) with its Parent node value (75). That means 85 > 75
  • Step 3: Here newNode value (85) is greater than its parent value (75), then swap both of them. After wsapping, max heap is as follows...
  • Step 4: Now, again compare newNode value (85) with its parent nede value (89).
    • Here, newNode value (85) is smaller than its parent node value (89). So, we stop insertion process. Finally, max heap after insetion of a new node with value 85 is as follows...

Deletion Operation in Max Heap

In a max heap, deleting last node is very simple as it is not disturbing max heap properties.

Deleting root node from a max heap is title difficult as it disturbing the max heap properties. We use the following steps to delete root node from a max heap...
  • Step 1: Swap the root node with last node in max heap
  • Step 2: Delete last node.
  • Step 3: Now, compare root value with its left child value.
  • Step 4: If root value is smaller than its left child, then compare left child with its right sibling. Else goto Step 6
  • Step 5: If left child value is larger than its right sibling, then swap root with left child. otherwise swap root with its right child.
  • Step 6: If root value is larger than its left child, then compare root value with its right child value.
  • Step 7: If root value is smaller than its right child, then swap root with rith child. otherwise stop the process.
  • Step 8: Repeat the same until root node is fixed at its exact position.
Example
Consider the above max heap. Delete root node (90) from the max heap.
  • Step 1: Swap the root node (90) with last node 75 in max heap After swapping max heap is as follows...
  • Step 2: Delete last node. Here node with value 90. After deleting node with value 90 from heap, max heap is as follows...
  • Step 3: Compare root node (75) with its left child (89).
    • Here, root value (75) is smaller than its left child value (89). So, compare left child (89) with its right sibling (70).
  • Step 4: Here, left child value (89) is larger than its right sibling (70), So, swap root (75) with left child (89).
  • Step 5: Now, again compare 75 with its left child (36).
    • Here, node with value 75 is larger than its left child. So, we compare node with value 75 is compared with its right child 85.
  • Step 6: Here, node with value 75 is smaller than its right child (85). So, we swap both of them. After swapping max heap is as follows...
  • Step 7: Now, compare node with value 75 with its left child (15).
    • Here, node with value 75 is larger than its left child (15) and it does not have right child. So we stop the process.

    Finally, max heap after deleting root node (90) is as follows...

Tries

Red Black Tree

Red - Black Tree is another varient of Binary Search Tree in which every node is colored either RED or BLACK. We can define a Red Black Tree as follows...
Red Black Tree is a Binary Search Tree in which every node is colored eigther RED or BLACK.
In a Red Black Tree the color of a node is decided based on the Red Black Tree properties. Every Red Black Tree has the following properties.

Properties of Red Black Tree

  • Property #1: Red - Black Tree must be a Binary Search Tree.
  • Property #2: The ROOT node must colored BLACK.
  • Property #3: The children of Red colored node must colored BLACK. (There should not be two consecutive RED nodes).
  • Property #4: In all the paths of the tree there must be same number of BLACK colored nodes.
  • Property #5: Every new node must inserted with RED color.
  • Property #6: Every leaf (e.i. NULL node) must colored BLACK.

Example

THe following is a Red Black Tree which created by inserting numbers from 1 to 9.
The above tree is a Red Black tree and every node is satisfying all the properties of Red Black Tree.
Every Red Black Tree is a binary search tree but all the Binary Search Trees need not to be Red Black trees.

Insertion into RED BLACK Tree:

In a Red Black Tree, every new node must be inserted with color RED. The insertion operation in Red Black Tree is similar to insertion operation in Binary Search Tree. But it is inserted with a color property. After every insertion operation, we need to check all the properties of Red Black Tree. If all the properties are satisfied then we go to next operation otherwise we need to perform following operation to make it Red Black Tree.
  • 1. Recolor
  • 3. Rotation followed by Recolor
The insertion operation in Red Black tree is performed using following steps...
  • Step 1: Check whether tree is Empty.
  • Step 2: If tree is Empty then insert the newNode as Root node with color Black and exit from the operation.
  • step 3: If tree is not Empty then insert the newNode as a leaf node with Red color.
  • Step 4: If the parent of newNode is Black then exit from the operation.
  • Step 5: If the parent of newNode is Red then check the color of parent node's sibling of newNode.
  • Step 6: If it is Black or NULL node then make a suitable Rotation and Recolor it.
  • Step 7: If it is Red colored node then perform Recolor and Recheck it. Repeat the same until tree becomes Red Black Tree.

Example

Deletion Operation in Red Black Tree

In a Red Black Tree, the deletion operation is similar to deletion operation in BST. But after every deletion operation we need to check with the Red Black Tree properties. If any of the property is voilated then make suitable operation like Recolor or Rotaton & Recolor.
Subscribe to: Posts (Atom)