Preconditioning

Preconditioning – What it is ?

Preconditioning is preprocessing step. It would reduce future computation. Preconditioning is particularly useful in problems having several instances involved. According to the domain of application, preconditioning either improve the accuracy or speeds up the process.

  • Consider the problem of finding ancestor of a node in tree / graph. Preconditions for this problem are described as,
  • Assume A and B are two nodes in tree.
  • If preorder(A) ≤ preorder (B), then A is ancestor of B or A is left to B in tree.
  • If postorder(A) ≥ postorder (B), then A is ancestor of B or A is right to B in tree.
  • If preorder(A) ≤ preorder (B) and postorder(A) ≥ postorder (B), then A is ancestor of B.
  • Nodes of following tree are labeled with preorder and post order traversal sequence. Italic number before node indicates preorder traversal sequence. Bold, underlined number after node indicates post order traversal sequence.
  • Let’s check if B is ancestor of C. Preorder(B) i.e. 2 is less then preorder(C), i.e. 3. These nodes satisfy first condition, so B can be ancestor of C or it can be left to C.
  • Let’s evaluate second condition. Postorder(B) i.e. 1 is not greater than postorder(C), i.e. 4, so B is not ancestor of C.
Preconditioning
  • Let’s check if A is ancestor of C. Preorder(A) i.e. 1 is less than preorder(C), i.e. 3. These nodes satisfy first condition, so A can be ancestor of C or it can be left to C.
  • Let’s evaluate second condition. Postorder(A) i.e. 5 is greater than postorder(C), i.e. 4. Nodes satisfy both conditions, so A is ancestor of C, and that we can verify from tree also.
  • These preconditions free us from traversing entire tree and compare relationships every time to check the ancestor relation between given nodes. Preorder and postorder sequence can be found in linear time, i.e. in O(n), where n is number of nodes in tree. Ancestor relationship can be verified in constant time.

Additional Reading: [Wiki]

Leave a Reply

Your email address will not be published. Required fields are marked *